定义 (nxt_i) 表示在字符串 (S) 中以 (i) 结尾的最长 (border)。
引理一：若 (n - nxt_n mid n) 则 (S_{1 sim n - nxt_n}) 为原串的最小循环节。
引理二：若 (n - nxt_n mid n) 则 (S_{1 sim n - nxt_n}) 为原串的弱循环节（即原串可以 (S_{1 sim n - nxt_n}) 不断循环但最终一段不能完整循环完毕）
关于引理一的 证明，引理二类似。
为了方便，下面我们令 (g(S) = S_{1 sim n - nxt_n} = T)。
观察一下 (f) 的变化规则可以发现，第一次我们一定会找到 (S) 的最长 (border) 然后在后面接上 (SS) 除了前后两个 (border) 的中间部分，即 (f(SS) = STST)。
因为生成的 (f) 依然是偶串，那么前后串必然相同，经过无限次迭代后我们只需考虑前半部分即 (S) 演变规律即可。
因为 (f(S) = Sg(S)) 不难发现难点在于如何找到每次迭代后的 (g(S))。
基于观察可以发现以下两个性质：
-
若 (|g(S)| mid |S|) 则 (g(f(S)) = g(S))
-
否则 (g(f(S)) = S)
性质一的证明是显然的，下面考虑如何证明性质二。
根据引理二，只需证明 (T) 为 (f(S)) 的最长 (border) 即可。
假设存在一个更长的 (border X, |X| > |T|)，首先假设 (|T| mid |X|)。
可以发现 (X \% T)（(X) 比上一个 (T) 多出来的部分） 会是 (T) 的一个弱循环节，若此时 (|X \% T| mid |T|) 则 (S) 存在一个更短的弱循环节 (X \% T)。
否则，以原来 (S) 的视角观察 (T) 可以发现 (T \% (X \% T)) 会是 (X \% T) 的的一个弱循环串。
注意到其本质是对于一个原串 (b) 其弱循环节 (a) 必然能推出 (b \% a) 为 (a) 的弱循环节，本质上即 ((a, b) ightarrow (b \% a, a)) 这就是辗转相除的过程。
所以我们必然可以推出 (gcd(X \% T, T)) 会是原串的弱/真循环节其长度小于 (T)，矛盾。
对于 (|T| mid |X|) 的从 (border) 处以类似的方式也可推出矛盾。
这样一来，就可以发现 (f) 进过无限次迭代之后的规律了。
-
若 (|T| mid |S|) 则 (f ^ infty (S) = STTTTTcdots)
-
若 (|T| mid |S|) 则 (f ^ i (S) = f ^ {i - 1} (S) + f ^ {i - 2} (S))
对于第一种情况，直接计算即可。
对于第二种情况，首先差分转化为求 ([1, r]) 中字符的出现次数。因为斐波那契的增长速度是指数级的，因此我们可以暴力计算出 (f) 在 (1e18) 长度内每个值的字符出现个数；最终直接使用递归的方式往下求解即可。
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define rep(i, l, r) for (int i = l; i <= r; ++i)
const int N = 2e5 + 5;
const int M = 30 + 5;
char s[N]; int n, l, r, nxt[N], ans[N];
int read() {
char c; int x = 0, f = 1;
c = getchar();
while (c > '9' || c < '0') { if(c == '-') f = -1; c = getchar();}
while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
return x * f;
}
namespace S1 {
void solve(int L, int buf) {
rep(i, 1, n - nxt[n]) ans[s[i] - 'a'] += buf * (max(0ll, L - n) / (n - nxt[n]));
rep(i, 1, min(L, n)) ans[s[i] - 'a'] += buf;
if(L > n) rep(i, 1, L % (n - nxt[n])) ans[s[i] - 'a'] += buf;
}
}
namespace S2 {
int g[N], f[N][M];
void dfs(int p, int L, int buf) {
if(!L) return ;
if(p == 0) { rep(i, 1, L) ans[s[i] - 'a'] += buf; return ; }
if(p == 1) {
rep(i, 1, min(L, n)) ans[s[i] - 'a'] += buf;
rep(i, 1, L - n) ans[s[i] - 'a'] += buf;
return ;
}
if(g[p - 1] <= L) {
rep(i, 0, 25) ans[i] += f[p - 1][i] * buf;
dfs(p - 2, L - g[p - 1], buf);
}
else dfs(p - 1, L, buf);
}
void solve(int L, int buf) {
memset(f, 0, sizeof(f)), memset(g, 0, sizeof(g));
rep(i, 1, n) f[0][s[i] - 'a']++, f[1][s[i] - 'a']++;
rep(i, 1, n - nxt[n]) f[1][s[i] - 'a']++;
g[0] = n, g[1] = n * 2 - nxt[n];
for (int i = 0; ; ++i) {
if(i > 1) {
g[i] = g[i - 1] + g[i - 2];
rep(j, 0, 25) f[i][j] = f[i - 1][j] + f[i - 2][j];
}
if(g[i] > L) { dfs(i, L, buf); break;}
}
}
}
signed main() {
scanf("%s", s + 1), n = strlen(s + 1) / 2;
l = read(), r = read();
for (int i = 2, j = 0; i <= n; ++i) {
for (; s[i] != s[j + 1] && j; j = nxt[j]) ;
nxt[i] = ((s[i] == s[j + 1]) ? (++j) : j);
}
if(n % (n - nxt[n]) == 0) {
S1 :: solve(r, 1), S1 :: solve(l - 1, -1);
rep(i, 0, 25) printf("%lld ", ans[i]);
}
else {
S2 :: solve(r, 1), S2 :: solve(l - 1, -1);
rep(i, 0, 25) printf("%lld ", ans[i]);
}
return 0;
}
像这类无限次迭代的题目一定要寻找规律，将规律用某些学习过的变量表示，这样可以方便下面的推导。
注意文中提到的证明方法，可能可以解决一部分字符串循环节问题。