[luogu4548]歌唱王国

（可以参考hdu4652，因此推导过程比较省略）

类似的定义$f_{i}$和$g_{i}$，同样去插入$len$个字符，但注意到并不是任意一个位置都可以作为结尾，$i+j$可以作为结尾当且仅当$s[0,j)=s[len-j,j)$

令两者生成函数分别为$F(x)$和$G(x)$，则有$G(x)=sum_{iin S}m^{i}frac{F(x)}{x^{i}}$，其中$S={i|s[0,i)=s[len-i,len)}$（根据定义$lenin S$），可以通过kmp或哈希求出

答案即为$G(1)=sum_{xin S}m^{x}$，注意对10000取模以及补充前导0

#include<bits/stdc++.h>
using namespace std;
#define N 100005
#define mod 10000
int n,m,t,ans,a[N],mi[N],nex[N];
int main(){
    scanf("%d%d",&m,&t);
    mi[0]=1;
    for(int i=1;i<N-4;i++)mi[i]=1LL*mi[i-1]*m%mod;
    while (t--){
        scanf("%d",&n);
        for(int i=1;i<=n;i++)scanf("%d",&a[i]);
        nex[0]=nex[1]=0;
        for(int i=2,j=0;i<=n;i++){
            while ((j)&&(a[i]!=a[j+1]))j=nex[j];
            if (a[i]==a[j+1])j++;
            nex[i]=j;
        }
        ans=0;
        for(int i=n;i;i=nex[i])ans=(ans+mi[i])%mod;
        if (ans<10)printf("0");
        if (ans<100)printf("0");
        if (ans<1000)printf("0");
        printf("%d
",ans);
    }
}