CF1799G Count Voting 笔记

容斥好题。

发现本题限制有点多，其中棘手的是不能投给自己阵营的人，不然考虑每个人投给了谁，最终答案就是一个可重集的排列数。

于是考虑容斥，考虑求出至少有 $i$ 人投给了自己阵营的人的方案数。

那么可以做背包，设 $f_{i, j}$ 表示考虑前 $i$ 组，至少有 $j$ 人投给了自己组，设 $g (i, k)$ 表示第 $i$ 组至少有 $k$ 人投给自己组的方案数， $d_{i}$ 表示第 $i$ 组有几个人，则有

f_{i, j} = \sum_{k}^{min (j, d_{i})} f_{i - 1, j - k} \times g (i, k)

于是问题在于求 $g (i, k)$ ，显然这个和组外无关，于是考虑第 $p$ 组，可以设 $g_{i, j}$ 表示考虑组内前 $i$ 个人，至少有 $j$ 个人投给了自己阵营的方案数，那么可以拆解成两个部分：投自己投给了谁？投别人投给了谁？

投自己投给了谁是好算的，就是从自己组还没被投的那些人中选若干个出来，即

g_{i, j} = \sum_{k}^{min (j, d_{i})} g_{i - 1, j - k} \times (\binom{d_{p} - (j - k)}{k})

但是投别人投给了谁？这个不好算，考虑最终的 $f_{m, j}$ （ $m$ 是组数），如果我们知道第 $i$ 组有 $a_{i}$ 个人投给了自己组（ $\sum a_{i} = j$ ），那么就可以用可重集排列数：

\frac{(n - j)!}{\prod (c_{i} - a_{i})!}

DP 无法支持记录 $a_{i}$ 到结束，但是发现分子和第 $i$ 组无关，于是考虑 DP 的时候只记录分母的部分，那么转移方程就变成了

g_{i, j} = \sum_{k}^{min (j, d_{i})} g_{i - 1, j - k} \times (\binom{d_{p} - (j - k)}{k}) \times \frac{1}{(c - k)!}

并且令最终的 $f (m, i)$ 乘上 $(n - i)!$ ，于是容斥即可。

时间复杂度，实现的好每一部分 DP 都可以 $n^{2}$ ，但是我感觉算 $g$ 只能是 $O (n^{3})$ 的，求大佬捶，但是题解都说整体 $O (n^{2})$ 。空间复杂度 $O (n^{2})$ 。

CF1799G Count Voting 笔记 ​