[HAOI2018]染色

时间：2020-05-16 22:56:35 阅读：50 评论：0 收藏：0 [点我收藏+]

题目

注意到数据范围中的重点 \(S\le 150\) 。

有了这个关键的数据范围，再加上题目对于 \(W[]\) 的定义”如果恰好出现了 \(S\) 次的颜色有 \(K\) 种, 则小 C 会产生 \(W_k\) 的愉悦度.“，其实这道题思路就比较明显了——利用容斥，计算出现次数恰好为 \(S\) 的颜色为 \(k\) 的方案数。

首先，我们考虑，假设我们有 \(k\) 个出现次数为 \(S\) 的颜色，他们内部的填色方案 \(T[k]\)，那么显然有

\[T[k]=\prod_{i=0}^{k-1} C_{kS-iS}^S \]

具体理解就是 \(k\) 种颜色中的前 \(i\) 种先使用完 \(iS\) 个格子之后，从剩下的 \(kS-iS\) 个格子种选出 \(S\) 个作为第 \(i+1\) 种颜色放置的位置。

我们将上式变换一下，就有

\[\begin{aligned} T[k]&=\prod_{i=0}^{k-1}\frac{(kS-iS)!}{S!(kS-iS-S)!} \&=\prod_{i=0}^{k-1}\frac{(kS-iS)!}{S![kS-(i+1)S]!} \end{aligned} \]

发现分母中 \([kS-(i+1)S]!\) 能与下一项，也就是 \(i‘=i+1\) 时的分子消去，那么前一项分母与后一项分子两两相消之后，我们能够得到

\[T[k]=\frac{(kS)!}{(S!)^k} \]

继续分析，由于我们使用容斥，定义 \(G[k]\) 为当有不少于 \(k\) 种颜色刚好 \(S\) 出现情况时的方案数，定义 \(F[k]\) 为当有刚好 \(k\) 种颜色出现 \(S\) 的情况方案数。

显然有

\[F[k]=\sum_{j=i}^m (-1)^{j-k}\times G[j]\times C_j^k \]

但是这个 \(G[k]\) 怎么算呢？我们都处理出 \(T[k]\) 了，那么 \(G[k]\) 也很明显

\[G[k]=C_m^k\times T[k]\times (m-k)^{n-kS} \]

那么这个时候，我们的时间复杂度是多少了呢？

考虑 \(G[],T[]\) 都可以预处理，阶乘、逆元也可以预处理，那么最后的时间复杂度在于计算 \(F[]\) 的时间，能够看出，其时间复杂度为 \(\mathcal O(m^2)\) 的。

这是 \(50\%\) 的得分了。

有了前面的分析，我们的目的很明确了——降低计算 \(F[]\) 的复杂度。

考虑将 \(F[]\) 的计算式

\[F[k]=\sum_{j=i}^m (-1)^{j-k}\times G[j]\times C_j^k \]

同样地，我们将 \(C\) 变换为阶乘的形式，那么有

\[\begin{aligned} F[k]&=\sum_{j=i}^m (-1)^{j-k}\times G[j]\times C_j^k \&=\sum_{j=i}^m (-1)^{j-k}\times G[j]\frac{j!}{k!(j-k)!} \end{aligned} \]

由于这个时候我们假设了当前为 \(k\)，即目前 \(k\) 是一个固定值，考虑将最后一项分母中的 \(k!\) 拿出来，就有

\[F[k]=\frac{1}{k!}\sum_{j=i}^m (-1)^{j-k}\times G[j]\frac{j!}{(j-k)!} \]

移项，有

\[F[k]\times k!=\sum_{j=i}^m (-1)^{j-k}\times G[j]\frac{j!}{(j-k)!} \]

我们令 \(H_1[j-k]=(-1)^{j-k}\times \frac{1}{(j-k)!}\)

再令 \(H_2[j]=G[j]\times j!\)

是否十分明朗了？假如我们将 \(H_1[]\) 执行一次类似于 reverse() 的操作，那么

\[H_1[k-j]=(-1)^{j-k}\times \frac{1}{(j-k)!} \H_2[j]=G[j]\times j! \]

而我们最后要求的 \(F[k]=\frac{H_1[k-j]\times H_2[j]}{k!}\)

上面是不是卷积？！！是不是 NTT ？！！

于是，这道题 \(100\%\) 的数据就这么解决了。

原文：https://www.cnblogs.com/Arextre/p/12902562.html

踩

(0)

评论一句话评论（0）

分享档案

更多>