P10597 BZOJ4665 小 w 的喜糖

· · 题解

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

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

故考虑二项式反演，定义 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)。