并非，应该改名为 dp 专题。
经常的转化是，可以把正的过程倒过来，令 \(f\) 为某个状态到最终状态的期望，这样 dp 有时候会更方便。
天依宝宝可爱！
方差
-
定义随机变量 \(X\) 的方差 \(D(X) = E((X - E(X))^2)\)，因为期望就是平均值，所以这个式子的含义就是 \(X\) 的每个值与 \(X\) 的平均值的差的平方的平均值，和初中所学的方差有一点相似之处。
-
方差的平方根称为标准差，记作 \(\sigma(X) = \sqrt {D(X)}\)。
-
方差反应了随机变量的离散程度，方差越大，随机变量的取值越分散。
-
由期望的线性性，可以得到方差的一个更好用的表达式：
\[D(X) = E(X^2) - E(X)^2 \]推导过程：
\[\begin{aligned} D(X) & = E((X - E(X))^2) \\ & = E(X^2 + E(X)^2 - 2XE(X)) \\ & = E(X^2) + E(X)^2 - 2E(X)^2 \\ & = E(X^2) - E(X)^2 \end{aligned} \]其中，第三步的理由是：因为第二步中的 \(E(X)\) 实际上就相当于一个常数了，因为 \(X\) 是固定的，它的期望也是固定的。所以就直接当常数乘出去即可。
-
一个小性质：\(D(aX) = a^2 D(X)\)，其中 \(a\) 为常数。
天依宝宝可爱！
CF148D
思维难度：\(\color{#F39C11} 橙\) *900
概率 dp 板子。令 \(f_{i,j}\) 表示 \(i\) 个白球 \(j\) 个黑球 A 获胜的概率，考虑当前轮拿球的情况，显然有转移：
submission
天依宝宝可爱！
POJ 3071
思维难度：\(\color{#F39C11} 橙\) *900
还是板子，直接暴力 dp 即可，令 \(f_{i,j}\) 为队伍 \(i\) 在 \(j\) 轮后存活的概率，枚举每个可能与 \(i\) 在第 \(j\) 轮相遇的队伍，二进制搞一下，暴力转移，复杂度是 \(O(2^{2n}n)\) 的。
sb poj 一会儿 CE 一会儿 T 一会儿 WA 的，反正思路是对的，代码也挺对的，不调了。猜测是多测多输入了或者少输入了的问题。
WA submission
天依宝宝可爱！
CF768D
思维难度：\(\color{#F39C11} 橙\) *1100
注意到概率期望完全不是同一个东西，不要弄混了。概率是不去考虑每个变量取了多少的，只考虑一个变量发生的概率。
显然 dp 状态就是令 \(f_{i,j}\) 表示 \(i\) 天取了 \(j\) 个物品的概率。转移直接考虑取的是否是新物品即可，有式子：
注意到 \(p \le 1000\)，所以 \(\frac p {2000} \le \frac 1 2\)，所以要求的概率很小，对应的天数实际上也很小，所以直接暴力 dp 是可以的。发现 \(k=1000\) 在天数 \(10000\) 的时候概率已经到达了 \(>0.9\)，故值域取 \(10000\) 即可。
submission
天依宝宝可爱！
POJ 2096
思维难度：\(\color{#FFC116} 黄\) *1300
首先题面很 shi，简要题意：
在一个 \(n \times m\) 的矩阵中，每次操作等概率撒点（包括已经撒过点的位置），求每行每列都撒过点的期望操作次数。
显然有一个显然的 dp，就是令 \(f_{i,j}\) 为填满 \(i \times j\) 的矩阵的操作次数，转移考虑最后一次撒点撒到了什么位置，有：
移项即可。
但是注意到，在 \(i=n , j=m\) 的时候，\(i \times j = n \times m\)，于是左右两边的 \(f_{i,j}\) 就约掉了，就没法转移了。
那么如何处理呢，只能考虑换状态了。我们的目的是不让 \(f_{i,j}\) 的系数的分子可能成为 \(n \times m\)，但发现好像怎么设计都无法避免，那就索性不避免了，直接把它当做初始状态来做！
所以，就可以得到一个新的状态，令 \(f_{i,j}\) 表示填满 \(i \times j\) 的矩阵距离填满 \(n \times m\) 剩余的操作次数，显然次数初始状态为 \(f_{n,m} = 0\)，也不难写出转移式：
虽然 \(i \times j\) 还是可能等于 \(n \times m\)，但是这种情况被放在了初始状态中，所以就相当于避免了它的出现！
submission
天依宝宝可爱！
洛谷 P1850
思维难度：\(\color{#FFC116} 黄\) *1400
怎么以前做过但是现在一点也不会了/jk
dp 是显然的，令 \(f_{i,j,0/1}\) 为前 \(i\) 节课申请换了 \(j\) 次，第 \(i\) 次是否申请的期望代价。
但是发现这样就没法确定第 \(i\) 次是否成功了，但是这是很重要的。
在这里卡住了。
考虑换状态？不行，这样就没法确定上个位置到底申请没申请，也就不能转移。
做法是直接枚举上一次和这一次是否换成功，概率分别为 \(p_{i-1}\) 和 \(p_i\)。
这样为什么是对的呢？不会重复乘一个概率吗？
回到状态定义，注意到状态只关心是否申请，不关心是否成功，所以就包含了成功和不成功两种情况，且两者的概率是已知的。而且在从 \(i-1\) 向 \(i\) 转移的时候，决定新的代价的是 \((i-1,i)\) 的取值，与 \(i-1\) 之前的取值没有任何关联，所以代价就不会重复计算。
或者说，这是一个最小代价的期望而不是操作次数的期望，所以这一步之前的代价与这一步的代价是没有转移的概率关系的，毕竟求最小值是要枚举前面的每个状态来转移而不是把前面的状态乘上概率再加起来。
submission
天依宝宝可爱！
CF908D
思维难度：\(\color{#52C41A} 绿\) *1700
trick：
在状态 \(S\) 下，若一次操作以 \(p\) 的概率转移到状态 \(T\)，以 \(1-p\) 的概率停留在状态 \(S\)，那么从 \(S\) 转移到 \(T\) 的期望步数为 \(\frac 1 p\)。
这个 trick 可以有效地避免算一些无穷级数相关的东西（状态可以达到无穷大）。虽然这个题貌似没用到。
dp 还是很显然的，令 \(f_{i,j}\) 为当前有 \(i\) 个 \(\tt a\)、\(j\) 个 \(\tt ab\)，到停止时的期望 \(\tt ab\) 个数，考虑在后面增加 \(\tt a\) 还是 \(\tt b\)，有：
但是这样可以发现 dp 是没有边界的，\(i\) 可以趋近于无穷大。
不过稍微推一下式子，令 \(a = \frac {p_a} {p_a + p_b} , b = \frac {p_b} {p_a + p_b}\)。注意到当 \(i+j \ge k\) 时，显然 \(f_{i,j+i} = j+i\)。于是有：
为了方便，令 \(t = i+j\)，把 \(b\) 拿出来，有：
于是就需要求 \(\displaystyle \sum _{i=0} ^{+\infin} a^i (t+i)\) 这个无穷级数。
注意到是等差乘等比的形式，所以考虑错位相减，令：
于是：
然后 \((1) - (2)\)，则：
于是只需要求 \(\displaystyle \sum _{i=0} ^n ia^i\) 即可，显然也是个等差乘等比，还是错位相减，令 \(s'_n\) 等于这个东西，有：
\((3) - (4)\) 得：
发现等比数列，对其求和，有：
然后其实就不要把 \(1-a\) 除过去了，因为上面就是要求 \(\displaystyle (1-a) \sum _{i=0} ^n ia^i\)，所以：
把 \(1-a\) 除过去，得：
至此就得到了 \(s_n\) 的通项，带入原式，得：
注意到 \(0 < a < 1\)，所以 \(\displaystyle \lim _{n \to \infin} a^n = 0\)，于是与 \(a^{\infin+1}\) 有关的都可以看做 \(0\) 了。
然后，注意到最后一项中出现了一个 \(\infin \times a^{\infin}\) 的东西，这个趋近于多少呢？丢到 desmos 上即可。可以发现 \(\infin\) 的增长速度远小于 \(a^{\infin}\) 的下降速度，所以这个也是趋近于 \(0\) 的。
有：
因为 \(b = 1-a\)，所以进一步化简：
草草草终于推完了。
还有一点，就是在求 \(f_{0,0}\) 的时候，可以发现 \(f_{0,0} = a f_{1,0} + b f_{0,0}\)，移项推一下得到 \(f_{0,0} = f_{1,0}\)，所以直接求 \(f_{1,0}\) 即可。
submission
天依宝宝可爱！