多项式计数

多项式计数

斯特林数快速计算

第二类斯特林数

设 $\begin{Bmatrix} n \\ m\end{Bmatrix}$ 表示 $n$ 个数划分成 $m$ 个集合的方案数量,那么简单的,使用 $O(n^2)$ 可得递推式:

$$
\begin{Bmatrix} n \\ m\end{Bmatrix} = \begin{Bmatrix} n-1 \\ m-1\end{Bmatrix}+m\begin{Bmatrix} n-1 \\ m\end{Bmatrix}
$$

边界情况是 $\begin{Bmatrix} n \\ 0\end{Bmatrix}=[n=0]$。

第二类斯特林数·行

考虑在 $O(n \log n)$ 内得到所有 $\begin{Bmatrix} n \\ i\end{Bmatrix}(1 \le i \le n)$ 的值,我们需要知道第二类斯特林数二项式反演(容斥)的公式:

$$
\begin{Bmatrix} n \\ m\end{Bmatrix} = \sum_{i=0}^m \dfrac{(-1)^{m-i}i^n}{i!(m-i)!}
$$

即 $G_i$ 表示 $i$ 个盒子可以为空的方案,简单的,为 $i^n$,然后 $F_i$ 表示 $i$ 个盒子不可以为空的方案,那么有:

$$
\begin{aligned}
F_i &= \sum_{j=0}^i (-1)^{i-j} C_i^j G_j \\
&= \sum_{j=0}^i \dfrac{(-1)^{i-j}i!j^n}{j!(i-j)!}
\end{aligned}
$$

答案就是 $\frac{F_m}{m!}$(盒子之间有序),所以分子的阶乘就没有了。

于是我们可以用 NTT 快速计算。

代码 here

第二类斯特林数·列

现在我们需要快速求出 $\begin{Bmatrix} i \\ m\end{Bmatrix}(0 \le i \le n)$。

首先不考虑盒子的顺序,最后除以 $m!$ 即可。考虑只有一个盒子的上面式子的指数型生成函数 EGF 为 $F(x)=\sum_{i=1}^{n} \frac{x^i}{i!}$,那么 $m$ 个盒子的指数型生成函数就是 $F^m(x)$,第 $n$ 项就是 $[x^n]F^m(x)$,最后算出答案之后需要根据指数型生成函数的定义乘上 $n!$ 即可。

上面的 $F^m(x)$ 不能使用 $O(n \log^2 n)$ 暴力快速幂计算,因为次数总和超过了 $n$,所以必须使用多项式 ln/exp 的方式计算。

于是时间复杂度为 $O(n \log n)$。

代码 here

第一类斯特林数

设 $\begin{bmatrix} n \\ m\end{bmatrix}$ 表示 $n$ 个数划分成 $m$ 个圆排列的方案数量,那么简单的,使用 $O(n^2)$ 可得递推式:

$$
\begin{bmatrix} n \\ m\end{bmatrix} = \begin{bmatrix} n-1 \\ m-1\end{bmatrix}+(n-1)\begin{bmatrix} n-1 \\ m\end{bmatrix}
$$

边界情况是 $\begin{bmatrix} n \\ 0\end{bmatrix}=[n=0]$。

第一类斯特林数·行

首先设一行的生成函数为 $F_i(x)$,那么由普通的转移方程得到 $F_n(x)=(n-1)F_{n-1}(x)+xF_{n-1}(x)$,所以 $F_n(x)=\prod_{i=0}^{n-1}(x+i)=x^{\overline{n}}$,这被称作 $x$ 的上升幂,同时还有 $x$ 的下降幂,因为两者比较相似,此处不做展开。

考虑如何计算 $x^{\overline{n}}$ 的各项系数,我们可以倍增先计算 $x^{\overline{n}}$ 再计算 $x^{\overline{2n}}$:

$$
x^{\overline{2n}}=x^{\overline{n}}(x+n)^{\overline{n}}
$$

于是问题变成了得知一个多项式 $f(x)$,我们现在想要知道 $f(x+c)$ 的表达式:

$$
\begin{aligned}
f(x+c)&=\sum_i f_i(x+c)^i \\
&=\sum_j x^j \sum_i f_i C_i^j c^{i-j} \\
&= \sum_j x^j \frac 1 {j!}\sum_i f_i \frac{i!}{(i-j)!} c^{i-j}
\end{aligned}
$$

