题目描述
A ternary string is a sequence of digits, where each digit is either 0, 1, or 2.
Chiaki has a ternary string s which can self-reproduce. Every second, a digit 0 is inserted after every 1 in the string, and then a digit 1 is inserted after every 2 in the string, and finally the first character will disappear.
For example, ``212'' will become ``11021'' after one second, and become ``01002110'' after another second.
Chiaki would like to know the number of seconds needed until the string become an empty string. As the answer could be very large, she only needs the answer modulo (109 + 7).
Chiaki has a ternary string s which can self-reproduce. Every second, a digit 0 is inserted after every 1 in the string, and then a digit 1 is inserted after every 2 in the string, and finally the first character will disappear.
For example, ``212'' will become ``11021'' after one second, and become ``01002110'' after another second.
Chiaki would like to know the number of seconds needed until the string become an empty string. As the answer could be very large, she only needs the answer modulo (109 + 7).
输入描述:
There are multiple test cases. The first line of input is an integer T indicates the number of test cases. For each test case:
The first line contains a ternary string s (1 ≤ |s| ≤ 10^5)
It is guaranteed that the sum of all |s| does not exceed 2 x 10^6
输出描述:
For each test case, output an integer denoting the answer. If the string never becomes empty, output -1 instead.
题意：给出一串字符，只包含012，每过一秒有以下的操作（在所有的2后面插一个1，在所有的1后面插一个0，删掉第一个字符），
问经过多少秒之后才会消完整个字符串
思路：我们想前面每经过一秒，后面又会多加了一堆数，所以前面插入数的次数会影响到后面，所以我们可以打表去找规律
我们会发现如下规律
如果前面经过x次 那当前是0的话，到这就是x+1次
如果前面经过x次 那当前是1的话，到这就是2*（x+1）次
如果前面经过x次 那当前是2的话，到这就是3*（2^(x+1)-1）次
所以我们就需要知道每个字符前到底发生多少次，我们又想算出前面的值之后再递推回来一个一个的算后面的值
这明显就是一个递归的过程，所以我们从最后一个字符开始，递归算出前面的值之后再来算当前值，但是这个字符串长度这么长
我们这个次方明显是成几何倍数递增的，所以快速幂已经不能完全解决问题，我们就可以考虑到数论里面的一个欧拉降幂
然后套一个欧拉降幂的模板即可，因为广义欧拉的推导我也不会>_<
公式 ： a^x=a^(phi(p)+x mod phi(p))mod p
#include<bits/stdc++.h> #define lson l,m #define rson m+1,r using namespace std; typedef long long ll; typedef unsigned long long ull; const int maxn = int(1e5) + 100; const int maxm=100; const int BN = 30; const int inf = 0x3f3f3f3f; const ll INF = 0x3f3f3f3f3f3f3f3f; const int mod = (int)1e9 + 7; const double EPS = 1e-12; char str[maxn]; map<ll,ll>mo; ll phi(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 base,ll n,ll modd) { //快速幂 ll ans=1; while(n) { if(n&1) ans=ans*base%modd; base=base*base%modd; n>>=1; } return ans; } void init(int mod){ //预处理出所有的欧拉降幂 while(mod!=1){ mo[mod]=phi(mod); mod=mo[mod]; } mo[1]=1; } ll dfs(int pos,int mod) {//递归分别对应三个数字不同的情况 我们会递归到最底的时候把前面有多少数递归回来 if(pos==0) return 0; else if(str[pos]=='0') return (dfs(pos-1,mod)+1)%mod; else if(str[pos]=='1') return (2*dfs(pos-1,mod)+2)%mod; else return (3*quick_pow(2,dfs(pos-1,mo[mod])+1,mod)-3+mod)%mod; } int main() { init(mod); int T; scanf("%d",&T); while(T--) { memset(str,0,sizeof(str)); scanf("%s",str+1); int len=strlen(str+1); ll ans=dfs(len,mod); printf("%lld ",ans); } return 0; }