【ARC077F】SS kmp+打表找规律

Description

如果某个串可以由两个一样的串前后连接得到，我们就称之为“偶串”。比如说“xyzxyz”和“aaaaaa”是偶串，而“ababab”和“xyzxy”则不是偶串。

对于一个非空串SS，我们定义f(S)f(S)是在SS后面添加一些字符得到的最短偶串。比如f(f('abaaba')=)='abaababaab'。容易证明，对于一个非空串SS，f(S)f(S)是唯一的

现在给定一个由小写英文字母构成的偶串SS，你需要求出f10100(S)f10100(S)，并统计计算结果的第ll个字符到第rr个字符中，每个字母出现了多少次

其中，f10100(S)f10100(S)是指f(f(f(...f(S)...)))f(f(f(...f(S)...)))，式子中共有1010010100个ff

Input

第一行输入串SS

第二行两个数l,rl,r

Output

对于每个字母，输出一个数字表示答案，两个数字之间应有一个空格

Sample Input

Sample #1

abaaba

6 10

Sample #2

xx

1 1000000000000000000

Sample #3

vgxgpuamkvgxgvgxgpuamkvgxg

1 1000000000000000000

Sample Output

Sample #1

3 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

Sample #2

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1000000000000000000 0 0

Sample #3

87167725689669676 0 0 0 0 0 282080685775825810 0 0 0 87167725689669676 0 87167725689669676 0 0 87167725689669676 0 0 0 0 87167725689669676 141040342887912905 0 141040342887912905 0 0

HINT

2≤|S|≤2×10^5

1≤l≤r≤10^18

本题采用subtask。

存在30%的数据，满足|S|≤20
存在50%的数据，满足|S|≤200

Sol

对于一个串，我们设为“SS”，它的最短周期为“T"（也就是S由T循环组成且最后一个T可以不完整），以”abaaba“举例，我们发现：

S->aba T->ab

aba|aba->abaab|abaab->abaababa|abaababa->abaababaabaab|abaababaabaab

即S|S->ST|ST->STS|STS->STSTS|STSTS。

这是一个斐波那契数列的形式，我们可以对每种字母单独求，因为fib数列到80就会爆1e18，所以时间复杂度不会爆炸，具体地，我们统计每种字母在S中出现次数的前缀和，然后递归计算，把l-1或者r分成很多fib数列的形式，若不满|S|，则直接返回。

Code

#include <bits/stdc++.h>

#define ll long long

using namespace std;

char s[200005];ll len,slen,tlen,sum[30][200005],nex[200005],l,r;

ll solve(ll now,int n)

{

	if(now<=len) return sum[n][now];

	ll f1=sum[n][slen],f2=sum[n][len],l1=slen,l2=len,tf,tl;

	while(l1+l2<now) tf=f2,tl=l2,f2+=f1,l2+=l1,f1=tf,l1=tl;

	return f2+solve(now-l2,n);

}

main()

{

	scanf("%s%lld%lld",s+1,&l,&r);len=strlen(s+1)/2;

	for(int i=2,j=0;i<=len;i++)

	{

		while(j&&s[i]!=s[j+1]) j=nex[j];

		if(s[j+1]==s[i]) nex[i]=++j;

	}

	slen=len-nex[len];

	for(int i=0;i<26;i++) for(int j=1;j<=len;j++)

	{

		sum[i][j]=sum[i][j-1];

		if(s[j]-'a'==i) sum[i][j]++;

	}

	for(int i=0;i<26;i++) printf("%lld ",solve(r,i)-solve(l-1,i));

}

巴特西