正题

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

---

题目大意

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

1 ≤ n ≤ 1 0 5 , t ≤ 50 , 1 ≤ m ≤ 1 0 5 1\leq n\leq 10^5,t\leq 50,1\leq m\leq 10^5 1≤n≤105,t≤50,1≤m≤105

---

解题思路

对于一个随机的数字 X X X，它的概率生成函数是一个形如
F ( x ) = ∑ i = 0 ∞ P ( X = i ) x i F(x)=\sum_{i=0}^\infty P(X=i)x^i F(x)=i=0∑∞​P(X=i)xi
F ′ ( x ) = ∑ i = 1 ∞ P ( X = i ) i x i − 1 F'(x)=\sum_{i=1}^\infty P(X=i)ix^{i-1} F′(x)=i=1∑∞​P(X=i)ixi−1
不难发现数字 X X X的期望值就是 E ( X ) = F ′ ( 1 ) E(X)=F'(1) E(X)=F′(1)
然后还有一个不知道有啥用的 X X X的方差（大概就是离散程度）
V ( X ) = F ′ ′ ( 1 ) + F ′ ( 1 ) − F ′ ( 1 ) 2 V(X)=F''(1)+F'(1)-F'(1)^2 V(X)=F′′(1)+F′(1)−F′(1)2

这题的话，设两个生成函数， F ( x ) F(x) F(x)表示停止时间 X X X的概率生成函数，还有一个 G ( x ) G(x) G(x)表示没有停止时间的概率（不是概率生成函数），具体地
G ( x ) = ∑ i = 0 ∞ P ( i < X ) x i G(x)=\sum_{i=0}^\infty P(i<X)x^i G(x)=i=0∑∞​P(i<X)xi
然后我们就有两个式子
x G ( x ) + 1 = F ( x ) + G ( x ) xG(x)+1=F(x)+G(x) xG(x)+1=F(x)+G(x)
这个式子的含义很好理解，在还没有结束的序列后面加入一个字符要么结束了要么没结束。
( x n ) m G ( x ) = ∑ i = 1 m ( x n ) m − i b i F ( x ) \left(\frac{x}{n}\right)^mG(x)=\sum_{i=1}^m \left(\frac{x}{n}\right)^{m-i}b_iF(x) (nx​)mG(x)=i=1∑m​(nx​)m−ibi​F(x)
b i b_i bi​表示 i i i是否是串 S S S的一个 b o r d e r border border，这个式子的意思就是说在直接在未结束的 T T T后面插入一个 S S S，此时可能提前结束。

然后这两个式子怎么用呢，我们对第一个式子求导就有
G ( x ) + G ′ ( x ) = F ′ ( x ) + G ′ ( x ) ⇒ F ′ ( x ) = G ( x ) G(x)+G'(x)=F'(x)+G'(x)\Rightarrow F'(x)=G(x) G(x)+G′(x)=F′(x)+G′(x)⇒F′(x)=G(x)
也就是说我们要求的 E ( X ) = F ′ ( 1 ) = G ( 1 ) E(X)=F'(1)=G(1) E(X)=F′(1)=G(1)
然后直接带入第二个式子，因为有 F ( 1 ) = 1 F(1)=1 F(1)=1，所以
( 1 n ) m G ( 1 ) = ∑ i = 1 m ( 1 n ) m − i b i F ( 1 ) \left(\frac{1}{n}\right)^mG(1)=\sum_{i=1}^m \left(\frac{1}{n}\right)^{m-i}b_iF(1) (n1​)mG(1)=i=1∑m​(n1​)m−ibi​F(1)
⇒ G ( 1 ) = ∑ i = 1 m n i b i \Rightarrow G(1)=\sum_{i=1}^mn^ib_i ⇒G(1)=i=1∑m​nibi​
用 K M P KMP KMP求出 b b b数组即可。

时间复杂度 O ( T m ) O(Tm) 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;
}