自动搬运

查看原文

来自洛谷，原作者为

	wurzang e

搬运于2025-08-24 22:10:20，当前版本为作者最后更新于2020-07-09 10:38:42，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

众所周知，第二类斯特林数有性质：

$$m^n=\sum_{i=0}^m \binom m i \left\{ \begin{matrix} n \\ i \end{matrix} \right\} i! $$

然后可以愉快地二项式反演了。

设

$$f(m)=m^n,g(m)= \left\{ \begin{matrix} n \\ m \end{matrix} \right\}m! $$

那么就有

$$ f(m)=\sum_{i=0}^m \binom{m}{i}g(i) \Leftarrow\Rightarrow g(m)=\sum_{i=0}^m \binom{m}{i}(-1)^{m-i}f(i)=\sum_{i=0}^m\binom m i(-1)^{m-i} i^n $$

于是就有

$$\left\{ \begin{matrix} n \\ m \end{matrix} \right\}m!=\sum_{i=0}^m \binom m i (-1)^{m-i} i^n $$$$\left\{ \begin{matrix} n \\ m \end{matrix} \right\}=\sum_{i=0}^m \frac{\binom m i (-1)^{m-i}i^n}{m!} $$

把组合数拆开来，就有：

$$\left\{ \begin{matrix} n\\m \end{matrix} \right\}=\sum_{i=0}^m \frac{i^n}{i!} \frac{(-1)^{m-i}}{(m-i)!} $$

发现这显然就是一个卷积形式，NTT 碾过去即可。

代码如下：

#include<bits/stdc++.h>
using namespace std;
#define int long long 
typedef long long ll;
const ll mod=167772161;
int G=3,invG;
const int N=2400000;
ll ksm(ll b,int n){
    ll res=1;
    while(n){
        if(n&1) res=res*b%mod;
        b=b*b%mod; n>>=1;
    }
    return res;
}
int tr[N];
void NTT(ll *f,int n,int fl){
    for(int i=0;i<n;++i)
        if(i<tr[i]) swap(f[i],f[tr[i]]);
    for(int p=2;p<=n;p<<=1){
        int len=(p>>1);
        ll w=ksm((fl==0)?G:invG,(mod-1)/p);
        for(int st=0;st<n;st+=p){
            ll buf=1,tmp;
            for(int i=st;i<st+len;++i)
                tmp=buf*f[i+len]%mod,
                f[i+len]=(f[i]-tmp+mod)%mod,
                f[i]=(f[i]+tmp)%mod,
                buf=buf*w%mod;
        }
    }
    if(fl==1){
        ll invN=ksm(n,mod-2);
        for(int i=0;i<n;++i)
            f[i]=(f[i]*invN)%mod;
    }
}
ll f[N],g[N],a[N],b[N],fac[N],inv[N];
void init(int n){
    fac[0]=1;
    for(int i=1;i<=n;++i)
        fac[i]=1ll*fac[i-1]*i%mod;
    inv[n]=ksm(fac[n],mod-2);
    for(int i=n-1;i>=0;--i)
        inv[i]=1ll*(i+1)*inv[i+1]%mod;
}
signed main(){
    invG=ksm(G,mod-2);
    int n;
    scanf("%lld",&n);
    init(n);
    for(int i=0;i<=n;++i)
        a[i]=(i&1?mod-inv[i]:inv[i]),
        b[i]=ksm(i,n)*inv[i]%mod;
    int limit=1;
    while(limit<=(n<<1)) limit<<=1;
    for(int i=0;i<=limit;++i)
        tr[i]=(tr[i>>1]>>1)|(i&1?limit>>1:0);
    NTT(a,limit,0);NTT(b,limit,0);
    for(int i=0;i<=limit;++i)
        a[i]=a[i]*b[i]%mod;
    NTT(a,limit,1);
    for(int i=0;i<=n;++i)
        printf("%lld ",a[i]);
    return 0;
}

顺便讲一下列的做法（

每个盒子的 $EGF$ 显然就是 $g(x)=\sum_{i=1}^n \frac{1}{i!}x^i=e^x-1$，把盒子的 $EGF$ 相乘就可以得到 $(e^x-1)^k$ （其中 $k$ 是盒子的个数）

然后就可以得到"第二类斯特林数"的 $EGF$ 了。但是还有个问题就是盒子是相同的，而我们在推导 $EGF$ 的过程中是把每个盒子按不同的来看待的，直接把这个"第二类斯特林数"除以 $k!$ 即可，是非常显然的去重，然后就可以得到真正的第二类斯特林数。

至于 $(e^x-1)^k$ 怎么算，直接多项式快速幂即可。

代码如下：

