H - Collecting Bugs POJ-2096
期望 dp
题意
根据题意可以将原题意转换成：
有个 \(n * s\) 的矩阵，每次会随机选取一个格子填上颜色，问每行每列都填上颜色的期望次数。
思路
dp，显然是期望 dp，那么设 \(dp_{i,j}\) 为已经有 \(i\) 行 \(j\) 列填上颜色，到目标还需的次数的期望，那么每次可以选的就有四种情况：
- \(dp_{i,j}\) 什么事也没发生，我选的格子的行列都已经被选过了，概率：\(\frac{ij}{ns} = a\)
- \(dp_{i+1,j}\) 选的格子列已经被选过了，但行未被选过，概率：\(\frac{(n - i)j}{ns} = b\)
- \(dp_{i,j + 1}\) 选的格子列已经被选过了，但行未被选过，概率：\(\frac{i(s - j)}{ns} = c\)
- \(dp_{i + 1,j + 1}\) 选的格子列已经被选过了，但行未被选过，概率：\(\frac{(n - i)(s - j)}{ns} = d\)
那么 \(dp_{i,j}\) 的转移式就是：\(dp_{i,j} = 1 + a \times dp_{i,j} + b \times dp_{i+1,j} + c \times dp_{i,j+1} + d \times dp_{i+1,j+1}\)
嗯