洛谷 P4548 - [CTSC2006]歌唱王国(概率生成函数)

洛谷题面传送门

PGF 入门好题。

首先介绍一下 PGF 的基本概念。对于随机变量 \(X\),满足 \(X\) 的取值总是非负整数,我们即 \(P(v)\) 表示 \(X=v\) 的概率,那么我们定义 \(X\) 的概率生成函数为 \(F(x)=\sum\limits_{n\ge 0}P(n)x^n\)。较一般的生成函数有所不同的是,对于概率生成函数 \(F(1)=1\) 必然成立,因为 \(X\) 取遍所有值的概率之和为 \(1\)。此外,\(X\) 的期望 \(E(X)\) 也可表示为 \(\sum\limits_{n\ge 0}P(n)·n=F'(1)\),同理 \(X\) 的方差 variant 也可被表示为 \(F''(1)+F'(1)-F'(1)^2\),这个可以由方差基本公式 \(E(X^2)-E(X)^2\) 推得。

接下来考虑这道题。我们设 \(P(x)\) 为刚好唱了 \(x\) 秒的概率,\(Q(x)\) 为唱了至少 \(x+1\) 秒的概率,再记 \(F(x),G(x)\) 分别为 \(P(x),Q(x)\) 的 PGF,那么考虑 \(F,G\) 之间有什么联系,首先:

\[P(x)+Q(x)=P(x-1)(x\ge 1) \]

这是因为至少唱 \(x\) 秒的概率就是恰好 \(x\) 秒的概率加上至少 \(x+1\) 秒的概率。

写成 PGF 的形式就是

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

我们再从酋长的名字 \(a\) 的角度列式子。我们考虑一个时刻 \(t\),如果唱了 \(t\) 秒后还没有唱出酋长的名字,并且在接下来 \(len\) 秒后刚好唱出了酋长的名字,那么这样的概率就是 \(Q(x)·\dfrac{1}{n^{len}}\),再考虑将这个概率表示成 \(P\) 的形式,我们考虑什么时第一次唱出酋长的名字,我们假设在时刻 \(t+t'\),显然 \(t'\in[1,len]\),那么这样的概率就是 \(P(t+t')·\dfrac{1}{n^{len-t'}}\),但是一个 \(t'\) 不一定符合条件。不难发现由于我们钦定 \([t+1,t+len]\) 唱出的部分刚好是酋长的名字,而由于我们钦定 \(t+t'\) 时刻刚好唱出酋长的名字,因此必须有 \(a_i=a_{t-t'+i}\),也就是 \(a\) 存在长度为 \(t'\) 的 border。如果我们设 \(b_i\) 表示 \(a\) 是否存在长度 \(i\) 的 border,那么

\[Q(x)·\dfrac{1}{n^{len}}=\sum\limits_{t'=1}^{len}b_{t'}·P(t+t')·\dfrac{1}{n^{len-t'}} \]

写成 PGF 的形式就是

\[G(x)·(\dfrac{1}{n}x)^{len}=\sum\limits_{t'=1}^{len}b_{t'}·F(x)·(\dfrac{1}{n}x)^{len-t'} \]

考虑将两个式子结合起来。对记一个式子求导可得:

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

取 \(x=1\) 可得:

\[E(x)=F'(1)=G(1) \]

也就是说答案等于 \(G(1)\)。

再将答案代入第二个式子:

\[G(1)·\dfrac{1}{n^{len}}=\sum\limits_{t'=1}^{len}b_{t'}·F(1)·\dfrac{1}{n^{len-t'}} \]

再结合 \(F(1)=1\) 可得:

\[E(x)=\sum\limits_{i=1}^{len}b_i·n^{i} \]

哈希/KMP 求 border 即可线性求解答案。

const int MAXN=1e5;
const int BS=333337;
const int HMOD=1004535809;
const int MOD=10000;
void print(int x){
	static int d[6];int len=0;
	while(x) d[len++]=x%10,x/=10;
	while(len<4) d[len++]=0;
	for(int i=3;~i;i--) printf("%d",d[i]);
	printf("\n");
}
int n,qu,len,a[MAXN+5],pre[MAXN+5],suf[MAXN+5],pw[MAXN+5],pwn[MAXN+5];
void solve(){
	scanf("%d",&len);for(int i=1;i<=len;i++) scanf("%d",&a[i]);
	for(int i=1;i<=len;i++) pre[i]=(pre[i-1]+1ll*a[i]*pw[i-1])%HMOD;
	suf[len+1]=0;for(int i=len;i;i--) suf[i]=(1ll*suf[i+1]*BS+a[i])%HMOD;
	int res=0;for(int i=1;i<=len;i++) if(pre[i]==suf[len-i+1]) res=(res+pwn[i])%MOD;
	print(res);
}
int main(){
	int qu;scanf("%d%d",&n,&qu);
	for(int i=(pwn[0]=1);i<=MAXN;i++) pwn[i]=1ll*pwn[i-1]*n%MOD;
	for(int i=(pw[0]=1);i<=MAXN;i++) pw[i]=1ll*pw[i-1]*BS%HMOD;
	while(qu--) solve();
	return 0;
}
上一篇:CF587F Duff is Mad


下一篇:洛谷 P4900 - 食堂(推式子)