氪鎄的容斥。

原题 CF1799G。

subtask 1

爆搜，时间复杂度 $O(n^n)$。

subtask 2

对答案最有启发意义的 subtask。

假设没有自己不能给自己投票这个限制，则最后的答案是一个不穿衣服的多重集排列数，计算公式为：

$$\frac{n!}{\prod_{i=1}^nc_i!}$$

现在考虑我们减去不合法的情况，我们记 $S_i$ 表示钦定 $i$ 个人把票投给自己的方案数，则根据容斥原理，答案就是：

$$\frac{n!}{\prod_{i=1}^nc_i!}-\sum_{i=1}^n(-1)^{i+1}S_i$$

现在我们考虑如何求 $S_i$，注意到有：

$$\begin{aligned} S_i&=\sum_{T\subseteq\{1,2,\cdots,n\},|T|=i}\frac{(n-i)!}{\prod_{j=1}^n(c_j-[j\in T])!}\\ &=(n-i)!\sum_{T\subseteq\{1,2,\cdots,n\},|T|=i}\left(\prod_{j=1}^n(c_j-[j\in T])!\right)^{-1} \end{aligned}$$

由于前面的 $(n-i)!$ 只和 $i$ 有关，所以我们把 $S_i$ 的定义变成后面那一坨，最后只需要乘上 $(n-i)!$ 即可。

现在我们希望能够求出后面那一坨东西，于是我们考虑 dp 设个状态。设 $f_{i,j}$ 表示钦定第 $i$ 个人给自己投票，在 $[i,n]$ 中有 $j$ 个人给自己投票的多重集排列数的分母部分之和，然后就有递推：

$$f_{i,j}=c_j\sum_{k=i+1}^nf_{k,j-1}$$

挺显然的吧，就是你把 $c_j-[j\in T]$ 这一步看成是把 $c_j$ 乘进去，然后就能得到这个递推，于是就有：

$$S_i=\sum_{j=1}^nf_{j,i}$$

对于 $f$ 的那个递推式，你可以把 $S$ 扩一维，令：

$$S_{i,j}=\sum_{k=1}^jf_{k,i}$$

于是：

$$\begin{aligned} f_{i,j}&=c_j\cdot\left(S_{j-1,n}-S_{j-1,i}\right)\\ S_{i,j}&=S_{i,j-1}+f_{j,i-1} \end{aligned}$$

初始化直接：

$$f_{i,1}=c_i\cdot\left(\prod_{j=1}^nc_j!\right)^{-1}$$

即可。

你得到了一个 $O(n^2)$ 的做法。

正解

考虑把那个 subtask 2 的部分做一个拓展。

注意到这个时候不合理的情况变成了某个位置 $i$ 选择了其所在家庭的某个人，所以我们把定义改一改。设 $f_{i,j,k}$ 表示钦定第 $i$ 个家庭给自己投票，第 $i$ 个家庭中有 $j$ 个人给自己家投了票，在 $[i,n]$ 中有 $k$ 个人给自己的家庭投票的多重集排列数的分母部分之和，然后就有递推：

$$f_{i,j,k}=\left(\prod_{l=0}^{j-1}(c_i-l)\right)\cdot (S_{k-j,n}-S_{k-j,i})\cdot\binom{c_j}{j}$$

$S$ 的定义不变，只不过求和时要枚举 $f$ 的两维。

初始化的时候直接：

$$f_{i,j,j}=c_i\cdot\left(\prod_{k=1}^nc_k!\right)^{-1}\cdot\binom{c_i}{j}$$

这是你可能会问，这不是 $O(n^3)$ 的递推吗？其实不是的，因为 $\sum c=n$，所以实际上 $f$ 的第二维在定死 $k$ 的情况下只会变化 $O(n)$ 次，所以实际上这是一个 $O(n^2)$ 的递推。

但是，最后的时候容斥出来的东西不是要减去的东西，由于你减去的东西实际上是自己家人给自己家人投票的方案数，是家给家的方案，而不是人给人的方案，所以最后还要乘上家里人的多重集排列数。我们记 $T_i$ 表示第 $i$ 个家庭的人数，则最后的答案为：

$$\frac{n!}{\prod_{i=1}^nc_i!}-\left(\sum_{i=1}^n(-1)^{i+1}\cdot(n-i)!\cdot S_{i,n}\right)\cdot \frac{\prod_{i=1}^nT_i!}{\prod_{i=1}^nc_i!}$$

时间复杂度 $O(n^2)$。