自动搬运

查看原文

来自洛谷，原作者为

	Anonymely 330。

搬运于2025-08-24 22:59:30，当前版本为作者最后更新于2024-08-12 19:14:21，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

直接计数不好计，原因在于直接做必须要记下每种颜色数剩多少。

注意到限制 糖的种类与原来不同 的反面 糖的种类与原来相同 是相对好做的，且每种颜色在该限制下独立。

故考虑二项式反演，定义 $m$ 为颜色总数，$x_i$ 表示颜色为 $i$ 的位置有多少个，$y_i$ 表示颜色为 $i$ 的位置中钦定 $y_i$ 个满足糖的种类与原来相同（即不满足题目条件），$g_i$ 表示钦定 $\sum y = i$ 的方案数，$f_i$ 表示恰好有 $i$ 个位置不满足条件的方案数。

我们要求 $f_0$，根据二项式反演（实际上就是容斥）我们有 $f_0 = \sum_{i=0}^n(-1)^ig_i$，问题转化为求 $g_i$。

对于一组确定的 $y$，方案数为：

$$\frac{(n-\sum y_i)!}{(x_i - y_i)!}\prod \binom{x_i}{y_i} $$

即对于每一种颜色先选出 $y_i$ 个位置不变，剩下的为多重集排列。

对该式子做背包即可做到 $O(n^2)$，虽然有三重循环但实际是 $O(n^2)$ 的，原因是对于任意两个不同颜色的数都只算了一遍贡献。

当然也可以看成 $m$ 个总项数和为 $n$ 的多项式相乘，可以做到 $O(n\log^2n)$。