这题(mathrm{YMD})去年就讲了,然而我今年才做(捂脸)
考虑生成函数,设(f_i)表示最终串长为(i)的概率,其概率生成函数为(F(x)=sum f_ix^i),设(g_i)表示做到长度为(i)没结束的概率,其概率生成函数为(G(x)=sum g_ix^i),那我们要求的就是(F'(1))
考虑他们之间的关系,首先如果在一个没有结束的串后接一个字符,那么这个串可能结束也可能没结束,可以得到(F(x)+G(x)=xG(x)+1),两边对(x)求导并代入(x=1)得到(F'(1)=G(1))
然后继续考虑如果在一个没有结束的串直接加入给定的串,那么一定会结束,只不过有可能在没加完的时候就结束了,假设加入了(i)个字符结束,那么说明原串有一个长度为(i)的(border),设(a_i)表示原串是否有长度为(i)的(border),那么可以得到(G(x)(frac{x}{n})^m=sum_{i=1}^{m}a_iF(x)(frac{x}{n})^{m-i}),化简并代入(x=1)得到(F'(1)=G(1)=sum_{i=1}^{m}a_in^i),然后kmp即可
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<vector>
#include<cmath>
#include<ctime>
#include<queue>
#include<map>
#include<set>
#define LL long long
#define db double
using namespace std;
const int N=1e5+10,mod=10000;
int rd()
{
int x=0,w=1;char ch=0;
while(ch<'0'||ch>'9'){if(ch=='-') w=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
return x*w;
}
int n,m,a[N],nxt[N],p[N],ans;
int main()
{
n=rd();
p[0]=1;
for(int i=1;i<=N-10;++i) p[i]=1ll*p[i-1]*n%mod;
int T=rd();
while(T--)
{
m=rd();
for(int i=1;i<=m;++i) a[i]=rd();
nxt[1]=nxt[2]=1;
for(int i=2,j=1;i<=m;++i)
{
while(j>1&&a[i]!=a[j]) j=nxt[j];
nxt[i+1]=a[i]==a[j]?++j:1;
}
ans=0;
int x=m+1;
while(x>1) ans=(ans+p[x-1])%mod,x=nxt[x];
if(ans<1000) putchar('0');
if(ans<100) putchar('0');
if(ans<10) putchar('0');
printf("%d
",ans);
}
return 0;
}
实测这题算答案不取模90'(我也不知道为什么)