CF1765C Card Guessing

· · 题解

根据期望的线性性，将答案摊到每次猜测。

第 i 次猜测的已知卡片数量为 c = \min(i - 1, k)。设四种卡片落在已知卡片区的张数分别为 c_1\sim c_4，需要满足 c = \sum c_i，则安排这些卡片的方案数为

\binom {c} {c_1, c_2, c_3, c_4} \binom {4n - c}{n - c_1, n - c_2, n - c_3, n - c_4}

我们要从所有出现次数最小的卡片中选一个放到下一个位置上。设出现次数最小的卡片数量为 d，则有 d 种方案，但因为 Monocarp 会从这 d 张卡片中随机选择，所以一乘一除抵消掉了。设最小值为 mn = \min c_i，则贡献至答案的式子为

\binom {c} {c_1, c_2, c_3, c_4} \binom {4n - c}{n - c_1, n - c_2, n - c_3, n - c_4} \times \dfrac {\binom {4n - c - 1} {n - mn - 1}} {\binom {4n - c} {n - mn}}

即

\dfrac {c!} {c_1! c_2! c_3! c_4!} \dfrac {(4n - c - 1)! (n - mn)!} {(n - c_1)! (n - c_2) ! (n - c_3)! (n - c_4)! (n - mn - 1)!}

枚举最小值 p，设 f_i 表示使得 c = i 的方案数之和，做背包即可。

时间复杂度 \mathcal{O}(n ^ 3)。代码。