HNOI2015 亚瑟王
标签
期望线性性，DP
\(T(T \le 444)\) 组询问，\(n \le 220, r \le 132\)
一个小结论：对于一个卡牌 \(i\)，如果遍历了 \(j\) 次（不管是否已经发动），不发动的概率为 \((1 - p_i)^j\)，发动的概率为 \(1 - (1 - p_i)^j\)。
根据期望线性性，设 \(F(i)\) 表示第 \(i\) 张卡牌经过 \(r\) 局游戏后发动的概率。那么 \(ans = \sum F(i) d(i)\)
- 第一张卡牌一定被遍历 \(r\) 次，\(F(1) = 1 - (1 - p_i)^r\) 。
- 第二张卡牌有 \(F(1)\) 的概率遍历 \(r - 1\) 次，\(1 - F(1)\) 的概率遍历 \(r\) 次，可计算出 \(F(2)\)。
- \(\dots \dots\)
不难发现：\(F(i)\) 只和第 \(i\) 张卡牌的遍历次数相关，而这个遍历次数又和前 \(i - 1\) 张卡牌总共的发动次数有关（也就是和 \(F(1) \sim F(i - 1)\) 有关。）
可以设计出一个 DP，令 \(f(i, j)\) 表示前 \(i\) 张牌发动了 \(j\) 张的方案数，转移时可以算出此时的 \(F'(i + 1, j)\)，转移到 \(f(i + 1, j), f(i + 1, j + 1)\)。而真的 \(F(i + 1) = \sum\limits_{j = 0}^r F'(i + 1, j)\)，继而求出 \(ans\)。
时间复杂度：\(O(\sum nr)\)。
根据期望线性性，明确我们要求出 \(F(i)\)，再找到 \(F(i)\) 与什么相关，进行 DP。