概率生成函数
(X)是非负整数集上的离散随机变量，那么(X)的概率生成函数为：
(F(z)=B(z^X)=sum_{i=0}^{oo}Pr(X=i)z^i)
基础性质：
- (F(1)=sum_{i=0}^{oo}Pr(X=i)=1)
- 一阶导数是期望(E(X)=F'(1)=sum_{i=0}^{oo}iPr(X=i))
- ……
用概率生成函数解决这类问题的方法：
- 定义一个概率生成函数与辅助函数
- 实际情况找特征列方程
- 代值和求导解出(F'(1))
例题：CSTC2006歌唱王国
题意：
给定一个长度为(L)的序列(A)，每次往(B)序列末尾等概率加入([1,m])里的一个数，求(A)在(B)中出现的期望次数。(L<=1e5)
SOL:
令(f_i)为结束时长度为(i)的概率，其生成函数为(F(x))
令辅助数组(g_i)为到长度为(i)还没有结束的概率，其生成函数为(G(x))
(ans=F'(1))
容易发现：
[F(x)+G(x)=1+G(x)*x
]
[G(x)*(frac{1}{m}x)^L=sum_{i=1}^La_i*F(x)*(frac{1}{m}x)^{L-i}
]
(a_i)表示(A[1,i])是否为(A)的一个(border)，即(A[1,i])是否等于(A[L-i+1,L])，是为1，否为0
将一式求导并代入(x=1)得：
[F'(x)+G'(x)=G(x)+G'(x)*x
]
[F'(1)=G(1)
]
将(x=1)代入二试得：
[G(1)*frac 1{m^L}=sum^L_{i=1}a_i*F(1)*frac{1}{m^{L-i}}
]
[F'(1)=sum^L_{i=1}a_im^i
]
用(kmp)即可(O(L))
#include<bits/stdc++.h>
using namespace std;
inline int read(){
int x=0,f=1;char c=getchar();
while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}
return f==1?x:-x;
}
const int N=1e5+4,mod=1e4;
int n,m,a[N],fail[N],ans,T;
inline int ksm(int x,int r){
int ret=1;
for(int i=0;(1<<i)<=r;i++){
if((r>>i)&1)ret=ret*x%mod;
x=x*x%mod;
}
return ret;
}
inline void solve(){
n=read();
for(int i=1;i<=n;i++)a[i]=read();
for(int i=2,j=0;i<=n;i++){
while(j&&a[j+1]!=a[i])j=fail[j];
if(a[j+1]==a[i])j++;
fail[i]=j;
}
ans=0;
while(n){
ans=(ans+ksm(m,n))%mod;
n=fail[n];
}
for(int i=1000;i>1;i/=10)
if(ans/i)break;
else putchar('0');
cout<<ans<<"
";
}
int main(){
m=read()%mod;/*!*/T=read();
while(T--)solve();
return (0-0);
}
更深入详细请阅读2018国家集训队论文《浅谈生成函数在掷骰子问题上的应用》杨懋龙