题解 P4491 【[HAOI2018]染色】
command_block
·
·
题解
广告：炫酷反演魔术 & 多项式计数杂谈
二项式反演经典题。
设 G_k 表示有恰好 k 种颜色出现了 S 次的方案数。
我们需要求出 G_{0\sim n}，其中 n=\min\big(M,\lfloor N/S\rfloor\big)，然后答案是
{\rm Ans} = \sum_{k=0}^nW_kG_k
一个 naive 的想法是：钦定 k 种颜色，每种强行染上 S 次。剩下的颜色放任自流，随便怎么染。得到
\binom{m}{k}\frac{n!}{(S!)^k(n-Sk)!}(m-k)^{n-Sk}
组合意义：选 k 种颜色 \times 可重排列 \times 放任自流
这个东西肯定不是 G_k，也并不是所谓“至少 k 种颜色出现了 S 次的方案数”。
事实上，这是会重复计数的，但是仍然以优美的方式蕴含了 G_k。
我们设其为 F_k。
-
先从特殊情况来分析：
假设 M=3，有三种颜色 a,b,c，按照上式的组合思想，考虑 F_2 是如何计数的：
1) 钦定 a,b，然后随便染，不幸的是 c 也出现了 S 次
2) 钦定 a,c，然后随便染，不幸的是 b 也出现了 S 次
很明显，F_2 会把 a,b,c 都恰好出现 S 次的方案算重复，所以严格来讲它并不能称之为方案数……或者可以认为是在元素上人为做标记之后的方案数。
究竟算重多少次呢？
考虑有 4 种颜色 a,b,c,d，那么 G_4 与 F_3 间的贡献关系是什么呢？
类比至一般情况，得
F_k=\sum\limits_{i=k}^{n}\dbinom{i}{k}G_i
已知 F 要求 G，不就是二项式反演的经典操作嘛！
反演可得
G_k=\sum_{i=k}^n(-1)^{i-k}\dbinom{i}{k}F_i
到现在复杂度还是 O(n^2) 的，我们考虑把组合数拆开看看能否卷积：
\begin{aligned}
G_k&=\sum\limits_{i=k}^n(-1)^{i-k}\dfrac{i!}{k!(i-k)!}F_i\\
&=\frac{1}{k!}\sum_{i=k}^n\dfrac{(-1)^{i-k}}{(i-k)!}i!F_i
\end{aligned}
可以明显地看到差卷积形式。设
A_i=i!F_i,\quad B_i=\dfrac{(-1)^i}{i!}
则有
G_k=\frac{1}{k!}\sum\limits_{i=k}^nA_iB_{i-k}
NTT 计算差卷积即可，复杂度 O(N+n\log n)。