2026/06/09
P5401 [CTS2019] 珍珠
题意：\(n\) 点，\(D\) 种颜色，要求出现次数为奇数的颜色种数 \(\leqslant n-2m\)，问染色方案数。
对颜色种数二项式反演，\(f_i\) 表示恰好 \(i\) 个奇数，\(g_i\) 表示钦定 \(i\) 个奇数，则 \(f_i=\sum_{j=i}^D\binom ji(-1)^{j-i}g_j=\frac1{i!}\sum_{j=i}^D\frac{(-1)^{j-i}}{(j-i)!}\cdot j!g_j\) 为差卷积形式。
对于 \(g_k\)，有：
\[\begin{aligned}
g_k&=\binom Dkn^k(\sum_{i=0}^{\infty}\frac1{i!}x^i)^{D-k}\\
&=\frac{D!n!}{k!(D-k)!}[x^n]\left(\frac{e^x-e^{-x}}2\right)^k\left(e^x\right)^{D-k}\\
&=\frac{D!n!}{2^kk!(D-k)!}[x^n]\left(e^x-e^{-x}\right)^k\left(e^x\right)^{D-k}\\
&=\frac{D!n!}{2^kk!(D-k)!}[x^n]\sum_{i=0}^k\binom ki(-1)^{k-i}e^{x(D+2i-2k)}\\
&=\frac{D!n!}{2^kk!(D-k)!}[x^n]\sum_{i=0}^k\binom ki(-1)^ie^{x(D-2i)}\\
&=\frac{D!n!}{2^kk!(D-k)!}[x^n]\sum_{i=0}^k\frac{k!}{i!(k-i)!}(-1)^ie^{x(D-2i)}\\
&=\frac{D!n!}{2^k(D-k)!}[x^n]\sum_{i=0}^k\frac{(-1)^ie^{x(D-2i)}}{i!}\cdot\frac1{(k-i)!}\\
&=\frac{D!}{2^k(D-k)!}\sum_{i=0}^k\frac{(-1)^i(D-2i)^n}{i!}\cdot\frac1{(k-i)!}\\
\end{aligned}
\]
这个为和卷积形式，总时间复杂度 \(O(D\log D)\)。Submission.