Ternary String（欧拉降幂）

题目链接

https://ac.nowcoder.com/acm/contest/142/A

题目大意

给你一个由0,1,2组成的三元字符串，每一秒按照顺序进行三个操作

1.在每一个1后面插入一个0

2.在每一个2后面插入一个1

3.删除第一个字符

问多少秒后可以把字符串删空

解题思路

通过分析（打表），可以知道

1.遇到0，直接删除，次数加一

2.遇到1，因为前面已经操作了x次，这个1后面多出了x个0，这个时候需要再进行x+2次操作

3.遇到2，因为前面已经操作了x次，打表发现还需要次3*（2^（x+1）-1)次操作

因为次数过大，所以要有模操作，但是指数取模会出错，因此要用到欧拉降幂。

代码

#include <bits/stdc++.h>
const int maxn=1e5+100;
using namespace std;
#define ll long long
char s[maxn];
#define MOD(a,b) a>=b?a%b+b:a
#define ll long long
unordered_map<int,int>mp;
int n,q,l,r;
ll m,w[maxn];
ll qpow(ll a,ll b,ll mod)
{
    ll res=1;
    while(b)
    {
        if(b&1)res=MOD(res*a,mod);
        a=MOD(a*a,mod);
        b>>=1;
    }
    return res;
}
ll phi(ll k)
{
    ll x=k,s=k;
    if(mp.count(k))return mp[k];
    for(int i=2;i*i<=k;i++)
    {
        if(k%i==0)s=1ll*s/i*(i-1);
        while(k%i==0) k/=i;
    }
    if(k>1)s=s/k*(k-1);
    mp[x]=s;
    return s;
}
ll solve(int id,ll mod)
{
    if(id==0)return 0;
    else if(s[id]=='0')return (solve(id-1,mod)+1)%mod;
    else if(s[id]=='1')return (2*solve(id-1,mod)+2)%mod;
    else return (3ll*qpow(w[id], solve(id-1, phi(mod))+1, mod)-3+mod)%mod;
}
int main()
{
    ios::sync_with_stdio(false);
    for(int i=0;i<maxn;i++){
        w[i]=2;
    }
    int t;
    cin>>t;
    while(t--){
        cin>>s+1;
        int n=strlen(s+1);
        r=n;
        cout<<solve(n,1e9+7)<<endl;
    }
    return 0;
}

（以弃用版本，由于存在缺陷）

#include <bits/stdc++.h>
const int maxn=1e5+100;
using namespace std;
#define ll long long
map<ll,ll>m;
char s[maxn];
ll ph(ll x){
    ll res=x,a=x;
    for(ll i=2;i*i<=x;i++){
        if(a%i==0){
            res=res/i*(i-1);
            while(a%i==0) a/=i;
        }
    }
    if(a>1) res=res/a*(a-1);
    return res;
}
ll qpow(ll a,ll b,ll mod){
    ll ans=1;
    while(b){
        if(b&1) ans=(ans*a)%mod;
        a=(a*a)%mod;
        b>>=1;
    }
    return ans;
}
ll dfs(ll i,ll mod){
    if(i==0)return 0;
    else if(s[i]=='0')return (dfs(i-1,mod)+1)%mod;
    else if(s[i]=='1')return (2*dfs(i-1,mod)+2)%mod;
    else
        return (3ll*qpow(2,dfs(i-1,m[mod])+(1+m[mod])%m[mod],mod)-3+mod)%mod;
}
int main()
{
    ios::sync_with_stdio(false);
    long long mo=1e9+7;
    while(mo!=1){
        m[mo]=ph(mo);
        mo=m[mo];
    }
    m[1]=1;
    int t;
    cin>>t;
    while(t--){
        cin>>s+1;
        int n=strlen(s+1);
        cout<<dfs(n,1e9+7)<<endl;
    }
    return 0;
}