题意：你有一个长度为(n)，且仅由012构成的字符串。每经过一秒，这个字符串所有1后面会插入一个0，所有2后面会插入一个1，然后会删除第一个元素。求这个字符串需要多少秒变为空串，对(10^9+7)取模。
(n leq 10^5)
显然这个答案是可以从左往右维护当前已经经过的时间，一位位算过来的。
设当前已经经过了(n)秒，那么，容易得到再删除下一个0需要1秒，再删除下一个1需要(n+2)秒。然而若下一个元素为2，似乎并不好处理。但至少我们能得到一个(O(n))的算法：
int func1(int n) { // 删除1所需时间
return n + 2;
}
int func2(int n) {
int ret = 0;
for (int k = 0 ; k <= n ; ++ k) // 统计删除这个2所产生的1的时间
ret = ret + func1(ret) + k;
ret = ret + 1; // 删除这个2还要1秒
return ret;
}
于是，我们设数列({a_n})表示(n)后删除一个2的时间是(a_n+1)，那么，我们能得到(a_n = 2a_{n-1} + n + 2)。那么，我们就能求出其通项式(a_n = 6 imes 2^n - n - 4)。
因此，删除下一个2需要(6 imes 2^n - n - 3)秒。
到这里问题还没有解决，因为(n)在指数里面。这样，如果我们要求答案对(10^9+7)取模的值，就要求答案对(phi(10^9+7))取模的值。而当模数(p)与(2)不互质时，可以参考bzoj3884的做法，令(p=2^k q)，其中(gcd(2,q)=1)，那么我们有(2^n mod p = 2^k (2 ^{n-k} mod q) = 2^k (2^{n-k mod phi(q)}))。于是我们就可以缩小模数，一直到1。因为所有不等于(1)的(q)都有(2 | phi (q))，所以除第一个外所有(p)都是偶数，则(phi(q) leq q leq frac {p} {2})。因此我们只要对(O(log n))个答案求解。
实现时还要考虑(n < k)的情况，特判一下就可以了。
时间复杂度(O(n log^2 n))。
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 100010, MAX = 40000, MOD = (int)(1e9 + 7);
char s[N];
int n,isp[MAX + 10],pri[MAX],pcnt,val[N],nex[N],sta[N],top,rel[N];
int getphi(int x) {
int ret = x;
for (int i = 1 ; pri[i] * pri[i] <= x ; ++ i) {
if (x % pri[i] == 0) {
ret /= pri[i];
ret *= pri[i] - 1;
while (x % pri[i] == 0) x /= pri[i];
}
}
if (x != 1) ret = ret / x * (x-1);
return ret;
}
int power(int a,int b,int mod) {
int ret = 1;
while (b) {
if (b&1) ret = 1ll * ret * a % mod;
a = 1ll * a * a % mod;
b >>= 1;
}
return ret;
}
void prework() {
for (int i = 2 ; i <= MAX ; ++ i) {
if (!isp[i]) pri[++pcnt] = i;
for (int j = 1 ; j <= pcnt && pri[j] * i <= MAX ; ++ j) {
isp[pri[j] * i] = 1;
if (i % pri[j] == 0) break;
}
}
for (int cur = MOD ; ; ) {
sta[++top] = cur;
if (cur == 1) break;
while ((cur&1) == 0) cur >>= 1;
cur = getphi(cur);
}
}
signed main() {
int T;
prework();
scanf("%lld",&T);
while (T --) {
scanf("%s",s+1);
n = strlen(s+1);
for (int i = 0 ; i <= n ; ++ i)
val[i] = 0;
rel[0] = 0;
for (int i = 1 ; i <= n ; ++ i) rel[i] = -1;
for (int i = 1 ; i <= n ; ++ i) {
if (s[i] == '0') rel[i] = rel[i-1] + 1;
if (s[i] == '1') rel[i] = 2 * (rel[i-1] + 1);
if (s[i] == '2') rel[i] = 6 * power(2,rel[i-1],MOD) - 3;
if (rel[i] >= 20) {
rel[i] = -1;
break;
}
}
for (int i = top - 1 ; i >= 1 ; -- i) {
int y = sta[i], x = 1, k = 0;
while ((y&1) == 0) x <<= 1, k ++, y >>= 1;
for (int j = 1 ; j <= n ; ++ j) {
if (s[j] == '0') nex[j] = 1;
else if (s[j] == '1') nex[j] = (nex[j-1] + 2) % sta[i];
else {
if (rel[j-1] != -1) nex[j] = (6 * power(2,rel[j-1],sta[i]) - nex[j-1] - 3) % sta[i];
else nex[j] = ((x * power(2,((val[j-1] - k) % sta[i+1] + sta[i+1]) % sta[i+1],y)) * 6 - nex[j-1] - 3) % sta[i];
}
nex[j] = (nex[j-1] + nex[j]) % sta[i];
}
for (int j = 0 ; j <= n ; ++ j)
val[j] = (nex[j] % sta[i] + sta[i]) % sta[i];
}
printf("%lld
",val[n]);
}
return 0;
}
小结：本题无非不是两个部分，一是数列求解，二是处理指数。关键还是在于清晰的思路。