概率生成函数

part0 What is it ?

一类人为规定的函数

设 (f(i)) 为第 (i) 项的概率

那么设 (F(x)) 为 (f) 的生成函数

[F(x) = sum_{i geq 0} f(i) * x ^ i ]

part1 一些性质

(1: F'(1) = E(x))

假如第 (i) 项的值为 (i)

则这件事情的期望 (E) 为

[sum_{i geq 0} i * f(i) ]

我们发现

[F'(x) = sum_{i geq 0} i * f(i) * x ^ {i - 1} ]

[F'(1) = sum_{i geq 0} i * f(i) = E(x) ]

$2 : $ 方差 $val(x) = $ $ F''(1) + F'(1) - F'(1) ^ 2 $

已知方差为

[E(x^2) - E(x)^2 ]

那么

[E(x^2) = sum_{i geq 0} i ^ 2 * f(i) ]

[F''(x) = sum_{i geq 0} i * (i - 1) * f(i) * x ^ {i - 2} ]

把式子拆开

[E(x^2) = F''(x) + F'(x) ]

[E(x^2) - E(x)^2 = F''(x) + F'(x) - F'(x) ^ 2 ]

然后就是做题了。。。

P4548 [CTSC2006] 歌唱王国

暴力

就是建一个ＫＭＰ自动机，高斯消元

正解

我们先设几个变量， (A) 表示名字序列，(m) 表示随机数生成器范围， (L) 表示名字长度

设 (f(i)) 表示序列在第 (i) 处结束的概率，答案就是 $ sumlimits_{i geq 0} i * f(i)$

我们发现这玩意有无穷多项，考虑使用概率生成函数

设 (F(X)) 为 (f) 的生成函数，答案就是 (F'(1))

这样还是毫无思绪，我们考虑上网搜题解

题解告诉我们，这种类型的题讲究套路，那我们就用套路

设 $g(i) $ 为序列长为 (i) 但没有结束的概率，它的生成函数为 (G(x))

对于 (G(x)) 此时序列还没有结束，我们往里面随便放一个数 (G(x) * 1 * x) 此时它可能结束，也可能没结束，那它就等于 (F(x) + G(x)) ，这样的话里面一定有字母，我们就少统计了 (f(0), g(0)) ，把它们加进去，(f(0) = 0, g(0) = 1) 此时我们得出一个等式

[F(x) + G(x) = 1 + G(x) * x ]

里面有两个未知量，我们还要再搞出一个

对于一个 (G(x)) 我们把一个人的名字 (A) 序列放进去，这时候序列一定结束了，但对于每一个未放完序列 (g(i)) 不一定是在 (i + |A|) 处结束，还可能更早

比如序列 (g(i)) 放入 (|A|) 后，在 (j (j > i)) 处结束，那他的概率就是

[g(i) * (frac 1 m) ^ L = f(j) * (frac 1 m) ^ {L - j} ]

序列在 (j) 处结束当且仅当 $A[1, (j - i)] = A[L - (j - i), L] $

于是我们可以得出

[G(x) * (frac 1 m) ^ L = sum_{A[1, i] = A[L - i, L]} F(x) * ( frac 1 m) ^ {(L - i)} ]

统计一下我们现在有两个式子

[egin{cases} F(x) + G(x) = 1 + G(x) * x \ G(x) * (frac 1 m) ^ L = sumlimits_{A[1, i] = A[L - i, L]} F(x) * ( frac 1 m) ^ {(L - i)} end{cases} ]

对一式求导

[F'(x) + G'(x) = G'(x) * x + G(x) ]

当 (x = 1) 时

[F'(1) + G'(1) = G'(1) + G(1) ]

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

我们现在想知道 (G(1))，把 (x = 1) 带入二式得

[G(1) * (frac 1 m) ^ L = sum_{A[1, i] = A[L - i, L]} F(1) * ( frac 1 m) ^ {(L - i)} ]

[G(1) = sum_{A[1, i] = A[L - i, L]} F(1) * m ^ i ]

而 (F(1) = sum p_i = 1)

所以

[E = G(1) = sum_{A[1, i] = A[L - i, L]} m ^ i ]

这个东西可以用 KMP 暴力 O(L) 跳边计算

于是这道题就解决了，时间复杂度 (O(t * L))

(code)

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
int nxt[N], s[N], pw[N], n, m, t;
const int mod = 10000;
#define rg register
inline int read(){
	rg char ch = getchar();
	rg int x = 0, f = 0;
	while(! isdigit(ch)) f |= (ch == '-'), ch = getchar();
	while(isdigit(ch)) x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar();
	return f ? -x : x;
}
int main(){
	n = read(), t = read();
	pw[0] = 1;
	for(int i = 1; i < N; ++i) pw[i] = pw[i - 1] * n % mod;
	while(t--){
		m = read();
		for(int i = 1; i <= m; ++i) s[i] = read();
		for(int j = 0, i = 2; i <= m; ++i){
			while(j && s[j + 1] ^ s[i]) j = nxt[j];
			j += (s[j + 1] == s[i]);
			nxt[i] = j;
		}
		int ans = 0;
		for(int i = m; i; i = nxt[i]){
			(ans += pw[i]);
			if(ans >= mod) ans -= mod;
		}
		printf("%04d
", ans);
	}
	return 0;
}