原题链接
https://arc077.contest.atcoder.jp/tasks/arc077_d
Description
定义偶串为这个字符串前一半和后一半相同(abadabad)
定义函数f(S)表示在S这个字符串后加上最短的串（不能为空），加上以后变成偶串
加完以后得到的串
给出S
求小写字母a~z分别在 f(f(f(….f(S)…))) 的串中[L,R]这个区间内出现了多少次
保证一开始S为偶串
其中嵌套了10^100次
L，R<=10^18
Solution
可以发现既然加上最短的串，那么我们要找到它的最长的非它本身的border（即kmp的next[n]）
就是找到它的最短周期
令S=RR，T为R的最短周期长度的R的前缀，P为R的最长border
那么R=TP
可以发现转移是这样的
若|T|整除|R|
那么|R|就是由若干个|T|拼接而成
那么RR->RTRT->RTTRTT…..
这种情况很好处理
否则是
RR->RTRT->RTRRTR->…
f(RR)=RTRT
f(RTRT)=RTRRTR
…
理解了前两个，后面可以迭代下去
f(RR)=RTRT为什么？
RR=RTP
因为P已经是R的最长border，不可能继续延长
并且根据border的定义，P既是R的前缀又是R的后缀
那么最短的前半段一定是RT
就OK了
那为什么f(RTRT)=RTRRTR
同上面的可以自己分析一下
我们只考虑前半串的话
就是这样的
R->RT->RTR->RTRRT->…
是斐波那契的形式
最终我们得出一个结论
定义F(n)为原串变换n次得到的串的前一半
规定F(1)=R,F(0)=T
那么F(n)=F(n-1)+F(n-2) （此处+为字符串的拼接）
并且F(n)的最短周期就是F(n-1)
这样以后就很简单了
考虑如何计算答案
不妨分成[1~L-1]和[1~R]求解
只考虑R
每个字母分别考虑，一直迭代到最后一个长度小于等于R的项，设为id
如果刚刚好对上就直接返回答案
如果还有剩下一点点，再迭代一次又多了
然而我们发现F(id+1)=F(id)+F(id-1)
而F(id-1)又是F(id)的前缀
所以是完全一样的，要求len[id]~R 相当于求1~R-len[id]
斐波那契大约80次就超过10^18了，所以10^100是完全没用的
直接暴力迭代都可以
回到之前，其实我们并不需要特殊考虑第一种整除的情况
因为既然|R|是由|T|拼接而成，那么在后面多次填T和填一次R是一样的
并且是操作无限次，那么和第二种情况并没有区别
Code
#include <cstdio>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define fod(i,a,b) for(int i=a;i>=b;i--)
#define LL long long
#define N 200005
using namespace std;
int nx[N],n;
LL a[200][26],le[200],l,r;
char ch[N];
void kmp()
{
int j=0;
fo(i,2,n/2)
{
while(j&&ch[j+1]!=ch[i]) j=nx[j];
if(ch[j+1]==ch[i]) j++;
nx[i]=j;
}
}
LL calc(int c,LL w)
{
int id=1;
if(le[id]>=w)
{
int s=0;
fo(i,1,w)
{
if(ch[i]-'a'==c) s++;
}
return s;
}
while(w>=le[id])
{
a[id+1][c]=a[id][c]+a[id-1][c];
le[id+1]=le[id]+le[id-1];
id++;
}
LL s=a[id-1][c];
if(w==le[id-1]) return s;
else return s+calc(c,w-le[id-1]);
}
int main()
{
scanf("%s",ch+1);
n=strlen(ch+1);
kmp();
cin>>l>>r;
le[0]=n/2-nx[n/2];
le[1]=n/2;
fo(i,1,n/2)
{
a[1][ch[i]-'a']++;
if(i<=le[0]) a[0][ch[i]-'a']++;
}
fo(i,0,25) printf("%lld ",calc(i,r)-calc(i,l-1));
}