于是这一部分就可以倍增+多项式乘法解决,整体来说也可以通过类似于这种方式得到解法,时间复杂度 $T(n) = T(\frac n2)+O(n \log n)=O(n \log n)$。

注意:倍增的时候每次 $+1$ 或者 $\times 2$ 直接计算会少 $2$ 倍常数。

代码 here

第一类斯特林数·列

现在我们需要快速求出 $\begin{bmatrix} i \\ m\end{bmatrix}(0 \le i \le n)$。

首先不考虑盒子的顺序,最后除以 $m!$ 即可。考虑只有一个盒子的上面式子的指数型生成函数 EGF 为 $F(x)=\sum_{i=1}^{n} (i-1)!\frac{x^i}{i!}=\sum_{i=1}^{n} \frac{x^i}{i}$,那么 $m$ 个盒子的指数型生成函数就是 $F^m(x)$,第 $n$ 项就是 $[x^n]F^m(x)$,最后算出答案之后需要根据指数型生成函数的定义乘上 $n!$ 即可。

上面的 $F^m(x)$ 也不能使用 $O(n \log^2 n)$ 暴力快速幂计算,因为次数总和超过了 $n$,所以必须使用多项式 ln/exp 的方式计算。

于是时间复杂度为 $O(n \log n)$。

代码 here

集合划分计数

设 $f_i$ 表示 $i$ 个元素划分集合的方案数,转移的时候枚举第一个元素所在集合大小即可:

$$
f_i = \sum_{j=1}^i C_{i-1}^{j-1} f_{i-j}
$$

于是把 $C$ 展开就可以简单地使用分治 NTT 计算了。

代码 here

连通图计数

给定 $n$ 计算大小为 $n$ 的无向连通图的数量。

设 $f_i$ 表示大小为 $i$ 的无向连通图的数量,有容斥:

$$
\begin{aligned}
f_i &= 2^{\frac{i(i-1)}{2}}-\sum_{j=1}^{i-1} f_j C_{i-1}^{j-1}2^{\frac{(i-j)(i-j-1)}{2}} \\
&= 2^{\frac{i(i-1)}{2}}-(i-1)!\sum_{j=1}^{i-1} \frac{f_j}{(j-1)!} \frac{2^{\frac{(i-j)(i-j-1)}{2}}}{(i-j)!} \\
\end{aligned}
$$

那么最后的东西也可以使用分治 NTT 快速计算,当然也可以用多项式 ln 做到单 $\log$,代码是分治双 $\log$ 的。

代码 here

多项式 ln 做法:根据多项式 exp 的定义就可以推断,注意,我们先要对总的 $g$($g_i$ 表示 $i$ 个点的任意无向图)进行求指数生成函数,然后 $f$ 的指数生成函数就是 $g$ 的指数生成函数的 ln。也就是最开始和结尾需要分别除以或者乘上阶乘。

多项式 ln 代码 here

多项式求逆:

$$
\begin{aligned}
f_i+(i-1)!\sum_{j=1}^{i-1} \frac{f_j}{(j-1)!} \frac{2^{\frac{(i-j)(i-j-1)}{2}}}{(i-j)!} &= 2^{\frac{i(i-1)}{2}} \\
\sum_{j=1}^{i} \frac{f_j}{(j-1)!} \frac{2^{\frac{(i-j)(i-j-1)}{2}}}{(i-j)!} &= \frac{2^{\frac{i(i-1)}{2}}}{(i-1)!} \\
\end{aligned}
$$

于是设 $F(x)=\sum_{i}\frac{f_i}{(i-1)!}x^i,G(x)=\sum_i \frac{2^{\frac{i(i-1)}{2}}}{i!}x^i,H(x)=\sum_i \frac{2^{\frac{i(i-1)}{2}}}{(i-1)!}x^i$,$F$ 的下标从 $1$ 开始;$G$ 的下标从 $0$ 开始,$H$ 的下标从 $1$ 开始。

所以 $F=HG^{-1}$,用一次多项式求逆+多项式乘法即可。

多项式求逆代码 here

边双连通分量计数

给定 $n,m$ 求出边双连通分量小于等于 $m+1$ 的图的个数。

