cf908d专题

CF908D New Year and Arbitrary Arrangement [概率DP]

传送门 f[i][j] 表示有 i 个 a, j 个 ab 的期望, 设 A 为选 a 的概率, B 为选 b 的 如果 i + j >= k 那么再放一个 b 就可以结束, 这种情况的期望就是 转移的话 初始状态如果是 0, 0 的话 显然会死循, 因为一开始可能为 bbbbbbb... 但由于 A = 1 - B, 所以上面那个式子等价于  所以初始状态设为 f[1]