题目分析

设生成函数 $F(x)$，$f _ i$表示歌唱序列长度为 $i$的概率。

显然 $F(1)=1$。

而期望就是 $\sum_{i=0}^{ \inf } F(i)i$，也就是 $F'(1)$

设生产函数 $G(x)$，$g _ i$表示你唱了 $i$声，并且还没有结束，还能继续唱的概率。

设字符集大小为 $m$，长老名字长度为 $L$，$a _ i$表示长老名字字符 $S[1…i]$是否等于 $S[L-i+1,L]$。

则有两个奥妙重重的式子：

1. $1+xG(x)=G(x)+F(x)$：左边相当于还没结束时再唱一声，右边为唱 $i$声结束了和未结束的概率之和。
2. $G(x)(\frac{1}{m}x) ^ L=\sum_{i=1}^n a _ i F(x)(\frac{1}{m}x) ^ {L-i}$：相当于若还没结束，再唱出一个长老的名字就相当于结束了。但还有唱名字唱到一半就结束了的情况，也要计算。

由第一个式子，$F'(1)+G'(1)=G(1)+G'(1)$，即 $F'(1)=G(1)$

由第二个式子，$G(1)=\sum_{i=1}^n a _ i F(1) m ^ i$，因为 $F(1)=1$，所以 $G(1)=\sum_{i=1}^n a _ i m ^ i$

用 KMP 算出 $a$即可。

代码

#include<bits/stdc++.h>
using namespace std;
#define RI register int
int read() {
    int q=0;char ch=' ';
    while(ch<'0'||ch>'9') ch=getchar();
    while(ch>='0'&&ch<='9') q=q*10+ch-'0',ch=getchar();
    return q;
}
const int N=100005,mod=10000;
int m,T,L,ans,S[N],a[N],ne[N];

void KMP() {
    ne[1]=0;
    for(RI i=2;i<=L;++i) {
        int j=ne[i-1];
        while(1) {
            if(S[j+1]==S[i]) {ne[i]=j+1;break;}
            if(!j) {ne[i]=0;break;}
            j=ne[j];
        }
    }
    for(RI i=1;i<=L;++i) a[i]=0;
    int x=L;while(x) a[x]=1,x=ne[x];
}
int main()
{
    m=read()%mod,T=read();
    while(T--) {
        L=read();
        for(RI i=1;i<=L;++i) S[i]=read();
        KMP();
        ans=0;for(RI i=1,mm=m;i<=L;++i,mm=mm*m%mod) ans=(ans+a[i]*mm%mod)%mod;
        printf("%d%d%d%d\n",ans/1000,(ans/100)%10,(ans/10)%10,ans%10);
    }
    return 0;
}