Luogu4491 [HAOI2018]染色


Description

为了报答小 C 的苹果, 小 G 打算送给热爱美术的小 C 一块画布, 这块画布可 以抽象为一个长度为 \(N\) 的序列, 每个位置都可以被染成 \(M\) 种颜色中的某一种.

然而小 C 只关心序列的 \(N\) 个位置中出现次数恰好为 \(S\) 的颜色种数, 如果恰 好出现了 \(S\) 次的颜色有 \(K\) 种, 则小 C 会产生 \(W_k\) 的愉悦度.

小 C 希望知道对于所有可能的染色方案, 他能获得的愉悦度的和对 \(1004535809\) 取模的结果是多少。

\(n\le 1e7,m\le 1e5,S \le 150\)

Solution

首先我们很自然地写出了一个

\[ G_i=\binom{M}{i}\binom{N}{iS}\frac{(i*S)!}{(S!)^i}(M-i)^{N-is} \]

组合意义就是先选 \(i\) 种颜色,然后把这\(i*S\)个物品选个位置,再给剩下的位置涂上颜色。感觉上好像是答案,其实不是。问题就出在我们最后任意涂的颜色,这些颜色的出现次数可能会恰好是 \(S\) 次。那么难道 \(G_i\)至少\(K\) 种的 方案数吗?也不是。我们发现 \(G_i\) 是会有重复的 。仔细思考一下发现

\[ G_n=\sum_{j=n}^{\min(N/S,M)} F_j\binom{j}{n} \]

其中 \(F\) 就是题目中要求的。

那么二项式反演一下

\[ \begin{aligned} F_n&=\sum_{j=n}^{\min(N/S,M)}(-1)^{j-n}\binom{j}{n}G_j \\ F_nn!&=\sum_{j=n}^{\min(N/S,M)}\frac{(-1)^{j-n}}{(j-n)!}(j!G_j)\\ F_nn!&=\sum_{j=n}^{lim}A[j-n]*B[j] \\ F_nn!&=\sum_{j=n}^{lim}A[j-n]*B_{rev}[lim-j]\\ F_nn!&=\sum_{j=0}^{lim-n}A[j]*B_{rev}[lim-n-j] \end{aligned} \]

好,那么把 \(j!G_j\) 转一下就是卷积的形式啦!


文章作者: ffacs
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 ffacs !
  目录