牛客网暑期ACM多校训练营（第四场）A 题解 (欧拉降幂)

题意:给你一个长度小于1e5的串，每次进行一次操作，在字符1后面插入一个0.在字符2后面插入一个1，然后删除首字符。

然后问你需要操作多少次，字符串会变成空串。

先写个暴力程序找找规律。
下面给出我的暴力代码。

#include 
using namespace std;
string ch(string s)
{
    int n=s.size();
    string ans;
    for(int i=0;i<n;i++)
    {
        if(i!=0) ans+=s[i];
        if(s[i]=='1')
        {
            ans+='0';
        }
        else if(s[i]=='2')
        {
            ans+='1';
        }    
    }
    return ans;
}
int main()
{
    string s;
    while(cin>>s)
    {
            int ans=0;
        while(1)
        {
            if(s.size()==0) break;
            //cout<<s<<endl;
            s=ch(s);
            ans++;
        }
        cout<<ans<<endl;
    }
    return 0;
}

每次我们加个1，假设没加1之前的操作次数是x，那么加了1之后操作次数就是2x+2。

每次我们加个2，假设没加2之前的操作次数是x，那么加了2之后的操作次数就变成3*(2^(x+1)-1)，这个怎么找到的呢。

我们看到类似9,21,45,93这种都是3的倍数，我们把他们都除以3，得到3,7,15,31...发现他们都是2^n-1，那么规律就找到了。

当我们每次加个0,操作次数就加1,这个没啥说的。

到这时我们递推一下就行了。
1: x+x+2
2: 3*2^(x+1)
0: x+1
然后我们交上去发现超时了%50！！难道评测姬坏掉了QAQ
没超时的大佬下面的不用看了~~~
仔细观察发现如果每次碰到2直接用快速幂算2^(x+1),那么n有2e6。极端情况下碰到全为2的串。我们每次都要算一次快速幂。那么评测姬

就会类似于这样，咳咳！！然而我们必须每次都算一次快速幂。
那么如何优化类似于(a^b^c^d^e.....)%mod这种式子。需要用到一个叫欧拉降幂的知识 (先%一下欧拉orz)。
关于欧拉降幂我也是刚学的，然后学的东西写这篇博客里了
https://blog.csdn.net/qq_37632935/article/details/81264965
那么学会欧拉降幂后这题就可以预处理出(ph...(ph(ph(1e9+7)))的所有欧拉函数值了。不能每次都求，要把它们先记下来，不然还是会T。
给出代码

#include 
using namespace std;
typedef long long ll;
map m;
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 quick_pow(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;
}
char s[100005];
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]=='2') return ((3ll*quick_pow(2,dfs(i-1,m[mod])+1,mod)-3)%mod+mod)%mod;
    else return (2*dfs(i-1,mod)+2)%mod;
}
int main()
{
    ll mo=1e9+7;
    while(mo!=1)
    {
        m[mo]=PH(mo);
        mo=m[mo];
    }
    m[1]=1;
    int T;
    scanf("%d",&T);
    while(T--)
    {
        ll mod=1e9+7;
        cin>>s+1;
        int n=strlen(s+1);
        printf("%lld\n",dfs(n,mod));
    }
    return 0;
}
/*
1  x+2
2  3*2^(x+1)-x
*/

贴一个循环的代码。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll mod[100005];
ll quick_pow(ll a, ll b, ll mo)
{
    ll res = 1;
    while(b)
    {
        if(b & 1)
            res = res * a % mo;
        b >>= 1;
        a = a * a % mo;
    }
    return res;
}
ll euler(ll n)   //??euler(n)
{
    ll res = n, a = n;
    for(ll i = 2; i * i <= a; 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;
}
char s[100005];
int main()
{
    mod[0] = 1e9 + 7;
    for(int i = 1; i < 1e5 + 5; i++)
    {
        mod[i] = euler(mod[i - 1]);
//        printf("%d---%lld\n",i,mod[i]);
    }
    int t;
    scanf("%d", &t);
    while(t--)
    {
        scanf("%s", s);
        int cnt = 0;
        for(int i = 0; s[i] != 0; i++)
        {
            if(s[i] == '2')
                cnt++;
        }
        ll ans = 0;
        for(int i = 0; s[i] != 0; i++)
        {
            if(s[i] == '0')
            {
                ans++;
                ans %= mod[cnt];
            }
            else if(s[i] == '1')
            {
                ans = (ans + ans + 2) % mod[cnt];
            }
            else
            {
                cnt--;
                if(ans<mod[cnt])        
                    ans = 3ll * (quick_pow(2ll, (ans + 1) % mod[cnt], mod[cnt]) - 1 + mod[cnt]) % mod[cnt];                
                else
                { 
                    ans = 3ll * (quick_pow(2ll, (ans + 1) % mod[cnt]+mod[cnt], mod[cnt]) - 1 + mod[cnt]) % mod[cnt];
                }
            }

        }
        printf("%lld\n", ans);

    }
}