第一类斯特林数
(egin{bmatrix}n\mend{bmatrix}) ,将 (n) 个元素划分为 (m) 个圆排列的方案数。
递推
递推式可以枚举最后一个元素是否放一个新的排列:(egin{bmatrix}n\mend{bmatrix}=egin{bmatrix}n-1\m-1end{bmatrix}+(n-1) imes egin{bmatrix}n-1\mend{bmatrix})
下面用 (s(n,m)) 表示 (egin{bmatrix}n\mend{bmatrix})。
性质
证明:考虑其组合意义。一个排列唯一对应一个置换,而一个置换唯一对应一组轮换。比如排列 ((1,5,2,3,4)),就可以看作轮换组 ([1][2,5,4][3])。如果两个排列不同,那他们对应的轮换中,必定有一个元素的下一个元素不同,故排列与轮换一一对应。所以等式右侧的式子就是有 $0sim n $ 个轮换的方案数。
求法
现在要快速求出第一类斯特林数的某一行。
直接给出定义,(s(n,*)) 这东西的生成函数等于 (prodlimits_{i=0}^{n-1} (x+i)),也就是 (x) 的 (n) 次上升幂。
于是就可以分治(mathrm{NTT})来求了,复杂度 (O(nlog^2 n))。具体实现用(mathrm{vector})比较好写。
当然也可以 (O(nlog n))。
令 (F_n(x)=prodlimits_{i=0}^{n-1}(x+i)),则(F_{2n}(x)=F_n(x) imes F_n(x+n))。
考虑如何用 (F_n(x)) 快速求出 (F_{n}(x+n))。
设 (F_n(x)=sum_limits{i=0}^{n-1}a_ix^i)
所以设 (F_n(x+n)=sumlimits_{i=0}^{n-1} b_ix^i,c_i=i! imes a_i,d_i=frac{n^i}{i!}) ,那么
把 (d) 翻转以后是一个标准的卷积式子,直接倍增就好了。
实现的小细节就是,如果当前长度 (len) 为奇数,不能除以 (2),所以直接递归 (len-1) ,然后回来之后乘上 ((x+len-1)) 就行了。