#include<bits/stdc++.h>
using namespace std;
#define int long long 
typedef long long ll;
const ll mod=167772161;
ll G=3,invG;
const int N=1200000;
ll ksm(ll b,int n){
	ll res=1;
	while(n){
		if(n&1) res=res*b%mod;
		b=b*b%mod; n>>=1;
	}
	return res;
}
int read(){
	int x=0;char ch=getchar();
	while(!isdigit(ch))ch=getchar();
	while(isdigit(ch)) x=(x*10+(ch-'0'))%mod,ch=getchar();
	return x;
}
int tr[N];
void NTT(ll *f,int n,int fl){
	for(int i=0;i<n;++i)
		if(i<tr[i]) swap(f[i],f[tr[i]]);
	for(int p=2;p<=n;p<<=1){
		int len=(p>>1);
		ll w=ksm((fl==0)?G:invG,(mod-1)/p);
		for(int st=0;st<n;st+=p){
			ll buf=1,tmp;
			for(int i=st;i<st+len;++i)
				tmp=buf*f[i+len]%mod,
				f[i+len]=(f[i]-tmp+mod)%mod,
				f[i]=(f[i]+tmp)%mod,
				buf=buf*w%mod;
		}
	}
	if(fl==1){
		ll invN=ksm(n,mod-2);
		for(int i=0;i<n;++i)
			f[i]=(f[i]*invN)%mod;
	}
}
void Mul(ll *f,ll *g,ll *p,int n,int m){
	m+=n;n=1;
	while(n<m) n<<=1;
	for(int i=0;i<n;++i)
		tr[i]=(tr[i>>1]>>1)|((i&1)?(n>>1):0);
	NTT(f,n,0);
	NTT(g,n,0);
	for(int i=0;i<n;++i) p[i]=f[i]*g[i]%mod;
	NTT(p,n,1);
	
}

void Inv(ll *f,ll *g,int m){
	if(m==1){
		g[0]=ksm(f[0],mod-2);
		return;
	}
	static ll w[N];
	Inv(f,g,(m+1)>>1);
	int n=1;
	while(n<(m<<1)) n<<=1;
	for(int i=0;i<m;++i) w[i]=f[i];
	for(int i=m;i<n;++i) w[i]=0;
	for(int i=0;i<n;++i)
		tr[i]=(tr[i>>1]>>1)|((i&1)?(n>>1):0);
	NTT(w,n,0);
	NTT(g,n,0);
	for(int i=0;i<n;++i)
		g[i]=((2*g[i]-g[i]*g[i]%mod*w[i]%mod)%mod+mod)%mod;
	NTT(g,n,1);
	for(int i=m;i<n;++i) g[i]=0; 
}
void diff(ll *f,ll *g,int n){
	for(int i=1;i<n;++i)
		g[i-1]=f[i]*i%mod;
	g[n-1]=0;
}
void integ(ll *f,ll *g,int n){
	for(int i=1;i<n;++i)
		g[i]=f[i-1]*ksm(i,mod-2)%mod;
	g[0]=0;
}
ll f_wf[N],f_inv[N],ans[N];
void Ln(ll *f,ll *g,int n){
	for(int i=0;i<(n<<2);++i) f_wf[i]=f_inv[i]=ans[i]=0;
	diff(f,f_wf,n);
	Inv(f,f_inv,n);
	Mul(f_wf,f_inv,ans,n,n);
	integ(ans,g,n);
}
void Exp(ll *f,ll *g,int m){
	if(m==1){
		g[0]=1;return;
	}
	Exp(f,g,(m+1)>>1);
	static ll w[N],ln[N];
	for(int i=0;i<m;++i) ln[i]=0;
	Ln(g,ln,m);
	int n=1;
	while(n<(m<<1)) n<<=1;
	for(int i=0;i<n;++i)
		tr[i]=(tr[i>>1]>>1)|(i&1?n>>1:0);
	for(int i=0;i<m;++i) w[i]=f[i];
	for(int i=m;i<n;++i) w[i]=0;
	NTT(w,n,0);NTT(g,n,0);NTT(ln,n,0);
	for(int i=0;i<n;++i)
		g[i]=g[i]*(1-ln[i]+w[i]+mod)%mod;
	NTT(g,n,1);
	for(int i=m;i<n;++i) g[i]=0;
}
int k2;
void Pow(ll *f,ll *g,int n,int k){
	static ll _f[N],lnf[N];
	ll deg=0;
	while(f[deg]==0) ++deg;
	if(deg*k>n) return;
	n-=deg;
	for(int i=0;i<n;++i)
		_f[i]=f[i+deg];
	ll f0=_f[0],inv0=ksm(_f[0],mod-2);
	for(int i=0;i<n;++i)
		_f[i]=_f[i]*inv0%mod;
	Ln(_f,lnf,n);
	for(int i=0;i<n;++i)
		lnf[i]=lnf[i]*k%mod;
	Exp(lnf,g,n);
	deg=deg*k2;
	for(int i=n+deg-1;i>=deg;--i)
		g[i]=g[i-deg]*ksm(f0,k2)%mod;
	for(int i=0;i<deg;++i) g[i]=0;
}
ll f[N],g[N];
ll inv[N],fac[N];
void init(int n){
	fac[0]=1;
	for(int i=1;i<=n;++i)
		fac[i]=1ll*fac[i-1]*i%mod;
	inv[n]=ksm(fac[n],mod-2);
	for(int i=n-1;i>=0;--i)
		inv[i]=1ll*inv[i+1]*(i+1)%mod;
}
string s;
signed main(){
	invG=ksm(G,mod-2);
	int n,k=0;
	cin>>n>>k;++n;
	if(k>=n){
		for(int i=0;i<n;++i) putchar('0'),putchar(' ');
		return 0;
	}
	k2=k;
	init(max(n,k));
	for(int i=1;i<n;++i)
		f[i]=inv[i];
	Pow(f,g,n,k);
	for(int i=0;i<n;++i)
		g[i]=g[i]*fac[i]%mod*inv[k]%mod,
		printf("%lld ",g[i]);
	return 0;
}

本来想再把 第一类斯特林数·行/列 给讲掉的，但这样博客实在太长了，就算了吧（

顺便一提第一类斯特林数·列的做法与第二类斯特林数·列的做法相似