一道很有价值的容斥题

· · 个人记录

有必要记录一下今天模拟赛的 C 题。题目链接。本文同步作为“对树边容斥”一类技巧的解释及例题分析。

\text{题意}

给定一棵 n 个节点的树，你需要用 m 种颜色去给每个节点染色，要求相邻点颜色不同。再给出一些关键点，一个染色方案 c 的价值 F(c) 为所有关键点的颜色集合的大小，求所有合法染色方案的 F(c)^k 之和。对 998244353 取模。n,m\le10^5,k\le400，关键点个数与 n 同级。

\text{初步思考}

容斥，即 S=U-U\backslash S，用无意见减去反对意见。

考虑相邻点颜色不同这个限制，如果我们只要求合法染色方案数，应该怎么做呢？从上往下考虑，答案显然是 m(m-1)^{n-1}。如果有一些额外的限制，使得这个公式用不了，那么我们可以考虑对边及其相邻的点进行容斥，将二者颜色不同容斥成二者之间无限制减去二者颜色相等，颜色相等的话可以缩成一个连通块一起考虑颜色，无限制则相当于断边，各自考虑。可以设 f_u 表示以 u 为根的子树的方案数，且暂时不考虑 u 所在连通块的颜色（因为还可能继续拓展），考虑转移一个子树 v，则有：

\bullet$ 断边，无意见：$f_u*mf_v\to f_u \bullet$ 加入连通块，反对意见：$f_u*f_v*(-1)\to f_u

最终 mf_{root} 即为答案。

\text{转化}

这道题有两种转化，但殊途同归。对于贡献形式为某种元素的次幂，可以考虑以下两种方式。

\text{method 1}

考虑使用斯特林数，将次幂转化成下降幂或者组合数，公式为：x^k=\sum_{i=0}^ki!\binom{x}{i}S(k,i)。其中 S(k,i) 为第二类斯特林数，意为将 k 个有标号的小球放入 i 个无标号的盒子中的方案数。

那么题目即求：

\sum_cF(c)^k=\sum_c\sum_{i=0}^ki!S(k,i)\binom{F(c)}{i}\\=\sum_{i=0}^ki!S(k,i)\sum_c\binom{F(c)}{i}

那么就转化成了钦定 i 种颜色必须在关键点集中各出现至少一次的方案数 f_i。上式中的 \sum_c\binom{F(c)}{i} 可以写成 \binom{m}{i}f_i。则 ans=\sum_{i=0}^ki!S(k,i)\binom{m}{i}f_i。

\text{method 2}

考虑 F(c)^k 的组合意义，我们将 F(c) 中出现过的颜色都拿出来，那么其组合意义为：从这些出现过的颜色中，有顺序可重复地选出 k 个颜色。那么我们枚举选完 k 次之后的选出来的颜色集合，设大小为 i，这一步方案是 \binom{F(c)}{i}，考虑这个集合能被数到多少次（因为是有顺序可重复，所以一种集合会被多次数到），由于这 i 个元素必须至少出现一次，那么我们考虑容斥，设这 i 个颜色中有 j 中颜色没有出现，剩下 i-j 中颜色无限制，那么该集合会被数到 \sum_{j=0}^i\binom{i}{j}(-1)^j(i-j)^k(其实这个过程就相当于将 k 个小球放进 i 个有标号盒子中，这个式子就等于 i!S(k,i)。)。那么有：

ans=\sum_c\sum_{i=0}^k\binom{F(c)}{i}\sum_{j=0}^i\binom{i}{j}(-1)^j(i-j)^k\\=\sum_{i=0}^k\sum_{j=0}^i\binom{i}{j}(-1)^j(i-j)^k\sum_c\binom{F(c)}{i}\\=\sum_{i=0}^ki!S(k,i)\binom{m}{i}f_i

那么我们用两种不同的方式将题意转化成了：求钦定 i 种颜色必须在关键点集中各出现至少一次的方案数 f_i。

\text{求解}

我们考虑求解所有的 f_i,i\in[0,k]。这需要我们在最外层枚举 i。

跟刚刚组合意义推导类似，我们无法记录哪些元素出现过。考虑容斥，某元素至少出现过一次的方案数，等于无限制方案数减去该元素不出现的方案数。考虑设 g_j 表示钦定的 i 种颜色中，容斥了 j 种颜色不出现在关键点集中的方案数（可能有其他的元素未出现，但根据容斥，那些是被我们判定成无限制的一部分，所以不是恰好 j 个未出现）。那么 f_i=\sum_{j=0}^i(-1)^j\binom{i}{j}g_j。

那么我们需要求解 g_j。现在的限制有：关键点集有 j 种元素不能选，其他点任选，相邻点颜色要求不同。

沿用我们在初步思考时的思路。由于有关键点的存在，一个连通块的染色方案数取决于连通块中是否含有关键点，因此我们设 t_{i,0/1} 表示 i 所在连通块中是/否含有关键点的染色方案数。当在点 u 时，考虑从 v 子树的转移，仍然是分当前边的是无限制还是反对，也即考虑断边还是加入连通块。注意我们断边时，要注意给 v 所在连通块分配颜色，因为我们的状态中时尚未考虑 u 处的染色情况的。这一步复杂度 O(n)。

\text{统计}

求出了最底层的 g_j 后，我们便可以一路倒退，O(k^2) 求出 f_i，再 O(k^2) 求出我们的最终答案。其中斯特林数和组合数都是可以预处理的。总复杂度 O(nk+k^2)。

\text{总结}

从这一题获得的收获很多。包括：

$\bullet$ 容斥的基本思路与原理。 $\bullet$ “值的次幂”贡献形式的组合意义套路及斯特林数将次幂转化为组合数、斯特林数的套路。 $\bullet$ 加强了对第二类斯特林数的理解。 感觉我对于容斥的理解更深了，也能更熟练地使用容斥这个工具。感谢 lrz 在这道题上对我的教导。