正题

题目链接:https://www.luogu.com.cn/problem/P4548

题目大意

\(t\)次询问，给出一个长度为\(m\)的串\(S\)和一个空串\(T\)，每次在\(T\)后面随机加入\(1\sim n\)的字符，直到\(T\)中出现\(S\)为止，求期望次数。

\(1\leq n\leq 10^5,t\leq 50,1\leq m\leq 10^5\)

解题思路

对于一个随机的数字\(X\)，它的概率生成函数是一个形如

\[F(x)=\sum_{i=0}^\infty P(X=i)x^i
\]\[F'(x)=\sum_{i=1}^\infty P(X=i)ix^{i-1}
\]

不难发现数字\(X\)的期望值就是\(E(X)=F'(1)\)

然后还有一个不知道有啥用的\(X\)的方差（大概就是离散程度）

\[V(X)=F”(1)+F'(1)-F'(1)^2
\]

这题的话，设两个生成函数，\(F(x)\)表示停止时间\(X\)的概率生成函数，还有一个\(G(x)\)表示没有停止时间的概率（不是概率生成函数），具体地

\[G(x)=\sum_{i=0}^\infty P(i<X)x^i
\]

然后我们就有两个式子

\[xG(x)+1=F(x)+G(x)
\]

这个式子的含义很好理解，在还没有结束的序列后面加入一个字符要么结束了要么没结束。

\[\left(\frac{x}{n}\right)^mG(x)=\sum_{i=1}^m \left(\frac{x}{n}\right)^{m-i}b_iF(x)
\]

\(b_i\)表示\(i\)是否是串\(S\)的一个\(border\)，这个式子的意思就是说在直接在未结束的\(T\)后面插入一个\(S\)，此时可能提前结束。

然后这两个式子怎么用呢，我们对第一个式子求导就有

\[G(x)+G'(x)=F'(x)+G'(x)\Rightarrow F'(x)=G(x)
\]

也就是说我们要求的\(E(X)=F'(1)=G(1)\)

然后直接带入第二个式子，因为有\(F(1)=1\)，所以

\[\left(\frac{1}{n}\right)^mG(1)=\sum_{i=1}^m \left(\frac{1}{n}\right)^{m-i}b_iF(1)
\]\[\Rightarrow G(1)=\sum_{i=1}^mn^ib_i
\]

用\(KMP\)求出\(b\)数组即可。

时间复杂度\(O(Tm)\)

code

#include<cstdio>
#include<cstring>
#include<algorithm>
#define ll long long
using namespace std;
const ll N=1e5+10,P=1e4;
ll T,m,n,pw[N],a[N],nxt[N];
signed main()
{
scanf("%lld%lld",&m,&T);pw[0]=1;
for(ll i=1;i<N;i++)pw[i]=pw[i-1]*m%P;
while(T--){
scanf("%lld",&n);ll ans=0;
for(ll i=1;i<=n;i++)
scanf("%lld",&a[i]);
for(ll i=2,j=0;i<=n;i++){
while(j&&a[j+1]!=a[i])j=nxt[j];
j+=(a[j+1]==a[i]);nxt[i]=j;
}
for(ll i=n;i;i=nxt[i])
(ans+=pw[i])%=P;
printf("%04lld\n",ans);
}
return 0;
}