一个比较简单的做法就是容斥+prufer 序的性质 $\prod_{i=1}^k a_i (\sum_{i=1}^k a_i)^{k-2}$ 即可。

于是我们可以设 $g_{i,j}$ 表示 $i$ 个点有 $j$ 个边双连通分量的答案,最后的答案就是 $\sum_{k=1}^{m+1} g_{n,k}$。

首先考虑算出来 $g_{i,j}(j \ge 2)$,然后用 $g_{i,1}=f_i-\sum_{j=2}^i g_{i,j}$ 求出 $g_{i,1}$。($f_i$ 表示 $i$ 个节点的连通图数量)

老套路枚举和 $i$ 在同一个连通块的点数,然后用组合数计算剩下的内容就可以了,具体而言:

$$
g_{i,j}(j \ge 2)= \sum_{k=1}^{i-1} g_{k,1}C_{i-1}^{k-1} \times opt
$$

$opt$ 是上文中我们提到的 $\prod_{i=1}^k a_i (\sum_{i=1}^k a_i)^{k-2}$,因为 $a$ 不好记录,所以还要再设 $h_{i,j}$ 为所有可能的情况中 $\prod_{i=1}^k a_i$ 的乘积的和,根据乘法分配律和结合律,得到:

$$
h_{i,j}(j \ge 2)= \sum_{k=1}^{i-1} h_{i-k,j-1}g_{k,1}C_{i-1}^{k-1} k
$$

最后根据 $h$ 还原出来 $g$($g_{i,j}=h_{i,j}i^{j-2}$),最后容斥出来 $g_{i,1}$ 即可。

时间复杂度为 $O(n^3)$。还有更加优秀的做法,此处不展开。

代码 here

有标号 DAG 计数

给定 $n$ 个点,求出 $n$ 个点有标号的弱连通 DAG 数量。

首先我们需要求出 $n$ 个点的 DAG 数量,然后按照连通图计数的方法求出弱连通 DAG 数量即可。

首先我们枚举入度为 $0$ 的节点,结合上有向无环图的容斥公式,有:

$$
f_i = \sum_{j=1}^i (-1)^{j+1} C_i^j f_{i-j}2^{j(j-i)}
$$

因为 $j(j-i)=C_i^2-C_j^2-C_{i-j}^2$,所以有:

$$
f_i = 2^{C_i^2}i!\sum_{j=1}^i \frac {(-1)^{j+1}}{j!2^{C_j^2}}\frac{f_{i-j}}{(i-j)!2^{C_{i-j}^2}}
$$

于是我们可以分治 NTT 解决,我们发现,这个分治 NTT 是完全 $f_i=\sum_{j=1}^i g_jf_{i-j}$(已知 $g$ 求 $f$)的形式,因此可以用多项式求逆 $F^{-1}=1-G$ 解决。

最后再次分治 NTT 或者多项式 ln 即可。

代码使用的是普通的分治 NTT。

代码 here

Update:使用多项式 ln

有标号二分图计数

首先我们设 $f(i)$ 表示 $i$ 个节点二分图连通的方案数,$F(x)$ 为其 EGF。容易发现 $f(0)=0$。

然后设 $g(i)$ 表示 $i$ 个节点二分图不一定连通的方案数,$G(x)$ 为其 EGF。容易发现 $G=e^F$。

最后设 $h(i)$ 表示 $i$ 个节点给二分图染色之后的染色+图的方案数量,容易发现 $h_i=\sum_{j=0}^i C_i^j 2^{j(i-j)}$,这个可以用 NTT 快速得到。

推导:

$$
\begin{aligned}
h_i &= i!2^{\frac{i(i-1)}{2}} \sum_{j=0}^i \frac{1}{j!2^{\frac{j(j-1)}2}} \frac{1}{(i-j)!2^{\frac{(i-j)(i-j-1)}2}}
\end{aligned}
$$

又因为 $F$ 的每个连通块都会在 $H$ 中计算两次(最小编号的点可以染色 $0/1$,剩下的点都确定了),所以设 $F’(x)=2F(x)$,那么 $H(x)=e^{F’(x)}=e^{2F(x)}=(e^{F(x)})^2=G^2(x)$。

于是把 $H$ 算出来,然后用多项式开根求 $G$ 即可(最后要乘上阶乘)。

代码 here