题解：P4491 [HAOI2018] 染色
xiezheyuan
·
·
题解
摘要：这里介绍仅使用 EGF 而不使用二项式反演的一种解法。
前置知识：指数生成函数（EGF）、多项式乘法（卷积，NTT）。
简要题意
给定一个长度为 n 的纸带，你需要用最多 m 种颜色给纸带的每一个位置染色。
若有 k 种颜色恰好出现了 S 次，则会获得 W_k 的收益。你需要输出所有染色方案的收益总和。
答案对 1004535809 取模。
## 思路
首先考虑设 $f(z)$ 表示有 $z$ 种颜色恰好出现 $S$ 次的方案数，则答案就是：
$$
\sum_{i=0}^{m}W_if(i)
$$
求 $f(z)$ 不妨考虑生成函数。我们将颜色分为恰好出现 $S$ 次的（下面成为关键色）以及恰好出现非 $S$ 次的（下面称为一般色）。由于纸带染色问题属于有标号体系，所以我们需要使用 EGF。
先构造关键色的生成函数：
$$
\hat{\mathbf{F}}_1 = \frac{x^S}{S!}
$$
然后是一般色的生成函数：
$$
\hat{\mathbf{F}}_0=-\frac{x^S}{S!}+\sum_{k=0}^{+\infty} \frac{x^k}{k!}=e^x-\frac{x^S}{S!}
$$
则有：
$$
f(z)=\binom{m}{z}\cdot n!\cdot [x^n]\left(\left(\hat{\mathbf{F}}_1\right)^z\cdot \left(\hat{\mathbf{F}}_0\right)^{m-z}\right)
$$
然后就是大力化式子，先考虑化简后面的多项式：
$$
\begin{aligned}
&\left(\hat{\mathbf{F}}_1\right)^z\cdot \left(\hat{\mathbf{F}}_0\right)^{m-z}\\
&=\left(\frac{x^S}{S!}\right)^z\cdot \left(e^x-\frac{x^S}{S!}\right)^{m-z}\\
&=\frac{x^{Sz}}{(S!)^z}\cdot \sum_{k=0}^{m-z}\binom{m-z}{k}e^{xk}\frac{x^{Sm-Sz-Sk}}{(S!)^{m-z-k}}(-1)^{m-k-z}\\
&=\sum_{k=0}^{m-z}\binom{m-z}{k}e^{xk}\frac{x^{Sm-Sk}}{(S!)^{m-k}}(-1)^{m-k-z}\\
&=\sum_{k=0}^{m-z}\binom{m-z}{k}\frac{x^{Sm-Sk}}{(S!)^{m-k}}(-1)^{m-k-z}\sum_{t=0}^{+\infty}\frac{k^t}{t!}x^t
\end{aligned}
$$
考虑它的 $x^n$ 项系数到底是什么，不难发现需要满足 $S(m-k)+t=n$，也就是 $t=n-S(m-k)$，代入：
$$
\begin{aligned}
&[x^n]\sum_{k=0}^{m-z}\binom{m-z}{k}\frac{x^{Sm-Sk}}{(S!)^{m-k}}(-1)^{m-k-z}\sum_{t=0}^{+\infty}\frac{k^t}{t!}x^t\\
&=\sum_{k=0}^{m-z}\binom{m-z}{k}\frac{k^{n-S(m-k)}(-1)^{m-k-z}}{(n-S(m-k))!(S!)^{(m-k)}}\\
&=(m-z)!\sum_{k=0}^{m-z}\frac{k^{n-S(m-k)}(-1)^{m-k-z}}{(n-S(m-k))!(S!)^{(m-k)}(m-k-z)!k!}
\end{aligned}
$$
换元，令 $k\leftarrow m-k$，得：
$$
(m-z)!\sum_{k=z}^{m}\frac{(m-k)^{n-Sk}(-1)^{k-z}}{(n-Sk)!(S!)^{k}(k-z)!(m-k)!}
$$
令：
$$
g(k)= \frac{(m-k)^{n-Sk}}{(n-Sk)!(m-k)!(S!)^k}
$$
则得到：
$$
\begin{aligned}
&(m-z)!\sum_{k=z}^{m}\frac{(m-k)^{n-Sk}(-1)^{k-z}}{(n-Sk)!(S!)^{k}(k-z)!(m-k)!}\\
&=(m-z)!\sum_{k=z}^{m}\frac{(-1)^{k-z}}{(k-z)!}g(k)
\end{aligned}
$$
改为枚举 $k-z$ 得：
$$
\begin{aligned}
&(m-z)!\sum_{k=z}^{m}\frac{(-1)^{k-z}}{(k-z)!}g(k)\\
&=(m-z)!\sum_{k=0}^{m}\frac{(-1)^k}{k!}g(k+z)
\end{aligned}
$$
令 $g'(k)=g(m-k)$，得：
$$
\begin{aligned}
&(m-z)!\sum_{k=0}^{m}\frac{(-1)^k}{k!}g(k+z)\\
&=(m-z)!\sum_{k=0}^{m}\frac{(-1)^k}{k!}g'((m-z)-k)
\end{aligned}
$$
最终得到：
$$
f(z)=\binom{m}{z}n!(m-z)!\sum_{k=0}^{m}\frac{(-1)^k}{k!}g'((m-z)-k)
$$
注意到后面那个式子可以看成一个卷积形式，答案就是卷积的 $x^{m-z}$ 项系数。因此我们可以构造两个多项式，一遍多项式卷积就可以求出后面那个和式的值。
时间复杂度 $O(n+m\log m)$。
## 代码
多项式模板过长，已经省略，下面展示核心代码：
```cpp
int n, m, s, fact[N], inv[N], w[N];
int binom(int x, int y){ return Mul(fact[x], Mul(inv[y], inv[x - y])); }
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin >> n >> m >> s;
for(int i=0;i<=m;i++) cin >> w[i];
fact[0] = fact[1] = inv[0] = inv[1] = 1;
for(int i=2;i<=max(n, m);i++){
fact[i] = Mul(fact[i-1], i);
inv[i] = Mul(mod - mod / i, inv[mod % i]);
}
for(int i=2;i<=max(n, m);i++) inv[i] = Mul(inv[i], inv[i-1]);
Poly poly(m + 1);
for(int k=0;k<=m;k++){
if(n - 1ll * s * k < 0) continue;
int tmp = fastpow(m - k, n - 1ll * s * k);
tmp = Mul(tmp, inv[n - 1ll * s * k]);
tmp = Mul(tmp, inv[m - k]);
tmp = Mul(tmp, fastpow(inv[s], k));
poly[k] = tmp;
}
reverse(poly.a.begin(), poly.a.end());
Poly poly2(m + 1);
for(int k=0;k<=m;k++){
int tmp = inv[k];
if(k & 1) tmp = mod - tmp;
poly2[k] = tmp;
}
poly = poly * poly2;
int ans = 0;
for(int i=0;i<=m;i++){
int tmp = Mul(fact[m - i], fact[n]);
tmp = Mul(tmp, poly[m - i]);
tmp = Mul(tmp, binom(m, i));
tmp = Mul(tmp, w[i]);
ans = Add(ans, tmp);
}
cout << ans << '\n';
return 0;
}
// Written by xiezheyuan
```