arc077f

题意：定义一个偶串为一个可写为一个字符串复制两次的字符串。S为一个偶串，定义f(S)为在S后加最少的字符（大于等于1个）使S成为的偶串。

设f(SS)=STST，g(S)=ST。则T为S最小的周期。
$$g(ST)=STT(|T| \\mid |S|) $$
$$g(ST)=STS(|T| \\nmid |S|)$$

#include <bits/stdc++.h>
using namespace std;
const int N=210000;
#define ll long long
char s[N];
ll L,R;
int nex[N];
ll len[210];
struct node
{
    ll a[26];
    void init(int x)
    {
        for(int i=1;i<=x;i++)
            a[s[i]-'a']++;
    }
    friend node operator + (const node &r1,const node &r2)
    {
        node ret;
        for(int i=0;i<26;i++)
            ret.a[i]=r1.a[i]+r2.a[i];
        return ret;
    }
    friend node operator - (const node &r1,const node &r2)
    {
        node ret;
        for(int i=0;i<26;i++)
            ret.a[i]=r1.a[i]-r2.a[i];
        return ret;
    }
    void print()
    {
        for(int i=0;i<26;i++)
            printf("%lld ",a[i]);
        puts("");
    }
}v[210];
node calc(ll x)
{
    int p;
    for(p=1;;p++)
        if(len[p]>=x)break;
    node ret,t;
    memset(&ret,0,sizeof(ret));
    memset(&t,0,sizeof(t));
    for(;p>=1;p--)
        if(len[p]<=x)
        {
            ret=ret+v[p];
            x-=len[p];
        }
    t.init(x);
    ret=ret+t;
    return ret;
}
int main()
{
    //freopen("tt.in","r",stdin);
    scanf("%s%lld%lld",s+1,&L,&R);
    len[2]=strlen(s+1)/2;
    nex[1]=0;
    for(int i=2,j=0;i<=len[2];i++)
    {
        while(j&&s[j+1]!=s[i])
            j=nex[j];
        if(s[j+1]==s[i])j++;
        nex[i]=j;
    }
    len[1]=len[2]-nex[len[2]];
    v[1].init(len[1]);
    v[2].init(len[2]);
    for(int i=3;;i++)
    {
        len[i]=len[i-1]+len[i-2];
        v[i]=v[i-1]+v[i-2];
        if(len[i]>=R)break;
    }
    (calc(R)-calc(L-1)).print();
    return 0;
}