第一类斯特林数 [nm] ，将 n 个元素划分为 m 个圆排列的方案数。 递推 递推式可以枚举最后一个元素是否放一个新的排列：[nm]=[n−1m−1]+(n−1)×[n−1m] 下面用 s(n,m) 表示 [nm]。 性质 n!=∑i=0ns(n,i) 证明：考虑其组合意义。一个排列唯一对应一个置换，而一个置换唯一对应一组轮换。比如排列 (1,5,2,3,4)，就可以看作轮换组 [1][2,5,4][3]。如果两个排列不同，那他们对应的轮换中，必定有一个元素的下一个元素不同，故排列与轮换一一对应。所以等式右侧的式子就是有 0∼n 个轮换的方案数。 求法 现在要快速求出第一类斯特林数的某一行。 直接给出定义，s(n,∗) 这东西的生成函数等于 ∏i=0n−1(x+i)，也就是 x 的 n 次上升幂。 于是就可以分治NTT来求了，复杂度 O(nlog2n)。具体实现用vector比较好写。 当然也可以 O(nlogn)。 令 Fn(x)=∏i=0n−1(x+i)，则F2n(x)=Fn(x)×Fn(x+n)。 考虑如何用 Fn(x) 快速求出 Fn(x+n)。 设 Fn(x)=∑i=0n−1aixi Fn(x+n)====∑i=0nai(x+n)i∑i=0nai×∑j=0iCjini−jxj∑i=0nxi×∑j=inCijnj−iaj∑i=0nxi×∑j=inj!i!(j−i)!nj−iaj 所以设 Fn(x+n)=∑i=0n−1bixi,ci=i!×ai,di=nii! ，那么 bi×i!=∑jcj×dj−i 把 d 翻转以后是一个标准的卷积式子，直接倍增就好了。 实现的小细节就是，如果当前长度 len 为奇数，不能除以 2 ，所以直接递归 len−1 ，然后回来之后乘上 (x+len−1) 就行了。 当你走进这欢乐场https://www.cnblogs.com/YoungNeal/p/10366962.html