正題

題目鏈接:https://www.luogu.com.cn/problem/P4548

---

題目大意

$t$次詢問，給出一個長度為$m$的串$S$和一個空串$T$，每次在$T$后面隨機加入$1～n$的字符，直到$T$中出現$S$為止，求期望次數。

$1\le n\le 10^5,t\le 50,1\le m\le 10^5$

---

解題思路

對于一個隨機的數字$X$，它的概率生成函數是一個形如
$$F(x)=\sum _{i=0}^{\infty }P(X=i)x^i$$
$$F^{\prime }(x)=\sum _{i=1}^{\infty }P(X=i)i{x}^{i?1}$$
不難發現數字$X$的期望值就是$E(X)=F^{\prime }(1)$
然后還有一個不知道有啥用的$X$的方差（大概就是離散程度）
$$V(X)=F^{\prime \prime }(1)+F^{\prime }(1)?F^{\prime }(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)}^{m}G(x)=\sum _{i=1}^m{\left(\frac{x}{n}\right)}^{m?i}{b}_{i}F(x)$$
$b_i$表示$i$是否是串$S$的一個$border$，這個式子的意思就是說在直接在未結束的$T$后面插入一個$S$，此時可能提前結束。

然后這兩個式子怎么用呢，我們對第一個式子求導就有
$$G(x)+G^{\prime }(x)=F^{\prime }(x)+G^{\prime }(x)?F^{\prime }(x)=G(x)$$
也就是說我們要求的$E(X)=F^{\prime }(1)=G(1)$
然后直接帶入第二個式子，因為有$F(1)=1$，所以
$${\left(\frac{1}{n}\right)}^{m}G(1)=\sum _{i=1}^m{\left(\frac{1}{n}\right)}^{m?i}{b}_{i}F(1)$$
$$?G(1)=\sum _{i=1}^m{n}^i{b}_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; }

總結

以上是生活随笔為你收集整理的P4548-[CTSC2006]歌唱王国【概率生成函数,KMP】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。