斯特林数快速计算

第二类斯特林数

设 $\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。