2018 牛客多校联盟 第四场总结

牛客多校联盟 第四场总结

本场是找规律场，我个菜鸡找不到，我心好累

A

遇到0时直接去掉
假设遇到1时，已经走了 t，消除这个1的效果还需要 t+2
假设遇到2时，已经走了t，消除这个2的效果还需要 3∗(2t+1−1)−t $3\ast (2^{t+1}-1)-t$（怎么找到的，打表找规律）
假设共有n个2且最后一个是2，那么解的形式就是 3∗（222..+t2+1+t1+1−1） $3\ast （2^{2^{2^{..}+t_2+1}+t_1+1}-1）$
需要欧拉降幂公式来实现求模
AK≡AK%ϕ(mod)+ϕ(mod)(% mod)K>ϕ(mod) $A^K\equiv A^{K\%\varphi \left(mod\right)+\varphi \left(mod\right)}\left(\%mod\right)K>\varphi \left(mod\right)$

const int maxn = 1e5+100;
char ar[maxn];
LL qpow(LL a,LL b,LL c){
    LL ans = 1;
    a %= c;
    while(b > 0){
        if( b & 1) ans = ans*a%c;
        a = a*a%c;
        b >>= 1;
    }
    return ans;
}
int Euler(int n){
    if(n == 1) return 0;
    int t = n;
    int m = sqrt(n+0.5);
    for(int i = 2;i <= m; ++i)
       if(n % i == 0){
         t = t/i*(i-1);
         while(n % i == 0)  n /= i;
       }
   if(n != 1)
      t = t/n*(n-1);
    return t;  
}
LL euler[maxn];
LL MOD(LL x,LL y){
    return x < y?x:x%y+y; 
}
int main(void)
{
    //cout<<Euler(1)<<endl;
    me(euler);
    euler[0] = mod;
    for(int i = 1;i <= 28; ++i){
        euler[i] = Euler(euler[i-1]);
//      cout<<euler[i]<<endl;
    }
    for(int i =  28; i < maxn ;++i)
        euler[i] = 1;
    int T;
    cin>>T;
   while(T--){
    scanf("%s",ar);
    int len = strlen(ar);
    int cnt = 0; // 统计一下2 的个数
    for(int i = 0;i < len; ++i){
        if(ar[i] == '2') cnt++;
       }
    LL x  = 0;
    for(int i = 0;i < len; ++i){
        if(ar[i] == '2') cnt--;
        if(cnt > 30) continue;
         if(ar[i] == '0')
//           x = (x+1)%euler[cnt];
             x = MOD(x+1,euler[cnt]);
        else if(ar[i] == '1')
//             x = (x+x+2)%euler[cnt];
             x = MOD(x+x+2,euler[cnt]);
          if(ar[i] == '2'){
                x = (3*(qpow(2, x+1, euler[cnt])%euler[cnt]-1)+euler[cnt]) % euler[cnt];
        }
    }

    printf("%lld\n",(x%mod+mod)%mod);
   }   

   return 0;
}

B Interval Revisited

线段树优化+dp，补题跟不上了，只能先鸽置了

Chiaki Sequence Reloaded

找规律，我是真不会 找规律+ 数位dp

DAnother Distinct Values

找规律构造我也不会，4的时候把 2的放中间，然后