概率生成函数
最近联测打到了两道能用概率生成函数直接秒的题。但是我不会概率生成函数。
概率生成函数.gb
对于非负整数范围内的随机变量 \(X\)，令 \(p_i\) 表示 \(X=i\) 的概率，那么我们定义 \(X\) 的概率生成函数 \(P\) 为 \(p\) 的普通生成函数，即 \(P=\sum_z p_iz^i\)。
我们对 \(P\) 求导得到 \(P'=\sum_z p_{i}iz^{i-1}\)，于是有 \(P'(1)=\sum_z p_{i-1}i\)，即 \(E(X)\)。
如果我们对 \(P\) 求 \(k\) 阶导函数，那么就可以得到 \(P^{(k)}(1)=E(X^{\underline{k}})\)。
使用例
考虑用它解决一类动态加字符匹配期望长度的问题。以下默认用 \(m\) 表示字符集大小。
例 1.1 (CTSC2006 歌唱王国) 给定模板串 \(S\)，文本串 \(T\) 一开始为空。每次在文本串的末尾等概率添加一个随机字符，若添加完成后可以匹配 \(S\) 立即中止。求文本串期望大小。\(O(|S|)\)。
设 \(|T|\) 的概率生成函数为 \(F\)，并设 \(g_i\) 表示添加了 \(i\) 次后仍不能匹配的概率，\(G\) 为 \(g\) 的普通生成函数。考虑 \(G(1)\) 的组合意义：\(G(1)=\sum g_i=E(|T|)\)，于是有 \(G(1)=E(|T|)=F'(1)\)。这个也可以通过对方程 \(F+G=zG-1\) 求导得到。
然后我们考虑一个方程。对于一个未满足要求的串 \(X\)（生成函数为 \(G\)），我们在后面拼上一个 \(S\)（生成函数为 \((\frac{z}{m})^{|S|}\)），我们还可以通过如下方式得到这样的串：对于一个恰好满足要求的串 \(Y\)（生成函数为 \(F\)），此时 \(Y\) 的后缀一定是一个 border 或整个串，于是我们将这个 border 补全得到整个串（生成函数为 \((\frac{z}{m})^{|S|-L}\)），于是方程为
我们取 \(z=1\)，令 Border 集合为 \(B\)，把 \(G\) 换成 \(F'\) 即可得到 \(F'(1)=\sum_{i\in B\cup \{|S|\}}m^i\)。
例 1.2 给定模板串集合 \(S_1,\dots,S_n\)，若添加完后可以匹配任意模板串即中止，其余条件同例 1.1。\(O(n^3+n\sum |S_i|)\)。
设 \(F_i\) 表示配上的是 \(S_i\) 的概率的生成函数，则有 \(\sum F_i(1)=1\)。同时保留 \(G\) 的定义，我们有 \(G=\sum F_i'\)。答案即 \(G(1)\)。
考虑类似的方程。只不过这次要列 \(i\) 个方程，第 \(i\) 个方程为 \(X+S_i\) 的两种生成函数表示，而我们最后的后缀可能是其它串与 \(S_i\) 进行前后缀匹配得到的，令 \(a_{i,j,k}=[S_i[1,k]=S_j[|S_j|-k+1,|S_j|]]\) 于是有
我们将 \(G(1),F_i(1)\) 作为 \(n+1\) 个变量，上述方程与 \(\sum F_i(1)=1\) 作为 \(n+1\) 个方程，消元即可。
例 1.3 维护模板串集合，支持动态加入模板串，其余条件同例 1.2。\(O(n^3+n\sum |S_i|)\)。
我们考虑加入一个串对于这个方程的影响。实际上，我们相当于插入了一行一列。考虑记录消元时的行变换，然后就可以维护动态插入一行一列了。复杂度是相同的。
例 1.4 每个字符插入的概率为 \(p_i\)，\(\sum p_i=1\)，其余条件同例 1.3。\(O(n^3+n\sum |S_i|)\)
此时对于 \(S_i\)，其生成函数不再是 \((\frac{z}{m})^{|S_i|}\)，而是 \(z^m\prod_{j=1}^{|S_i|} p_{S_{i,j}}\)。同理，对于 \(S_j\) 的长 \(k\) 的后缀也要进行改变，变为后缀的 \(p\) 的乘积。
例 1.5 给定模板串集合 \(S_1,\dots,S_n\)，若添加完后可以匹配所有模板串即中止，其余条件同例 1.1。\(O(2^nn^3+n\sum |S_i|)\)。
考虑进行 Min-Max 容斥，枚举 Min-Max 容斥的集合，然后再做 1.2 的操作即可。
例 2.1 文本串一开始为空，每次在文本串的末尾等概率添加一个随机字符，若添加完成后，长 \(n\) 的后缀字符全部相同立即停止。问期望操作次数。\(O(n+m)\)。
这题中的方程考虑在未满足要求的串后拼 \(n\) 个相同字符，可以得到
解得 \(F(1)=\frac{m^n-1}{n-1}\)。
例 2.2 文本串一开始为空，每次在文本串的末尾等概率添加一个随机字符，若添加完成后，长 \(n\) 的后缀字符全部不同立即停止。问期望操作次数。\(O(n+m)\)。
解得 \(F(1)=\sum_{i=1}^{n} \frac{m^i}{m^{\underline{i}}}\)。长得很有趣。