期望 dp
普通期望 dp
CF1925D Good Trip
有 \(n\) 个同学，\(m\) 对朋友。起初，第 \(i\) 对朋友的友好值为 \(f_i\)，非朋友的友好值为 \(0\)。
执行 \(k\) 次操作：
- 选中两个同学；
- 若他们是朋友，则将他们的友好值加上 \(1\)。
求每次操作前选中同学后选中同学的友好值的期望值之和。
\(n,m\leq 10^5\)，\(k\leq 2\times 10^5\)。
概率期望好题。显然有 \(N=\dfrac{n(n+1)}{2}\) 对同学。
考虑初始值的贡献。 每次选中第 \(i\) 对朋友的概率是 \(\dfrac{1}{N}\)，所以第 \(i\) 对朋友的贡献为 \(\dfrac{kf_i}{N}\)。所以所有朋友初始值的贡献为 \(\dfrac{k\sum f_i}{N}\)。
现在我们可以考虑友好值全为 \(0\) 的问题。每对朋友显然是独立的，可以分开计算。假设选中第 \(i\) 对朋友 \(x\) 次，贡献显然为 \(\frac{x(x-1)}{2}\)（注意贡献是在友好值自增之前计算的）。选中第 \(i\) 对朋友恰好 \(x\) 次的概率显然为 \({k\choose x}\left(\frac{1}{N}\right)^x\left(\frac{N-1}{N}\right)^{k-x}\)，所以我们只需要计算
\[\sum_{x=0}^k {k\choose x}\frac{x(x-1)}{2}\left(\frac{1}{N}\right)^x\left(\frac{N-1}{N}\right)^{k-x} \]就可以得到第 \(i\) 个朋友的总贡献。注意到每对朋友的贡献相同，于是乘以 \(m\) 即可。
单次复杂度 \(\Theta(k\log p)\)。
P3239 [HNOI2015] 亚瑟王
环上的期望 dp
CF963E Circles of Waiting
一个动点初始在原点处，每次以 \(p_1\) 的概率向左移动一格，\(p_2\) 的概率向下移动一格，\(p_3\) 的概率向右移动一格，\(p_4\) 的概率向上移动一格。求移到距离原点大于 \(r\) 的点的期望步数。
\(r\leq 50\)。
设 \(f[i,j]\) 为从 \((i,j)\) 走到符合条件的点的期望步数。我们显然有
\[f[i,j]=\begin{cases} p_1f[i-1,j]+p_2f[i,j-1]+p_3f[i+1,j]+p_4f[i,j+1]+1 & i^2+j^2\leq r^2 \\ 0 & i^2+j^2\gt r^2 \end{cases} \]有 \(\Theta(r^2)\) 个点，朴素的 Gauss 消元为 \(\Theta(r^6)\) 无法通过。然而，我们有两种优化。
主元法
对转移方程变形，得到
\[f[i+1,j]=\frac{1}{p_3}\left(f[i,j]-p_1f[i-1,j]-p_2f[i,j-1]-p_4f[i,j+1]-1\right) \]注意到 \(f[i+1,j]\) 只和其左边的点有关。于是我们选定每一行最左边的离原点距离小于等于 \(r\) 的点作为主元，对每一个点 \((i,j)\)，我们可以由转移方程推出一个向量 \((a_1,a_2,a_3,\cdots,a_{2r+1},b)\)，表示 \(f[i,j]=b+\sum_{i=1}^{2r+1}a_ix_i\)。我们选出 \(2r+1\) 个离远点大于 \(r\) 的点，此时显然有 \(f[i,j]=b+\sum_{i=1}^{2r+1}a_ix_i=0\)。由此可以解出 \(2r+1\) 个主元，然后直接代入 \((0,0)\) 对应的向量求解即可。
时间复杂度 \(\Theta(r^3)\)，可以通过。
P6125 [JSOI2009] 有趣的游戏
给定 \(n\) 个长度为 \(m\) 的字符串 \(P_i\)，字符集 \(|\Sigma|=l\)。
初始时有一个空字符串 \(S\)。每次 以 \(p_i\) 的概率选取字符 \(i\) 加到 \(S\) 的尾部。当存在 \(i\in [1,n]\)，使得 \(P_i\) 是 \(S\) 的子串时停止这个过程，我们称为在 \(i\) 处停止。对于 \(i\in [1,n]\)，求在 \(i\) 处停止的概率。
\(n,m,l\leq 10\)。
建出 \(P_i\) 的 AC 自动机。此时问题转化为：
给定有向图 \(G\)，初始你在 \(0\) 号点处。每条出边有 \(p_i\) 的概率被选取（保证每个节点的出边概率之和为 \(1\)），每次选取一条出边走到下一个节点。有一些关键点，走到关键点后停止。求走到每个关键点的概率。
既然是概率，考虑正推。设 \(f[u]\) 为从起点走到 \(u\) 的概率，初始值为 \(f[s]=1\)。我们有如下的转移：
\[f[v]=\sum_{(u,v,p_i)\in E} p_i\cdot f[u] \]转移可能成环，Gauss 消元即可。时间复杂度 \(\Theta(n^3m^3)\)，可以通过。
概率生成函数（PGF）
设 \(X\) 为仅取非负整数值的随机变量。定义 \(X\) 的概率生成函数（PGF）为
\[G_X(z)=\sum_{k\geq 0} P(X=k) z^k \]显然有 \(\sum_{k\geq 0} P(x=k)=1\)，即 \(G_X(1)=1\)。
PGF 与数学期望
\[\begin{aligned} E(X)&=\sum_{k\geq 0} k\cdot P(X=k) \\ &=\sum_{k\geq 0} P(X=k) \cdot 1^{k-1} \\ &= G_X'(1) \end{aligned} \]进一步有
\[E(X^{\underline{k}})=G_X^{(k)}(1) \]PGF 与方差
\[\begin{aligned} D(X)&=E(X^2)-E^2(X) \\ &=E(X^{\underline{2}})-E^2(X)+E(X) \\ &=G''(1)-G'^2(1)+G'(1) \end{aligned} \]我们只需要知道 \(G''(1)\) 和 \(G'^2(1)+G'(1)\) 即可求出方差。
PGF 与卷积
设 \(X,Y\) 为仅取非负整数值的随机变量，且相互独立。那么显然有
\[\begin{aligned} P(X+Y=n)&=P(X=k \land Y=n-k) \\ &=P(X=k)P(Y=n-k) \\ &=\sum_{k=0}^n P(X=k)P(Y=n-k) \end{aligned} \]显然是一个卷积的形式，所以我们得到了
\[G_{X+Y}(z)=G_X(z)G_Y(z) \]P6125 [JSOI2009] 有趣的游戏
给定 \(n\) 个长度为 \(m\) 的字符串 \(P_i\)（\(P=\{P_1,P_2,\cdots,P_n\}\)），字符集 \(|\Sigma|=l\)。
初始时有一个空字符串 \(S\)。每次等概率随机选取字符 \(i\) 加到 \(S\) 的尾部。对于字符串 \(P_i\)，当且仅当 \(\exists p\in P\backslash\{P_i\}\) 使得 \(p\) 是 \(S\) 的子串时停止这个过程，记此时的期望长度为 \(f(i)\)。
对于 \(i\in [1,n]\)，求 \(f(i)\)。只需要保留后四位数字。
\(n\leq 50\)，\(l,|P_i|\leq 10^5\)。
P3706 [SDOI2017] 硬币游戏
给定 \(n\) 个长度为 \(m\) 的字符串 \(P_i\)，字符集 \(\Sigma=\{\texttt{0},\texttt{1}\}\)。
初始时有一个空字符串 \(S\)。每次等概率随机选取 \(\texttt{0}\) 或 \(\texttt{1}\) 加到 \(S\) 的尾部。当存在 \(i\in [1,n]\)，使得 \(P_i\) 是 \(S\) 的子串时停止这个过程，我们称为在 \(i\) 处停止。对于 \(i\in [1,n]\)，求在 \(i\) 处停止的概率。
\(n,m\leq 300\)。
本题即为 P6125 的加强版。\(\Theta(n^3m^3)\) 只能通过 \(40\%\) 的数据（不能通过 \(60\%\) 的数据的原因是，精度问题）。
标签：概率,期望,sum,leq,Theta,frac From： https://www.cnblogs.com/Starrykiller/p/18028199/probability