AtCoder

分析

设 $T$ 为 $S$ 减去 $S$ 的最长 border 后缀后得到的串。

如果 $|T|$ 是 $|S|$ 的约数，那么操作得到的串依次是
$$
SS\to STST\to STTSTT\to STTTSTTT\to\cdots
$$
因为操作次数高达 $10^{100}$，所以我们可以只看前半部分，即
$$
S\to ST\to STT\to STTT\to\cdots
$$
我们把询问差分成 $[1,r]-[1,l-1]$，那么我们只要求一个前缀中每个字符的出现次数。那么我们只要算一下完整的 $T$ 的个数，然后把不是一个完整的 $T$ 的部分算一下即可。

如果 $|T|$ 不是 $|S|$ 的约数，那么操作得到的串依次是
$$
SS\to STST\to STSSTS\to STSSTSTSST\to\cdots
$$
同样只看前半部分
$$
S\to ST\to STS\to STSST
$$
可以发现，$s_i=s_{i-1}+s_{i-2}$。

那么串长增长的速度是指数级别的，所以我们可以直接暴力地算出前若干个这样的串中每个字符的个数，询问时把 $[1,r]$ 拆成若干个这样的串相接再加上不是一个完整的 $S$ 的部分即可。

// ====================================
//   author: M_sea
//   website: https://m-sea-blog.com/
// ====================================
#include <bits/stdc++.h>
#define file(x) freopen(#x".in","r",stdin); freopen(#x".out","w",stdout)
#define debug(...) fprintf(stderr,__VA_ARGS__)
using namespace std;
typedef long long ll;

ll read() {
    ll X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=200000+10;

int n,lt,lim; char s[N];
int sum[N][26];
ll ans[26],len[100],cnt[100][26];

int nxt[N];
void getnext() {
    for (int i=2,j=0;i<=n;++i) {
        while (j&&s[j+1]!=s[i]) j=nxt[j];
        if (s[j+1]==s[i]) ++j;
        nxt[i]=j;
    }
}

void calc_sp(ll p,int w) {
    if (!p) return;
    for (int i=0;i<26;++i) ans[i]+=w*(p/lt)*sum[lt][i];
    for (int i=0;i<26;++i) ans[i]+=w*sum[p%lt][i];
}

void calc(ll p,int w) {
    if (!p) return;
    for (int i=lim;i;--i) {
        if (p<len[i]) continue;
        p-=len[i];
        for (int j=0;j<26;++j) ans[j]+=w*cnt[i][j];
    }
    for (int i=0;i<26;++i) ans[i]+=w*sum[p][i];
}

int main() {
    scanf("%s",s+1); n=strlen(s+1)>>1;
    ll l=read(),r=read();
    getnext(); lt=n-nxt[n];
    for (int i=1;i<=n;++i) {
        memcpy(sum[i],sum[i-1],sizeof(sum[i]));
        ++sum[i][s[i]-'a'];
    }
    if (n%lt==0) calc_sp(r,1),calc_sp(l-1,-1);
    else {
        len[1]=n,len[2]=n+lt;
        for (int i=0;i<26;++i)
            cnt[1][i]=sum[n][i],cnt[2][i]=sum[n][i]+sum[lt][i];
        for (int i=3;;++i) {
            len[i]=len[i-1]+len[i-2];
            for (int j=0;j<26;++j) cnt[i][j]=cnt[i-1][j]+cnt[i-2][j];
            if (len[i]>1e18) { lim=i; break; }
        }
        calc(r,1),calc(l-1,-1);
    }
    for (int i=0;i<26;++i) printf("%lld ",ans[i]); puts("");
    return 0;
}