2018牛客暑假多校四 A（打表+数论）

题目描述：

    给个长度为n的三进制串，有这样一个操作：在每个2后⾯面插入一个1，每个1后面插 入一个0，然后删掉第一个字符。问多少次操作后，变成空串 n <= 1e5。

题目分析：

    比赛的时候一直不知道要怎么做，直到赛后才知道这题是个打表题然后用数论的知识进行解决。（emmmm，原本表就打不出来了，结果还加个数论emmmmm）于是我们就来学习一下这题的做法。

    首先我们要发现（愉快的打表过程开始了），在删除字符串的过程中，如果遇到0，直接删除，操作次数+1。而如果遇到1，假设我们之前操作了x次，那么这个1后面就多产生了x个0。因此，此时我们需要再经过x+2次操作才能删完所有字符。而当遇到2，考虑之前已经操作了了x次，然后打(oe)个(is)表可以发现，之后还需要经过次操作才能全部删完 。

    但是，直接快速幂取模或者用矩阵快速幂去处理上述的式子是不可行的，因为x可能相当的大，这就使得如果使用快速幂之类的求幂算法必定会超时。因此我们需要考虑数论中的一种降幂公式。具体看下图：

    有了这条公式，我们就可以进行运算了。但是这里还有一个问题，我们要计算，于是也得计算，同理也还得继续求出，依次类推。因此我们可以优先预处理出来1到1e5的模数的欧拉函数，之后如果遇到字符‘2’则直接调用即可。

代码：

#include <bits/stdc++.h>
#define maxn 100010
using namespace std;
typedef long long ll;
ll powmod(ll a,ll n,ll mo){//快速幂
    ll res=1;
    while(n){
        if(n&1){
            res=res*a%mo;
        }
        n>>=1;
        a=a*a%mo;
    }
    return res;
}
ll eular(ll n){//欧拉函数
    ll res=n;
    for(ll i=2;i*i<=n;i++){
        if(n%i==0){
            res-=res/i;
            while(n%i==0){
                n/=i;
            }
        }
    }
    if(n>1) res-=res/n;
    return res;
}
ll mod[maxn];//模数
void init(){//预处理模数
    mod[0]=1e9+7;
    for(int i=1;i<=1e5+5;i++){
        mod[i]=eular(mod[i-1]);
    }
}
char str[maxn];
int main()
{
    int t;
    scanf("%d",&t);
    init();
    while(t--){
        scanf("%s",str);
        int cnt=0;
        ll ans=0;
        for(int i=0;str[i]!=0;i++){
            if(str[i]=='2') cnt++;//有几个2就有多少个模数调用
        }
        for(int i=0;str[i]!=0;i++){
            if(str[i]=='0'){
                ans++;
                ans%=mod[cnt];
            }
            else if(str[i]=='1'){
                ans=(ans+ans+2)%mod[cnt];
            }
            else{
                cnt--;
                ans=3ll*(powmod(2ll,(ans+1)%mod[cnt],mod[cnt])-1+mod[cnt])%mod[cnt];
            }
        }
        cout<<ans<<endl;
    }
}