为啥写这篇文章

请移步这篇文章

boshi: 我有一个绝妙的思路和解释，不过尔等凡人听不懂

所以就有了这篇文章

然后这篇文章堪了一些 boshi 懒得改的已经更正的误

Problem

CSA

Solution

一道毒枭题，不同的状态可以得到不同复杂度的算法= =

为了防止歧义，我们约定一些变量的含义：$m$ 为球的不同颜色数，第 $i$ 种球有 $c_i$ 个，记 $n=\sum_{i=1}^m c_i$

记录非法的边数

让两个相邻且颜色相同的球连一条非法边。$f[i][j]$ 表示前 $i$ 种有 $j$ 条非法边的方案数，枚举拆开的非法边有 $l$ 个，第 $i$ 个元素被分成了 $t$ 段，那么有
$$f[i][k-l+c_i-t]=\sum_{k,l,t} f[i-1][k]\binom k l\binom {c_i-1} {t-1} \binom {n-k+1} {t-l}$$

复杂度的上界为 $O(n^3)$

记录各颜色球的个数，容斥计数

$g[n_1,n_2,\cdots,n_m]$ 表示第 $i$ 种球有 $n_i$ 个时，没有相邻元素的方案数

$f[n_1,n_2,\cdots,n_m]$ 表示第 $i$ 种球有 $n_i$ 个时，随意排的方案数，显然等于 $\frac {(\sum_{i=1}^m n_i)!} {\prod_{i=1}^m n_i!}$

用高维容斥即可得到
$$g[n_1,n_2,\cdots,n_m]=\sum_{a_i\leq n_i} (-1)^{\sum n_i-\sum a_i} \prod \binom {n_i} {a_i} \frac {(\sum a_i)!} {\prod a_i!}$$

$$=(-1)^{\sum n_i} \sum_{N=0}^{\sum n_i} (-1)^N N! \prod_{\sum a_i=N} \frac {\binom {n_i} {a_i}} {a_i!}$$

$\sum a_i=N$ 其实就是卷积，用分治 FFT 可以把时间复杂度优化至 $O(n\log^2 n)$

枚举颜色的段数，第 $i$ 种颜色的生成函数为：

$$F_i(x)=\sum_{j=1}^{c_i} \binom {c_i-1} {j-1}(-1)^{c_i-j}\frac {x^j} {j!}$$

要解释这个式子，需要反过来思考，从最终局面出发，枚举最终局面下的一种颜色被分成了多少段，然后把这个颜色全部删去，再考虑下一种颜色。其中 $(-1)^{c_i-j}$ 来源于这种颜色贡献的非法边。$[x^i]$ 项的系数表达的是分成 $i$ 段的方案数。

有另外一种解释的方法。每一项代表有多少段，只需要考虑各段之间的拼接即可，这个是 EGF。不难发现这个拼接过程并不能保证最终局面下的相邻颜色段是不同颜色。而所求的其实就是最后有 $n$ 段的方案数，因此我们仍然需要容斥，容斥系数即为 $(-1)^{n-i}$ 。这个本质就是 DP，卷积就描述了 DP 的过程。

用分治 FFT 同样可以做到 $O(n\log^2 n)$

不难发现第二种和第一种的生成函数卷积出来的第 $i$ 项的容斥系数是一致的，这两种容斥是殊途同归的。

于是乎这个生成函数就可以把容斥系数给去掉了，虽然叫 “带容斥系数的生成函数” 似乎有点名不副其实。

队长：这为啥不能叫 “带容斥系数的生成函数”，不然分治 FFT 的名字是怎么来的……