知识点
知识点 - Stirling数
解决问题类型：
- 将p个物体排成k个圆排列(非空循环排列)的方法数。
- 从左往右会依次遇到A个比当前遇到的最大值更大的元素的排列的个数。（等价于上面的问题）
- 表示将n个不同的元素拆分成k个集合的方案数。
- 求泰勒展开系数
- 每条边的长度为1，对每个节点u，求 E u = ∑ v = 1 n ( d ( u , v ) ) k , E_u = \sum_{v=1}^n (d(u, v))^k, Eu=∑v=1n(d(u,v))k,
- 从n≤1e9个人中选取一个非空子集X，求所有可能的子集大小的次方之和即 ∣ X ∣ k |X|^k ∣X∣k，k≤5000（也可以二项式求导）
定义与结论：
第一类Stirling数
-
多项式 [ x ] n = x ( x − 1 ) ( x − 2 ) ⋅ ⋅ ⋅ ( x − n + 1 ) \left\lbrack x \right\rbrack_{n} = x\left( x - 1 \right)\left( x - 2 \right) \cdot \cdot \cdot \left( x - n + 1 \right) [x]n=x(x−1)(x−2)⋅⋅⋅(x−n+1)中常数项和 x , x 2 , x 3 , ⋅ ⋅ ⋅ , x n x,x^{2},x^{3}, \cdot \cdot \cdot ,x^{n} x,x2,x3,⋅⋅⋅,xn的系数称为带符号第一类Stirling数，记为 S s ( n , k ) , k = 0 , 2 , ⋅ ⋅ ⋅ , n S_{s}\left( n,k \right),k = 0,2, \cdot \cdot \cdot ,n Ss(n,k),k=0,2,⋅⋅⋅,n. 或 [ n k ] . \begin{bmatrix} n \\ k \end{bmatrix}. [nk].
相对的无符号的第一类Stirling数，记为 S u ( n , k ) S_{u}\left( n,k \right) Su(n,k).对应 [ x ] n = x ( x + 1 ) ( x + 2 ) ⋅ ⋅ ⋅ ( x + n − 1 ) \left\lbrack x \right\rbrack_{n} = x\left( x + 1 \right)\left( x + 2 \right) \cdot \cdot \cdot \left( x + n - 1 \right) [x]n=x(x+1)(x+2)⋅⋅⋅(x+n−1)
-
S s S_s Ss满足递归关系
{ S 1 ( n + 1 , k ) = S 1 ( n , k − 1 ) + n S 1 ( n , k ) , n ≥ 0 , k > 0 S 1 ( n , n ) = 1 , S 1 ( n , 0 ) = 0 \left\{ \begin{matrix} S_{1}\left( n + 1,k \right) = S_{1}\left( n,k - 1 \right) + nS_{1}\left( n,k \right),n \geq 0,k > 0 \\ S_{1}\left( n,n \right) = 1,S_{1}\left( n,0 \right) = 0 \\ \end{matrix} \right. {S1(n+1,k)=S1(n,k−1)+nS1(n,k),n≥0,k>0S1(n,n)=1,S1(n,0)=0$S_u$满足递归关系
{ S 1 ( n + 1 , k ) = S 1 ( n , k − 1 ) − n S 1 ( n , k ) , n ≥ 0 , k > 0 S 1 ( n , n ) = 1 , S 1 ( n , 0 ) = 0 \left\{ \begin{matrix} S_{1}\left( n + 1,k \right) = S_{1}\left( n,k - 1 \right) - nS_{1}\left( n,k \right),n \geq 0,k > 0 \\ S_{1}\left( n,n \right) = 1,S_{1}\left( n,0 \right) = 0 \\ \end{matrix} \right. {S1(n+1,k)=S1(n,k−1)−nS1(n,k),n≥0,k>0S1(n,n)=1,S1(n,0)=0 -
S u ( p , k ) S_u(p,k) Su(p,k)的一个的组合学解释是：将p个物体排成k个圆排列(非空循环排列)的方法数。
考虑第n+1个物品，如果它单独构成一个圆排列有 S 1 ( n , k − 1 ) S_1(n,k-1) S1(n,k−1)个方案，插入任意元素的左边有 n S 1 ( n , k ) nS_1(n,k) nS1(n,k)个方案。
-
∑ k = 0 n [ n k ] = n ! , \sum_{k=0}^n \begin{bmatrix} n \\ k \end{bmatrix} = n!, k=0∑n[nk]=n!,
s[0][0]=1;
for (register int i=1;i<maxn;++i) {for (register int j=1;j<=i;++j) {s[i][j]=(s[i-1][j-1]+((i-1)*s[i-1][j])%q)%q;}}
第二类Stirling数
-
多项式 [ x ] n = x ( x − 1 ) ( x − 2 ) ⋅ ⋅ ⋅ ( x − n + 1 ) \left\lbrack x \right\rbrack_{n} = x\left( x - 1 \right)\left( x - 2 \right) \cdot \cdot \cdot \left( x - n + 1 \right) [x]n=x(x−1)(x−2)⋅⋅⋅(x−n+1)， x n = ∑ k = 0 n S 2 ( n , k ) [ x ] k x^{n} = \sum_{k = 0}^{n}{S_{2}\left( n,k \right)\left\lbrack x \right\rbrack_{k}} xn=∑k=0nS2(n,k)[x]k，称 S 2 ( n , k ) S_{2}\left( n,k \right) S2(n,k)为第二类Stirling数。记为 { n k } . \begin{Bmatrix} n \\ k \end{Bmatrix}. {nk}.
-
组合学解释是:表示将n个不同的元素拆分成k个集合的方案数。
-
第二类Stirling数满足 S 2 ( n , k ) = 1 k ! ∑ i = 0 k − 1 ( − 1 ) i C k i ( k − i ) n S_{2}\left( n,k \right) = \frac{1}{k!}\sum_{i = 0}^{k - 1}{\left( - 1 \right)^{i}C_{k}^{i}\left( k - i \right)^{n}} S2(n,k)=k!1∑i=0k−1(−1)iCki(k−i)n
-
第二类Stirling数满足递归关系
{ S 2 ( n + 1 , k ) = S 2 ( n , k − 1 ) + k S 2 ( n , k ) , n ≥ 0 , k ≥ 1 S 2 ( 0 , 0 ) = 1 , S 2 ( n , 0 ) = 0 \left\{ \begin{matrix} S_{2}\left( n+1,k \right) = S_{2}\left( n,k - 1 \right) + kS_{2}\left( n,k \right),n \geq 0,k \geq 1 \\ S_{2}\left( 0,0 \right) = 1,S_{2}\left( n,0 \right) = 0 \\ \end{matrix} \right. {S2(n+1,k)=S2(n,k−1)+kS2(n,k),n≥0,k≥1S2(0,0)=1,S2(n,0)=0
$$ -
第二类Stirling数可以用卷积的方法求，根据（2）得 S 2 ( n , k ) = ∑ i = 0 k − 1 ( − 1 ) i i ! ( k − i ) n ( k − i ) ! S_2(n,k)=\sum_{i=0}^{k-1}\frac{(-1)^i}{i!}\frac{(k-i)^n}{(k-i)!} S2(n,k)=∑i=0k−1i!(−1)i(k−i)!(k−i)n ，对 a i = ( − 1 ) i i ! a_i=\frac{(-1)^i}{i!} ai=i!(−1)i 与 b i = i n i ! b_i=\frac{i^n}{i!} bi=i!in 卷积即可
-
∑ k = 0 n { n k } = B n , \sum_{k=0}^n \begin{Bmatrix} n \\ k \end{Bmatrix} = B_n, k=0∑n{nk}=Bn,
其中Bn是 Bell 数。
斯特林数与阶乘幂
我们定义下降幂（Falling Factorial）：
x n ‾ = x ( x − 1 ) ⋯ ( x − n + 1 ) . x^{\underline{n}} = x(x-1)\cdots (x-n+1). xn=x(x−1)⋯(x−n+1).
以及上升幂（Rising Factorial）：
x n ‾ = x ( x + 1 ) ⋯ ( x + n − 1 ) . x^{\overline{n}} = x(x+1)\cdots (x+n-1). xn=x(x+1)⋯(x+n−1).
则有以下等式，即上面的定义：
x n ‾ = ∑ k = 0 n ( − 1 ) n − k [ n k ] x k ⟺ x n = ∑ k = 0 n { n k } x k ‾ x n ‾ = ∑ k = 0 n [ n k ] x k ⟺ x n = ∑ k = 0 n ( − 1 ) n − k { n k } x k ‾ x n ‾ = ∑ k = 0 n L ( n , k ) x k ‾ ⟺ x n ‾ = ∑ k = 0 n ( − 1 ) n − k L ( n , k ) x k ‾ \begin{aligned} x^{\underline{n}} = \sum_{k=0}^n (-1)^{n-k} \begin{bmatrix} n \\ k \end{bmatrix} x^k & \Longleftrightarrow x^n = \sum_{k=0}^n \begin{Bmatrix} n \\ k \end{Bmatrix} x^{\underline{k}} \\ x^{\overline{n}} = \sum_{k=0}^n \begin{bmatrix} n \\ k \end{bmatrix} x^k & \Longleftrightarrow x^n = \sum_{k=0}^n (-1)^{n-k} \begin{Bmatrix} n \\ k \end{Bmatrix} x^{\overline{k}} \\ x^{\overline{n}} = \sum_{k=0}^n L(n, k) x^{\underline{k}} & \Longleftrightarrow x^{\underline{n}} = \sum_{k=0}^n (-1)^{n-k} L(n, k) x^{\overline{k}} \end{aligned} xn=k=0∑n(−1)n−k[nk]xkxn=k=0∑n[nk]xkxn=k=0∑nL(n,k)xk⟺xn=k=0∑n{nk}xk⟺xn=k=0∑n(−1)n−k{nk}xk⟺xn=k=0∑n(−1)n−kL(n,k)xk
其中：
L ( n , k ) = ∑ j [ n j ] { j k } = ( n − 1 k − 1 ) n ! k ! . L(n, k) = \sum_j \begin{bmatrix} n \\ j \end{bmatrix} \begin{Bmatrix} j \\ k \end{Bmatrix} = \binom{n-1}{k-1} \frac {n!} {k!}. L(n,k)=j∑[nj]{jk}=(k−1n−1)k!n!.
注：最常用的是将 x n x^n xn分成若干个 x k ‾ x^{\underline{k}} xk之和，或者是 ( x k ) \binom{x}{k} (kx)之和，即
x n = ∑ k = 0 n { n k } x k ‾ = ∑ k = 0 n k ! { n k } ( x k ) . x^n = \sum_{k=0}^n \begin{Bmatrix} n \\ k \end{Bmatrix} x^{\underline{k}} = \sum_{k=0}^n k! \begin{Bmatrix} n \\ k \end{Bmatrix} \binom{x}{k}. xn=k=0∑n{nk}xk=k=0∑nk!{nk}(kx).
stirling 反演
斯特林数和阶乘幂的关系可推广至一般函数：
g ( n ) = ∑ k = 0 n ( − 1 ) n − k [ n k ] f ( k ) ⟺ f ( n ) = ∑ k = 0 n { n k } g ( k ) g ( n ) = ∑ k = 0 n L ( n , k ) f ( k ) ⟺ f ( n ) = ∑ k = 0 n ( − 1 ) n − k L ( n , k ) g ( k ) \begin{aligned} g(n) = \sum_{k=0}^n (-1)^{n-k} \begin{bmatrix} n \\ k \end{bmatrix} f(k) & \Longleftrightarrow f(n) = \sum_{k=0}^n \begin{Bmatrix} n \\ k \end{Bmatrix} g(k) \\ g(n) = \sum_{k=0}^n L(n, k) f(k) & \Longleftrightarrow f(n) = \sum_{k=0}^n (-1)^{n-k} L(n, k) g(k) \end{aligned} g(n)=k=0∑n(−1)n−k[nk]f(k)g(n)=k=0∑nL(n,k)f(k)⟺f(n)=k=0∑n{nk}g(k)⟺f(n)=k=0∑n(−1)n−kL(n,k)g(k)
第一类斯特林数的快速求解
为快速计算 [ n k ] \begin{bmatrix} n \\ k \end{bmatrix} [nk]，我们利用
x n ‾ = ∑ k = 0 n [ n k ] x k . x^{\overline{n}} = \sum_{k=0}^n \begin{bmatrix} n \\ k \end{bmatrix} x^k. xn=k=0∑n[nk]xk.
令 f ( x ) = x n ‾ , g ( x ) = ( x + n ) n ‾ f(x) = x^{\overline{n}}, g(x) = (x+n)^{\overline{n}} f(x)=xn,g(x)=(x+n)n,则 f ( x ) g ( x ) = x 2 n ‾ f(x)g(x) = x^{\overline{2n}} f(x)g(x)=x2n。这样我们就能从 [ n k ] \begin{bmatrix} n \\ k \end{bmatrix} [nk] 得到 [ 2 n k ] \begin{bmatrix} 2n \\ k \end{bmatrix} [2nk] .
计算过程如下，设：
f ( x ) = ∑ k = 0 n a k x k , f(x) = \sum_{k=0}^n a_k x^k, f(x)=k=0∑nakxk,
则：
g ( x ) = ∑ k = 0 n a k ( x + n ) k = ∑ k = 0 n a k ∑ i = 0 k ( k i ) n k − i x i = ∑ k = 0 n 1 ( n − k ) ! x n − k ∑ i + j = k n i i ! a n − j ( n − j ) ! \begin{aligned} g(x) & = \sum_{k=0}^n a_k (x+n)^k \\ & = \sum_{k=0}^n a_k \sum_{i=0}^k \binom{k}{i} n^{k-i} x^i \\ & = \sum_{k=0}^n \frac{1} {(n-k)!} x^{n-k} \sum_{i+j=k} \frac{n^i}{i!} a_{n-j} (n-j)! \end{aligned} g(x)=k=0∑nak(x+n)k=k=0∑naki=0∑k(ik)nk−ixi=k=0∑n(n−k)!1xn−ki+j=k∑i!nian−j(n−j)!
就变成了卷积计算。每一次倍增用快速傅里叶变换则计算g(x)的时间复杂度为O(nlogn)。
总复杂度为 T ( n ) = T ( n / 2 ) + O ( n log n ) = O ( n log n ) T(n) = T(n/2)+O(n\log n)=O(n\log n) T(n)=T(n/2)+O(nlogn)=O(nlogn)
reference:
证明：百度百科 公式：liouzhou_101
复杂度：
递推的话是 O ( n 2 ) O(n^2) O(n2)
注意到第二类stirling数可以卷积,用FFT O ( n l o g n ) O(nlogn) O(nlogn)
第一类也可以构造出卷积， O ( n l o g n ) O(nlogn) O(nlogn)
例题
Count the Buildings给你一个n，表示有n个高度分别为1，2，3……n的楼，然后要求你排列这n个楼的位置，使得从最左端看能看到x个楼，从最右端看到y个楼，问你满足要求的方案数。
解：先将最高的楼去掉，然后将剩下的n-1个楼分成x-1+y-1组，每组内部是随意排列的，而组之间要保证从左/右往中间是递增的，这就是第一类斯特林数的定义。在中x-1+y-1组中选x-1个放在左边，得到公式：
S ( n − 1 , x − 1 + y − 1 ) ∗ C ( x − 1 + y − 1 , x − 1 ) S(n-1,x-1+y-1)*C(x-1+y-1,x-1) S(n−1,x−1+y−1)∗C(x−1+y−1,x−1)
exe
CodeForces 932E. Team Work从n≤1e9个人中选取一个非空子集X，求所有可能的子集大小的次方之和即 ∣ X ∣ k |X|^k ∣X∣k，k≤5000
HDU 4625. JZPTREE每条边的长度为1，对每个节点u，求 E u = ∑ v = 1 n ( d ( u , v ) ) k , E_u = \sum_{v=1}^n (d(u, v))^k, Eu=∑v=1n(d(u,v))k,
CodeForces 1097G. Vladislav and a Great Legend类似上一题
CodeForces 960G. Bandit Blues类似例题
Coefficienthdu多校求泰勒展开系数，dls说有用到stirling数
代码
using namespace std;
typedef long long giant;
const int maxn=2e3+1;
const giant q=1e9+7;
giant c[maxn][maxn],s[maxn][maxn];
int main() {#ifndef ONLINE_JUDGEfreopen("test.in","r",stdin);#endifc[0][0]=s[0][0]=1;for (register int i=1;i<maxn;++i) {c[i][0]=1;for (register int j=1;j<=i;++j) {c[i][j]=(c[i-1][j]+c[i-1][j-1])%q;s[i][j]=(s[i-1][j-1]+((i-1)*s[i-1][j])%q)%q;}}int T=read();while (T--) {int n=read(),f=read(),b=read();giant ans=(c[b+f-2][b-1]*s[n-1][b+f-2])%q;printf("%lld\n",ans);}
}
发布评论