牛客网暑期ACM多校训练营(第四场):A Ternary String(欧拉降幂)

时间:2022-09-23 10:45:14

链接:牛客网暑期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 ;
}