[Str记录]AT2651 [ARC077D] SS
command_block
2021-05-01 13:40:19
**题意** ： 对于非空串 $S$，定义 $f(S)$ 是在 $S$ 后面添加一些（至少一个）字符得到的最短平方串。
现在给出平方串 $S$ ，记 $T=f(f(f(...f(S))))$ （可以认为有无穷多个 $f$）
给出 $l,r$ ，询问 $T[l,r]$ 中各个字符的出现次数。（字符集为小写英文字母）
$|S|\leq 2\times 10^5,\ l,r\leq 10^{18}$ ，时限$\texttt{2s}$。
------------
考虑给出 $S$ 如何求解 $f(SS)$。
设 $S$ 的周期集合为 ${\rm per}(S)$ ，求出 $\min\limits_{p\in{\rm per(SS)},p>|S|}p$ ，即大于一半的最小循环节。
将 $SS$ 补成两个 $p$ 即可。
记 $S$ 的最短循环节前缀 为 $T$ ，$p$ 所对应的串即为 $ST$。记 $g(S)$ 为 $S$ 的最小循环节前缀。
也即 ： $SS\rightarrow Sg(S)Sg(S)\times 2$。
由于会重复无限次操作，我们只需考虑前半部分，即 $S\rightarrow Sg(S)$。
观察这一操作有何规律，能发现 ：
- 当 $g(S)$ 为整循环节，$Sg(S)$ 的最小循环节与 $S$ 的相同，且也是整循环节。
记 $G=g(S)$ ，操作的效果为 ：
$$S\rightarrow SG\rightarrow SG^2 \rightarrow SG^3...$$
容易在 $O(\Sigma)$ 内求解。
- 当 $g(S)$ 不是整循环节， $Sg(S)$ 的最小循环节为 $S$ ，且也不是整循环节。
**证明** ： 假设 $T=Sg(S)$ 有小于 $|S|$ 的周期 $p$ 。
注意到 $p$ 同时也是 $S$ 的周期，则有 $|g(S)|\leq p$。
考虑 $i\in \big[|S|+1,|T|\big]$ ，由于 $g(S)$ 是 $S$ 的前缀，又有 $T[i]=T[i-|S|]$。
根据周期有 $T[i]=T[i-p]$ ，由于 $|g(S)|\leq p\Rightarrow i-p\leq |S|$ ，此时 $T[i-p]$ 已经是 $S$ 的一部分。
根据 $S$ 的周期 $g(S)$ ，又有 $i-|S|=i-p\pmod{|g(s)|}$ 即 $|S|=p\pmod{|g(S)|}$。
那么，由于 $p<|S|$ ，有 $p\leq |S|-|g(S)|$。
根据弱周期引理，$S$ 有新的周期 $\gcd(|g(S)|,p)$。
由于 $g(S)$ 已经是最小周期，故 $p$ 一定是 $g(S)$ 的倍数。（否则会得到更小的周期）
注意到 $p=|S|\neq 0\pmod{|g(S)|}$ ，矛盾。
记 $G=g(S)$ ，操作的效果为 ：
$$S\rightarrow SG\rightarrow SGS \rightarrow SGSSG...$$
（记第 $i$ 此操作后的串为 $F_i$ ，有 $F_0=S,F_1=SG,F_i=F_{i-1}+F_{i-2}$）
串的长度是指数增加的，不难做到 $O\big(|\Sigma|{\rm poly}(\log r)\big)$。
还需用一次 $O(|S|)$ 的 $\rm KMP$ 求出 $G$。
```cpp
#include<algorithm>
#include<cstring>
#include<cstdio>
#define ll long long
#define MaxN 200500
using namespace std;
const int mod=998244353;
char s[MaxN];
ll ans[30],c[105][30],len[105];
void dfs(ll r)
{
if (r<=len[0]){
for (int i=1;i<=r;i++)
ans[s[i]]++;
return ;
}
int k=0;while(len[k+1]<=r)k++;
for (int i=0;i<26;i++)ans[i]+=c[k][i];
dfs(r-len[k]);
}
int n,p;
void calc(ll r)
{
if (r<=n+p){
for (int i=1;i<=min(r,(ll)n);i++)ans[s[i]]++;
for (int i=1;i<=r-n;i++)ans[s[i]]++;
return ;
}
if (n%p==0){
for (int i=1;i<=n;i++)ans[s[i]]++;
r-=n;
for (int i=1;i<=p;i++)ans[s[i]]+=(r-i+p)/p;
}else dfs(r);
}
int f[MaxN];
int main()
{
scanf("%s",s+1);
n=strlen(s+1)/2;
for (int i=1;i<=n;i++)s[i]-='a';
for (int i=2;i<=n;i++){
while(p&&s[p+1]!=s[i])p=f[p];
if (s[p+1]==s[i])p++;
f[i]=p;
}
p=n-f[n];
ll l,r;scanf("%lld%lld",&l,&r);
for (int i=1;i<=n;i++)c[0][s[i]]++;
for (int i=1;i<=n;i++)c[1][s[i]]+=(1+(i<=p));
len[0]=n;len[1]=n+p;
int k=2;
while(1){
len[k]=len[k-1]+len[k-2];
for (int i=0;i<26;i++)
c[k][i]=c[k-1][i]+c[k-2][i];
if (len[k]>r)break;
k++;
}
calc(l-1);
for (int i=0;i<26;i++)ans[i]*=-1;
calc(r);
for (int i=0;i<26;i++)
printf("%lld ",ans[i]);puts("");
return 0;
}
```