牛客网暑期ACM多校训练营（第四场）：A Ternary String（欧拉降幂）

链接：牛客网暑期ACM多校训练营（第四场）：A Ternary String

题意：给出一段数列 s，只包含 0、1、2 三种数。每秒在每个 2 后面会插入一个 1 ，每个 1 后面会插入一个 0，之后第一个数字消失。求最后为空串需要多少秒。

题解：

（1）如果在消除一个 0 前经过了 n 秒，那么消掉这个 0 需要 n + 1 秒。

（2）如果在消除一个 1 前经过了 n 秒，那么消掉这个 1 与其产生的所有数需要 (n + 1) * 2 秒。

（3）如果在消除一个 2 前经过了 n 秒，那么消掉这个 2 与其产生的所有数需要 (2 ^ (n + 1) - 1) * 3 秒。

需要用欧拉定理降幂。

#include <bits/stdc++.h>

using namespace std;

const double EPS = 1e-;

const int INF = 0x3f3f3f3f;

const long long mod = 1e9 + ;

const int maxn = 1e5 + ;

char s[maxn];

map<long long, long long> phi;

long long Eul(long long n)

{

    long long ans = n;

    for(int i = ; i * i <= n; i++){

        if(n % i == ){

            ans -= ans / i;

            while(n % i == ) n /= i;

        }

    }

    if(n > ) ans -= ans / n;

    return ans;

}

long long Mod(long long x, long long y)     //欧拉定理的条件

{

    return x < y ? x : x % y + y;

}

long long pow_mod(long long x, long long n, long long mod)

{

    long long ans = ;

    while(n){

        if(n & ) ans = Mod(ans * x, mod);

        x = Mod(x * x, mod);

        n >>= ;

    }

    return ans;

}

long long DFS(int i, long long mod)

{

    if(i < ) return ;

    if(s[i] == '') return Mod((DFS(i-, mod) + ), mod);

    if(s[i] == '') return Mod((DFS(i-, mod) + ) * , mod);

    if(s[i] == '') return Mod((pow_mod(, DFS(i-, phi[mod]) + , mod) - ) * , mod);

    return ;

}

int main()

{

    for(long long x = mod, y = Eul(x); x != y; y = Eul(y)) phi[x] = y, x = y; phi[] = ;

    int T;

    scanf("%d", &T);

    while(T--){

        scanf("%s", s);

        printf("%lld\n", DFS(strlen(s) - , mod) % mod);

    }

    return ;

}