[atARC077F]SS

(以下字符串下标从0开始,并定义$2s=s+s$)

考虑$f(S)$,即令$l=\max_{2i<|S|且S[0,i)=S[|S|-i,|S|)]}i$,则$f(S)=S+S[l,|S|-l)$

由于次数足够多,先做一次$S=f(S)$不影响答案,因此假设原串为$2S$(这个$S$不同于初始的$S$)

考虑$f(2S)$,类似的即令$l=\max_{i<|S|且S[0,i)=S[|S|-i,|S|)}i$(最长非自身的border),则$f(2S)=2(S+S[0,|S|-l))$

构造一个新的函数$g(S)=S+S[0,|S|-l)$,不难归纳得到$f_{k}(2S)=2g_{k}(S)$,且由于$|g_{10^{100}}(S)|\ge 10^{18}$,因此不需要考虑2倍,只需要求$g_{10^{100}}(S)$

令$T=S[0,|S|-l)$,那么$g_{2}(S)=g(S+T)$,记$S'=S+T$,即求$S'$时的$l$

根据$l$的定义可得$S[0,|S|-|T|)=S[|T|,|S|)$,代入到每一个字符即$\forall 0\le i<|S|-|T|,S_{i}=S_{i+|T|}$

若$|T|$为$|S|$的约数,由此不难得到$S=TT...T$,否则$S=TT...TP$(其中$P$为$T$的前缀),之后$l$所对应的$S$的border即为去掉第一个$T$后的串

对于第一种情况有$l=|S|$,可得$S'[0,l)=S[|S'|-l,|S'|)=S$,同时若有更大的$l'$,可得$TT...TP=PTT...T$(其中$P=T[0,l'-|S|)$),那么将两边同时去掉串首的$T$即得到$S$一个更长的border

(关于第二个为什么以$P$开头:首先由于其与$T$相同,必然是$T$的前缀,长度又等于$P$,根据前缀的唯一性即为$P$)

在此基础上继续归纳下去,即得$g_{k}(S)=g_{k-1}(S)+T=STT...T$(共$k$个$T$),简单计算一下即可

对于第二种情况有$l=|T|$,可得$S'[0,l)=S'[|S'|-l,|S'|)=T$,同时若存在更大的$l'$,则考虑两者相同的最后$|T|$个字符,前者是$T$的一个循环,后者即为$T$

假设以$T_{i}$开头,即得到$T_{j}=T_{(j+i)mod\ |T|}$,不难得到$T$必然是一个串循环若干次,这与KMP的性质矛盾,因此不存在更大的$l'$

接下来同样归纳,可得$g_{k+1}(S)=g_{k}(S)+g_{k-1}(S)$,考虑如何处理:

先将其差分,求长为$l$的前缀的各个字母数量,而由于$|g_{0}(S)|,|g_{1}(S)|\ge 1$,不难发现其在100项时长度一定超过$10^{18}$,找到最后一个$g_{k}(S)\le l$,之后统计$g_{k}(S)$的字母数量并递归$l-g_{k}(S)$即可

这样的时间复杂度最优可以达到$o(|S|+|\alpha|m)$(其中$m=100$)

[atARC077F]SS
 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 #define N 200005
 4 #define M 105
 5 #define ll long long
 6 int n,m,nex[N];
 7 ll l,r,len[M],sum[M][31],ans[31];
 8 char s[N];
 9 void calc1(ll k,int p){
10     if (k<n)
11         for(int i=0;i<k;i++)ans[s[i]-'a']+=p;
12     else{
13         for(int i=0;i<n;i++)ans[s[i]-'a']+=p;
14         k-=n;
15         for(int i=0;i<nex[n];i++)ans[s[i]-'a']+=p*k/nex[n];
16         for(int i=0;i<k%nex[n];i++)ans[s[i]-'a']+=p;
17     }
18 }
19 void calc2(ll k,int m,int p){
20     if (k<=n){
21         for(int i=0;i<k;i++)ans[s[i]-'a']+=p;
22         return;
23     }
24     while (len[m]>k)m--;
25     for(int i=0;i<26;i++)ans[i]+=sum[m][i]*p;
26     calc2(k-len[m],m,p);
27 }
28 int main(){
29     scanf("%s%lld%lld",s,&l,&r);
30     n=strlen(s);
31     nex[0]=nex[1]=0;
32     for(int i=1,j=0;i<n;i++){
33         while ((j)&&(s[j]!=s[i]))j=nex[j];
34         if (s[j]==s[i])j++;
35         nex[i+1]=j;
36     }
37     int nn=n;
38     while (2*n>=nn)n=nex[n];
39     n=nn-n;
40     nex[n]=n-nex[n];
41     if (n%nex[n]==0){
42         calc1(r,1);
43         calc1(l-1,-1);
44         for(int i=0;i<26;i++)printf("%lld ",ans[i]);
45         return 0;
46     }
47     len[0]=n;
48     for(int i=0;i<n;i++)sum[0][s[i]-'a']++;
49     len[1]=n+nex[n];
50     for(int i=0;i<n;i++)sum[1][s[i]-'a']++;
51     for(int i=0;i<nex[n];i++)sum[1][s[i]-'a']++;
52     m=1;
53     while (len[m]<r){
54         m++;
55         len[m]=len[m-1]+len[m-2];
56         for(int i=0;i<26;i++)sum[m][i]=sum[m-1][i]+sum[m-2][i];
57     }
58     calc2(r,m,1);
59     calc2(l-1,m,-1);
60     for(int i=0;i<26;i++)printf("%lld ",ans[i]);
61 } 
View Code

 

上一篇:链表操作函数集合(C++)


下一篇:LRU缓存