牛课暑假多校第四场 A-Ternary String（欧拉降幂）

淩亂°似流年 2022-05-18 02:40 124阅读 0赞

[传送门][Link 1]

思路：从前往后遍历字符串，如果遇到0，那么时间就是T+1（假设T是之前所用的时间）

如果遇到‘1’，时间是2\*T+2， 因为在之前的T时间，这个‘1’会产生T个零，消去这个‘1’的时候还会产生1个‘0’，这样算的话就是产生了T+1个’0‘，再加上之前的时间T, 消去这个’1‘的时间 1， 总共为  2\*T+2的时间；

如果遇到’2‘，时间是3\*（pow（2， T+1）-1）。因为遇到这个’2‘的时候会产生T个’1‘， 消去’2‘的时候还会产生一个‘1’，每个‘1’后面分别有0、1、2、……T个‘0’，这样可以推算一下，我推了一个递推式子。![a\[n\]=2\*a\[n-1\]+1][a_n_2_a_n-1_1],a\[n\]是消去第n个’1‘及其它产生的’0‘，需要的时间，a\[1\]是2，这样数列求和为![s\[n\]=3\*(2^\{n\}-1)-n][s_n_3_2_n_-1_-n],n是T+1，所以用的时间就是3\*（pow（2， T+1）-1）-（T+1）+（T+1）=3\*（pow（2， T+1）-1）；

另外由于T是不断取模的，所以，直接用T+1当次幂的话不正确，所以就用到欧拉降幂，如下：

若gcd(a,m)=1，那么使用欧拉定理即可：a^b≡a^(b%φ(m))(mod m)

若gcd(a,m)>1，且b>φ(m)，则有“求幂大法”——**a^b≡a^(b%φ(m)+φ(m))(mod m)**

（当b<=φ(m)时直接用快速幂即可）

但有个问题，不知道为什么只用a^b≡a^(b%φ(m))(mod m)这个公式答案是对的。

#include<bits/stdc++.h>
    
    using namespace std;
    typedef long long ll;
    const ll mod=1e9+7;
    const int N =1e5+5;
    ll s, mo;
    ll phi[N];
    char str[N];
    int cnt=1, num;
    
    ll Phi(ll x){
        ll m=sqrt(x+0.5),ans=x;
        for(ll i=2;i<=m;i++){
            if(x%i==0){
                ans=ans/i*(i-1);
                while(x%i==0)x/=i;
            }
        }
        if(x>1)ans=ans/x*(x-1);
        return ans;
    }
    
    void init(){
    
        phi[0]=mod;
        while(phi[cnt-1]!=1){
            phi[cnt]=Phi(phi[cnt-1]);
            cnt++;
        }
        //for(int i=0;i<cnt;i++){
        //  printf("i:%d %lld\n",i,phi[i]);
       //}
    }
    
    ll _pow(ll bas, ll x){
        ll ans=1;
    
        while(x){
    
            if(x&1)
                ans=ans*bas%mo;
    
            bas=bas*bas%mo;
            x>>=1;
        }
        return ans;
    }
    
    int main()
    {
        init();
        int T;
        scanf("%d", &T);
        while(T--){
            s=0;
            scanf("%s", str);
            int len=strlen(str);
    
            for(int i=0; i<len; i++)
                if(str[i]=='2') num++;
    
            mo=num>=28? 1ll:phi[num];
    
            for(int i=0; i<len; i++){
                if(str[i]=='0'){
                    s++;
                    s%=mo;
                }
                else if(str[i]=='1'){
                    s=s+s+2;
                    s%=mo;
                }
                else{
                    
                    num--;
                    mo=num>=28? 1ll:phi[num];
                    s++;
                    s%=mo;
                    ll tmp=3ll*(_pow(2ll, s)-1ll)-s;
                    s=(s+tmp+mo)%mo;
                }
            }
            printf("%lld\n", (s%mo+mo)%mo);
        }
    
        return 0;
    }

[Link 1]: https://www.nowcoder.com/acm/contest/142/A
[a_n_2_a_n-1_1]: https://private.codecogs.com/gif.latex?a%5Bn%5D%3D2*a%5Bn-1%5D&plus;1
[s_n_3_2_n_-1_-n]: https://private.codecogs.com/gif.latex?s%5Bn%5D%3D3*%282%5E%7Bn%7D-1%29-n