多项式计数
斯特林数快速计算
第二类斯特林数
设 {nm} 表示 n 个数划分成 m 个集合的方案数量,那么简单的,使用 O(n2) 可得递推式:
{nm}={n−1m−1}+m{n−1m}
边界情况是 {n0}=[n=0]。
第二类斯特林数·行
考虑在 O(nlogn) 内得到所有 {ni}(1≤i≤n) 的值,我们需要知道第二类斯特林数二项式反演(容斥)的公式:
{nm}=m∑i=0(−1)m−iini!(m−i)!
即 Gi 表示 i 个盒子可以为空的方案,简单的,为 in,然后 Fi 表示 i 个盒子不可以为空的方案,那么有:
Fi=i∑j=0(−1)i−jCjiGj=i∑j=0(−1)i−ji!jnj!(i−j)!
答案就是 Fmm!(盒子之间有序),所以分子的阶乘就没有了。
于是我们可以用 NTT 快速计算。
第二类斯特林数·列
现在我们需要快速求出 {im}(0≤i≤n)。
首先不考虑盒子的顺序,最后除以 m! 即可。考虑只有一个盒子的上面式子的指数型生成函数 EGF 为 F(x)=∑ni=1xii!,那么 m 个盒子的指数型生成函数就是 Fm(x),第 n 项就是 [xn]Fm(x),最后算出答案之后需要根据指数型生成函数的定义乘上 n! 即可。
上面的 Fm(x) 不能使用 O(nlog2n) 暴力快速幂计算,因为次数总和超过了 n,所以必须使用多项式 ln/exp 的方式计算。
于是时间复杂度为 O(nlogn)。
第一类斯特林数
设 [nm] 表示 n 个数划分成 m 个圆排列的方案数量,那么简单的,使用 O(n2) 可得递推式:
[nm]=[n−1m−1]+(n−1)[n−1m]
边界情况是 [n0]=[n=0]。
第一类斯特林数·行
首先设一行的生成函数为 Fi(x),那么由普通的转移方程得到 Fn(x)=(n−1)Fn−1(x)+xFn−1(x),所以 Fn(x)=∏n−1i=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=∑jxj∑ifiCjici−j=∑jxj1j!∑ifii!(i−j)!ci−j
于是这一部分就可以倍增+多项式乘法解决,整体来说也可以通过类似于这种方式得到解法,时间复杂度 T(n)=T(n2)+O(nlogn)=O(nlogn)。
注意:倍增的时候每次 +1 或者 ×2 直接计算会少 2 倍常数。
第一类斯特林数·列
现在我们需要快速求出 [im](0≤i≤n)。
首先不考虑盒子的顺序,最后除以 m! 即可。考虑只有一个盒子的上面式子的指数型生成函数 EGF 为 F(x)=∑ni=1(i−1)!xii!=∑ni=1xii,那么 m 个盒子的指数型生成函数就是 Fm(x),第 n 项就是 [xn]Fm(x),最后算出答案之后需要根据指数型生成函数的定义乘上 n! 即可。
上面的 Fm(x) 也不能使用 O(nlog2n) 暴力快速幂计算,因为次数总和超过了 n,所以必须使用多项式 ln/exp 的方式计算。
于是时间复杂度为 O(nlogn)。
集合划分计数
设 fi 表示 i 个元素划分集合的方案数,转移的时候枚举第一个元素所在集合大小即可:
fi=i∑j=1Cj−1i−1fi−j
于是把 C 展开就可以简单地使用分治 NTT 计算了。
连通图计数
给定 n 计算大小为 n 的无向连通图的数量。
设 fi 表示大小为 i 的无向连通图的数量,有容斥:
fi=2i(i−1)2−i−1∑j=1fjCj−1i−12(i−j)(i−j−1)2=2i(i−1)2−(i−1)!i−1∑j=1fj(j−1)!2(i−j)(i−j−1)2(i−j)!
那么最后的东西也可以使用分治 NTT 快速计算,当然也可以用多项式 ln 做到单 log,代码是分治双 log 的。
多项式 ln 做法:根据多项式 exp 的定义就可以推断,注意,我们先要对总的 g(gi 表示 i 个点的任意无向图)进行求指数生成函数,然后 f 的指数生成函数就是 g 的指数生成函数的 ln。也就是最开始和结尾需要分别除以或者乘上阶乘。
多项式求逆:
fi+(i−1)!i−1∑j=1fj(j−1)!2(i−j)(i−j−1)2(i−j)!=2i(i−1)2i∑j=1fj(j−1)!2(i−j)(i−j−1)2(i−j)!=2i(i−1)2(i−1)!
于是设 F(x)=∑ifi(i−1)!xi,G(x)=∑i2i(i−1)2i!xi,H(x)=∑i2i(i−1)2(i−1)!xi,F 的下标从 1 开始;G 的下标从 0 开始,H 的下标从 1 开始。
所以 F=HG−1,用一次多项式求逆+多项式乘法即可。
边双连通分量计数
给定 n,m 求出边双连通分量小于等于 m+1 的图的个数。
一个比较简单的做法就是容斥+prufer 序的性质 ∏ki=1ai(∑ki=1ai)k−2 即可。
于是我们可以设 gi,j 表示 i 个点有 j 个边双连通分量的答案,最后的答案就是 ∑m+1k=1gn,k。
首先考虑算出来 gi,j(j≥2),然后用 gi,1=fi−∑ij=2gi,j 求出 gi,1。(fi 表示 i 个节点的连通图数量)
老套路枚举和 i 在同一个连通块的点数,然后用组合数计算剩下的内容就可以了,具体而言:
gi,j(j≥2)=i−1∑k=1gk,1Ck−1i−1×opt
opt 是上文中我们提到的 ∏ki=1ai(∑ki=1ai)k−2,因为 a 不好记录,所以还要再设 hi,j 为所有可能的情况中 ∏ki=1ai 的乘积的和,根据乘法分配律和结合律,得到:
hi,j(j≥2)=i−1∑k=1hi−k,j−1gk,1Ck−1i−1k
最后根据 h 还原出来 g(gi,j=hi,jij−2),最后容斥出来 gi,1 即可。
时间复杂度为 O(n3)。还有更加优秀的做法,此处不展开。
有标号 DAG 计数
给定 n 个点,求出 n 个点有标号的弱连通 DAG 数量。
首先我们需要求出 n 个点的 DAG 数量,然后按照连通图计数的方法求出弱连通 DAG 数量即可。
首先我们枚举入度为 0 的节点,结合上有向无环图的容斥公式,有:
fi=i∑j=1(−1)j+1Cjifi−j2j(j−i)
因为 j(j−i)=C2i−C2j−C2i−j,所以有:
fi=2C2ii!i∑j=1(−1)j+1j!2C2jfi−j(i−j)!2C2i−j
于是我们可以分治 NTT 解决,我们发现,这个分治 NTT 是完全 fi=∑ij=1gjfi−j(已知 g 求 f)的形式,因此可以用多项式求逆 F−1=1−G 解决。
最后再次分治 NTT 或者多项式 ln 即可。
代码使用的是普通的分治 NTT。
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(i−j),这个可以用 NTT 快速得到。
推导:
hi=i!2i(i−1)2i∑j=01j!2j(j−1)21(i−j)!2(i−j)(i−j−1)2
又因为 F 的每个连通块都会在 H 中计算两次(最小编号的点可以染色 0/1,剩下的点都确定了),所以设 F′(x)=2F(x),那么 H(x)=eF′(x)=e2F(x)=(eF(x))2=G2(x)。
于是把 H 算出来,然后用多项式开根求 G 即可(最后要乘上阶乘)。