分类： 快速数论变换

第二类斯特林数，指的是一组表示「将n个不同的元素划分为m个非空不相交集的方案数」的组合数。有时写作\(S(n,m)\)或\(\left\{\begin{matrix}n\\m\end{matrix}\right\}\)
从题意来看，我们可以容易地想到一个递推方案：每个新的元素，可以为它新开一个集合，或者放到已有的任何一个集合里面。所以我们得到一个递推式：
$$S(n,m)=S(n-1,m-1)+m*S(n-1,m)$$
然后问题是怎么求值。

首先我们有一个式子，我们称之为二项式反演的通项式。
$$ f(n)=\sum_{i=0}^nC_{n}^{i}g(n) \Leftrightarrow g(n)=\sum_{i=0}^n(-1)^{n-i}C_{i}{n}f(n)$$
举个例子：
$$\begin{matrix} f_{1}&=&g_{1}\\f_{2}&=&g_{1}&+&g_{2}\\f_{3}&=&g_{1}&+&2*g_{2}&+&g_{3}\\f_{4}&=&g_{1}&+&3*g_{2}&+&3*g_{3}&+&g_{4} \end{matrix}$$

由此可得：

$$\begin{matrix} g_{1}&=&f_{1}\\g_{2}&=&f_{2}&-&f_{1}\\g_{3}&=&f_{3}&-&2*g_{2}&-&g_{1}\\&=&f_{3}&-&2*f_{2}&+&f_{1}\\g_{4}&=&f_{4}&-&3*g_{3}&-&3*g_{2}&-&g_{1}\\&=&f_{4}&-&3*f_{3}&-&3*g_{2}&-&4*g_{1}\\&=&f_{4}&-&3*f_{3}&+&3*f_{2}&-&f_{1} \end{matrix}$$

然后我们考虑\(m^n\)的组合意义，也就是，将\(n\)个不同的球，放到\(m\)个不同的盒子（可以有空盒）的方案数。
我们不妨枚举有装东西的盒子的个数。令它为\(i\)，那么选取这些盒子的方案数即是\(C_{m}^{i}\)。
选取了盒子之后，问题就转化为了将\(n\)个不同物品装到\(m\)个不同盒子里，使得每个盒子非空。这就相当于，将\(n\)个不同物品装到\(m\)个相同盒子里，使得每个盒子非空的方式——也就是\(S(n,m)\)，乘上盒子的排列顺序——也就是\(m!\)。
形式化的说，就是：
$$m^n=\sum_{i=0}^{m}S(n,i)i!C_{m}^{i}$$
我们发现这个式子的形式符合二项式反演的通项式。
因而我们将\(m^n\)作为\(f\)，将\(S(n,i)i!\)作为\(g\)。
那么反演得到：
$$S(n,m)=\frac{1}{m!}\sum_{i=0}^{m}(-1)^{m-i}i^nC_{m}^{i}$$
考虑\(C_{m}^{i}=\frac{m!}{i!(m-i)!}\)，我们可以将上式化简得到：
$$S(n,m)=\sum_{i=0}^{m}\frac{(-1)^{m-i}i^n}{i!(m-i)!}$$
于是我们有：
$$\left\{\begin{matrix}n\\m\end{matrix}\right\}=\sum_{i=0}^{m}\frac{(-1)^{m-i}i^n}{i!(m-i)!}$$
考虑函数卷积的本质，对于卷积\(f=gu\)，其本质是： $$f(n)=\sum_{i=0}^{n}g(i)u(n-i)$$ 因而，我们发现，上式本质上就是： $$\left\{\begin{matrix}n\\m\end{matrix}\right\}=\sum_{i=0}^{m}\frac{(-1)^{m-i}}{(m-i)!}*\frac{i^n}{i!}$$
上一个NTT卷积一下就好了。

#include<iostream>
#include<cstdio>

#define Swap(A,B) (A^=B^=A^=B)
const long long P=167772161;
const long long g0=3,gi=55924054;
int L=1,R[1<<21|1];
long long invL;
inline int pw(int A,int X){
	long long BS=A,RT=1;
	while(X){
		if(X&1){
			RT=RT*BS%P;
		}
		BS=BS*BS%P;
		X>>=1;
	}
	return RT;
}
inline void prpr(int LEN){
	int B=0;
	while(L<=LEN){
		L<<=1;
		++B;
	}
	invL=P-(P-1)/L;
	for(int i=0;i<L;++i){
		R[i]=R[i>>1]>>1|(i&1)<<(B-1);
	}
}
inline void FNTT(int *A,int typ){
	for(int i=0;i<L;++i){
		if(R[i]<i){
			Swap(A[R[i]],A[i]);
		}
	}
	int gn,g,X,Y,M;
	for(int i=2;i<=L;i<<=1){
		M=i>>1;
		gn=pw(~typ?g0:gi,(P-1)/i);
		for(int j=0;j<L;j+=i){
			g=1;
			for(int k=0;k<M;++k,g=1ll*g*gn%P){
				X=A[j+k],Y=1ll*g*A[M+j+k]%P;
				A[j+k]=(X+Y)%P,A[M+j+k]=(X-Y)%P;
			}
		}
	}
}
int n,a[1<<21|1],b[1<<21|1],inv[1<<21|1];
void init(){
	scanf("%d",&n);
	prpr(n+1<<1);
	inv[0]=inv[1]=1;
	for(int i=2;i<=n;++i){
		inv[i]=1ll*(P-P/i)*inv[P%i]%P;
	}
	for(int i=1;i<=n;++i){
		inv[i]=1ll*inv[i-1]*inv[i]%P;
	}
	for(int i=0;i<=n;++i){
		a[i]=1ll*pw(-1,i)*inv[i]%P;
		b[i]=1ll*pw(i,n)*inv[i]%P;
	}
	FNTT(a,1);
	FNTT(b,1);
	for(int i=0;i<L;++i){
		a[i]=1ll*a[i]*b[i]%P;
	}
	FNTT(a,-1);
	for(int i=0;i<=n;++i){
		printf("%d ",1ll*(a[i]+P)*invL%P);
	}
}

int main(){
	init();
	return 0;
}