传送门

被一个ARC题虐爆了。。。

看到题后随手猜了个结论,感觉大概是对的。结果写完之后过不了大样例。。。然后发现结论是假的,仅仅一个字母a就能出现反例。。。看来我这个猜结论的能力还得提高一个。

然后就不会做了啊。。。看了题解,发现题解也是猜结论??给了个结论最后连证明都没给,只给了个证明框架,结果我到现在都还不会证。。。日文版题解甚至连证明框架都没给。。。?

结论就是对任意字符串$S$,如果$T$是$S$的最短周期且$|T|$不能整除$|S|$($T$是$S$的周期当且仅当$S$是无限个$T$拼在一起组成的串的前缀),那么$ST$的最短周期是$S$。

考虑一直把$S$赋值成$f(S)$,最后能得到什么。每次$S:=f(S)$的时候,其实就是把$S$末尾删掉一个最长border(这个border长度不能大于等于一半),并把$S$复制一份接在后面。

当$S$已经是一个重复串的时候,记$S=AA$,这时$S$的最长的短于一半的border其实就是$A$的最长border。那么再记$B$为$A$在末尾后删掉自己最长border(这里没有长度限制)后形成的串,则$f(S)=ABAB$。根据border和周期的对应关系,可以知道$B$其实就是$A$的最短周期。

既然$S$一直是重复串,那么其实只用考虑前半段就行了。记$g(A)=AB$,其中$B$是$A$的最短周期,那么根据之前的那个结论,只要$|B|\nmid|A|$,那么$g(AB)=ABA$。当$|B|$整除$|A|$的时候,由于接下来都是$B$一直循环,所以用上面那种方法算出来结果是一样的。

这时发现$g^k(S)=g^{k-1}(S)+g^{k-2}(S)$,所以直接类似斐波那契数列那样乱搞就行啦。

以后做这种跟border有关的题目,还是多往周期那边想一下比较好。。。

代码:

#include <cstdio>
#include <cstring>
#define MAXN 1000010
#define LL long long

int n;
char str[MAXN];
int nxt[MAXN];
int s[26][MAXN];
LL L,R,S,T;

void gaoNext(){
    nxt[1]=0;
    for(int i=2,j=1;i<=n;i++,j++){
        while(j && str[i]!=str[j]){
            if(j==1) j=0;
            else j=nxt[j-1]+1;
        }
        nxt[i]=j;
    }
}

void gaoS(){
    for(int i=0;i<26;i++){
        s[i][0]=0;
        for(int j=1;j<=n;j++)
            s[i][j]=s[i][j-1]+((str[j]=='a'+i)?1:0);
    }
}

void pre_gao(){
    gaoNext();
    int temp=n;
    while(temp*2>=n) temp=nxt[temp];
    n-=temp;
}

LL getS(int ch,LL len){
    if(len<=n) return s[ch][len];
    LL l1=T,l2=S;
    LL s1=s[ch][l1],s2=s[ch][l2];
    while(l1+l2<=len){
        LL l3=l1+l2,s3=s1+s2;
        l1=l2; l2=l3;
        s1=s2; s2=s3;
    }
    return s2+getS(ch,len-l2);
}

int main(){
#ifdef DEBUG
    freopen("F.in","r",stdin);
#endif
    scanf("%s",str+1);
    n=strlen(str+1);
    scanf("%lld%lld",&L,&R);
    pre_gao();
    gaoS();
    S=n; T=n-nxt[n];
    for(int i=0;i<26;i++)
        printf("%lld ",getS(i,R)-getS(i,L-1));
    return 0;
}