多项式计数

多项式计数

斯特林数快速计算

第二类斯特林数

{nm} 表示 n 个数划分成 m 个集合的方案数量,那么简单的,使用 O(n2) 可得递推式:

{nm}={n1m1}+m{n1m}

边界情况是 {n0}=[n=0]

第二类斯特林数·行

考虑在 O(nlogn) 内得到所有 {ni}(1in) 的值,我们需要知道第二类斯特林数二项式反演(容斥)的公式:

{nm}=mi=0(1)miini!(mi)!

Gi 表示 i 个盒子可以为空的方案,简单的,为 in,然后 Fi 表示 i 个盒子不可以为空的方案,那么有:

Fi=ij=0(1)ijCjiGj=ij=0(1)iji!jnj!(ij)!

答案就是 Fmm!(盒子之间有序),所以分子的阶乘就没有了。

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

代码 here

第二类斯特林数·列

现在我们需要快速求出 {im}(0in)

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

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

于是时间复杂度为 O(nlogn)

代码 here

第一类斯特林数

[nm] 表示 n 个数划分成 m 个圆排列的方案数量,那么简单的,使用 O(n2) 可得递推式:

[nm]=[n1m1]+(n1)[n1m]

边界情况是 [n0]=[n=0]

第一类斯特林数·行

首先设一行的生成函数为 Fi(x),那么由普通的转移方程得到 Fn(x)=(n1)Fn1(x)+xFn1(x),所以 Fn(x)=n1i=0(x+i)=x¯n,这被称作 x 的上升幂,同时还有 x 的下降幂,因为两者比较相似,此处不做展开。

考虑如何计算 x¯n 的各项系数,我们可以倍增先计算 x¯n 再计算 x¯2n

x¯2n=x¯n(x+n)¯n

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

f(x+c)=ifi(x+c)i=jxjifiCjicij=jxj1j!ifii!(ij)!cij

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

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

代码 here

第一类斯特林数·列

现在我们需要快速求出 [im](0in)

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

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

于是时间复杂度为 O(nlogn)

代码 here

集合划分计数

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

fi=ij=1Cj1i1fij

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

代码 here

连通图计数

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

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

fi=2i(i1)2i1j=1fjCj1i12(ij)(ij1)2=2i(i1)2(i1)!i1j=1fj(j1)!2(ij)(ij1)2(ij)!

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

代码 here

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

多项式 ln 代码 here

多项式求逆:

fi+(i1)!i1j=1fj(j1)!2(ij)(ij1)2(ij)!=2i(i1)2ij=1fj(j1)!2(ij)(ij1)2(ij)!=2i(i1)2(i1)!

于是设 F(x)=ifi(i1)!xi,G(x)=i2i(i1)2i!xi,H(x)=i2i(i1)2(i1)!xiF 的下标从 1 开始;G 的下标从 0 开始,H 的下标从 1 开始。

所以 F=HG1,用一次多项式求逆+多项式乘法即可。

多项式求逆代码 here

边双连通分量计数

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

一个比较简单的做法就是容斥+prufer 序的性质 ki=1ai(ki=1ai)k2 即可。

于是我们可以设 gi,j 表示 i 个点有 j 个边双连通分量的答案,最后的答案就是 m+1k=1gn,k

首先考虑算出来 gi,j(j2),然后用 gi,1=fiij=2gi,j 求出 gi,1。(fi 表示 i 个节点的连通图数量)

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

gi,j(j2)=i1k=1gk,1Ck1i1×opt

opt 是上文中我们提到的 ki=1ai(ki=1ai)k2,因为 a 不好记录,所以还要再设 hi,j 为所有可能的情况中 ki=1ai 的乘积的和,根据乘法分配律和结合律,得到:

hi,j(j2)=i1k=1hik,j1gk,1Ck1i1k

最后根据 h 还原出来 ggi,j=hi,jij2),最后容斥出来 gi,1 即可。

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

代码 here

有标号 DAG 计数

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

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

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

fi=ij=1(1)j+1Cjifij2j(ji)

因为 j(ji)=C2iC2jC2ij,所以有:

fi=2C2ii!ij=1(1)j+1j!2C2jfij(ij)!2C2ij

于是我们可以分治 NTT 解决,我们发现,这个分治 NTT 是完全 fi=ij=1gjfij(已知 gf)的形式,因此可以用多项式求逆 F1=1G 解决。

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

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

代码 here

Update:使用多项式 ln

有标号二分图计数

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

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

最后设 h(i) 表示 i 个节点给二分图染色之后的染色+图的方案数量,容易发现 hi=ij=0Cji2j(ij),这个可以用 NTT 快速得到。

推导:

hi=i!2i(i1)2ij=01j!2j(j1)21(ij)!2(ij)(ij1)2

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

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

代码 here