https://www.cnblogs.com/zzctommy/p/14256844.html
https://www.cnblogs.com/HenryHuang-Never-Settle/p/14702997.html
概率生成函数，设多项式 \(F(x)=\sum P(X=i)x^i\)。
则：
-
\(F(1)=1\)；
-
\(E(x)=F'(1)\);
-
\(E(x^{\underline{k}})=F^{(k)}(1)\)，\(k\) 阶导。
-
\(E(x^2)=E(x^{\underline{2}}+x^{\underline{1}})=E(x^\underline 2)+E(x^\underline 1)=F''(1)+F'(1)\)。
-
方差 \(V(x)=E((x-E(x))^2)=E(x^2-2xE(x)+E(x)^2)=E(x^2)+E(x)^2-2E(x)E(x)=E(x^2)-E(x)^2\)，即方差等于随机变量平方的期望减去期望的平方。
-
设 \(G(x)=\sum P(X > i)x^i\)，则有 \(1+xG(x)=F(x)+G(x)\)。
-
\(E(x)=F'(1)=G(1)\)。
大小写分不清楚了。。
250.P4548 CTSC2006歌唱王国
答案就是 \(F'(1)\)。
显然有 \(1+xG(x)=F(x)+G(x)\)，求导后可得 \(F'(1)=G(1)\)。
还有 \(F(1)=1\)。
以及
\[G(x)(\dfrac{x}{n})^{m}=\sum_{i=1}^{m}A_iF(x)(\dfrac{x}{n})^{m-i} \]表示还没结束，后面加入一个完整的 \(S\)，但是可能提前结束，枚举在什么时候提前结束，\(A_i\) 表示 \(S[1,i]\) 是否为字符串的 border。
代入 \(x=1\) 后可得，\(G(1)=\sum_{i=1}^{m}A_in^i\)。
251.Hitori的作文(string)
设 \(w_p\) 表示得到连续的字符串 \(p\) 的概率，则 \(w_p=\prod_{i=1}^{n} a_{p_i}\)显然也有
\[G(x)\cdot x^{|S|} \cdot w_S=\sum_{p,\operatorname{p is a border of S}} F(x)\cdot x^{|S|-|p|}\cdot w_{S-p}\\=\sum_{p,\operatorname{p is a border of S}} F(x)\cdot x^{|S|-|p|}\cdot \frac{w_S}{w_p} \]则：
\[G(1)=\sum_{p,\operatorname{p is a border of S}}\frac{1}{w_p} \]252.P3706 [SDOI2017] 硬币游戏 and 加强版
给定 \(n\) 个序列 \(A_1,A_2,\cdots,A_n\)，第 \(i\) 个序列的长度为 \(L_i\)。每次从 \([1,m]\) 中以 \(p_i\) 的概率生成一个数 \(i\) 加入初始为空的序列 \(B\) 末尾，若 \(A_1,A_2,\cdots ,A_n\) 均为 \(B\) 的子串则停止。求序列 \(B\) 的期望长度。
答案为 \(E(\max(T_i))\)，\(T_i\) 表示 \(i\) 首次出现时的长度。
容斥后答案为：\(\sum_{S\subseteq\{1,2,\cdots n\}}(-1)^{|S|+1}E(\min_{i\in S}(T_i))\)。
即只考虑 \(S\) 中字符串，出现一个 \(A_i\) 就停止的期望长度。
设 \(G(x)\) 表示 \(i\) 轮之后还没结束的概率。
记 \(F_i(x)\) 表示第 \(i\) 个人在第 \(j\) 轮获胜概率，\(P(T)=\prod_{i\in T} p_i\)，\(a_{i,j,k}=[A_i[1,k]=A_j[L_{j}-k+1,L_j]]\)。
则有：
\[\sum_{i=1}^{n}F_i(x)+G(x)=1+xG(x)\\ \forall i\in S,G(x)P(A_i)x^{L_i}=\sum_{j\in S}\sum_{k=1}^{L_i}a_{i,j,k}F_j(z)P(A_i[k+1,L_i])x^{L_i-k} \]答案就是 \(\sum_{i=1}^{n}F_i'(1)\)。
带入 \(x=1\) 得到 \(n\) 个方程，同时还有 \(\sum_{i=1}^{n}F'(1)=G(1),\sum_{i=1}^{n}F(1)=1\)。
高斯消元即可。
标签：概率,函数,cdot,sum,生成,cdots,border,underline From： https://www.cnblogs.com/orzz/p/18345967