斯特林数行列求解

正题

第二类斯特林数.行

根据通项公式有:$S(n,m)=\frac{1}{m!}{\sum }_{i=0}^m{C}_m^i(-1{)}^i(m-i{)}^n$

拆开来就可以变成卷积的形式.

第一类斯特林数.行:

第一类斯特林数实际上是上升幂展开成普通幂的系数,那么只需要多项式平移就可以倍增求出$s(n,0)-s(n,n)$

void gas(vi&f){
	int n=f.size()-1,m=n/2;
	if(n==1){f[1]=1;return ;}
	vi f0;f0.resize(m+1);gas(f0);
	vi g;g.resize(m+1);
	int t=1;f=f0;
	for(int i=0;i<=m;i++) 
		f0[i]=1ll*fac[i]*f0[i]%mod,g[i]=1ll*t*finv[i]%mod,t=1ll*t*m%mod;
	reverse(g.begin(),g.end());g=f0*g;
	for(int i=0;i<=m;i++) g[i]=1ll*g[m+i]*finv[i]%mod;
	g.resize(m+1);f=f*g;
	if(n%2==1) {
		f.push_back(0);
		for(int i=n-1;i>=0;i--) ad(f[i+1],f[i]),f[i]=1ll*f[i]*(n-1)%mod;
	}
}
 
int main(){
	scanf("%d",&n);pre();
	A.resize(n+1);gas(A);
	for(int i=0;i<=n;i++) printf("%d ",A[i]);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

第二类斯特林数.列

将递推公式写出来,设$G_k={\sum }_{i=0}S(i,k)x^i$

显然有$$\begin{gathered} {G}_k(x)=kx{G}_k(x)+x{G}_{k-1}(x) \\ {G}_k(x)=\frac{x}{1-kx}{G}_{k-1}(x) \end{gathered}$$

那么就是要求一个前缀的$(1-kx)$卷积,多项式平移即可,最后讨论一下系数.

void gas(vi&f){
	int n=f.size()-1,m=n/2;
	if(n==1){f[1]=1;return ;}
	vi f0;f0.resize(m+1);gas(f0);
	vi g;g.resize(m+1);
	int t=1;f=f0;
	for(int i=0;i<=m;i++) 
		f0[i]=1ll*fac[i]*f0[i]%mod,g[i]=1ll*t*finv[i]%mod,t=1ll*t*m%mod;
	reverse(g.begin(),g.end());g=f0*g;
	for(int i=0;i<=m;i++) g[i]=1ll*g[m+i]*finv[i]%mod;
	g.resize(m+1);f=f*g;
	if(n%2==1) {
		f.push_back(0);
		for(int i=n-1;i>=0;i--) ad(f[i+1],f[i]),f[i]=1ll*f[i]*(n-1)%mod;
	}
}
 
int main(){
	scanf("%d %d",&n,&m);pre();
	if(n<m){for(int i=0;i<=n;i++) printf("0 ");return 0;}
	A.resize(m+2);gas(A);
	int t=(m&1)?(mod-1):1;
	for(int i=0;i<=m;i++) A[i]=1ll*A[i+1]*t%mod,t=(t==1)?(mod-1):(1);
	A.pop_back();reverse(A.begin(),A.end());
	A.resize(n-m+1);INV(A);
	for(int i=0;i<m;i++) printf("0 ");
	for(int i=0;i<n-m+1;i++) printf("%d ",A[i]);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

第一类斯特林数.列

实际上就是求把若干个个元素拆成 $k$ 个置换环的方案数，显然可以构造单个置换环的 $EGF$ ，然后求这个 $EGF$ 的 $k$ 次,再除以 $k$ 的阶乘,然后就可以的得到i个元素拆成 $k$ 个置换环的 $EGF$ 。

int main(){
	scanf("%d %d",&n,&m);pre();
	vi A;A.resize(n+1);A[0]=0;
	for(int i=1;i<=n;i++) A[i]=1ll*fac[i-1]*finv[i]%mod;
	KSM(A,m,m,0);
	for(int i=0;i<=n;i++) printf("%lld ",1ll*A[i]*fac[i]%mod*finv[m]%mod);
}
1
2
3
4
5
6
7