第二类斯特林数学习笔记
定义
第二类斯特林数 \(S(n,m)\)
表示的是把 \(n\) 个不同的小球放在 \(m\) 个相同的盒子里方案数
求法
递推式
$S(n,m)=S(n-1,m-1)+mS(n-1,m) $
含义分别是新开了一个集合和在已有的集合中选择一个放
容斥
\(S(n,m)=\frac{1}{m!}\sum_{i=0}^m(-1)^iC_m^i(m-i)^n\)
考虑用二项式反演
假设一共有 \(n\) 个小球
设 \(f[i]\) 为恰好有 \(i\) 个盒子放了小球的方案数
\(g[i]\) 为至多有 \(i\) 个盒子放了小球的方案数
那么 \(g[k]=\sum_{i=0}^k C_k^if[i]\)
则 \(f[k]=\sum_{i=0}^k(-1)^{k-i}C_k^ig[i]=\sum_{i=0}^k(-1)^{k-i}C_k^i i^n\)
化得好看一点就成了
\(f[k]=\sum_{i=0}^k(-1)^iC_k^i (k-i)^n\)
那么 \(f[m]=\sum_{i=0}^m(-1)^iC_m^i(m-i)^n\)
因为我们算组合数的时候是按照盒子不同算的，所以还要除以一个 \(m!\)
这个式子可以化成卷积的形式
\(S(n,m)=\frac{1}{m!}\sum_{i=0}^m(-1)^iC_m^i(m-i)^n\)
\(S(n,m)=\sum_{i=0}^m\frac{(-1)^i}{i!}\frac{(m-i)^n}{(m-i)!}\)
就可以用 \(ntt\) 在 \(nlogn\) 的时间复杂度内求出一行的第二类斯特林数
代码
#include<cstdio>
#include<algorithm>
#include<cstring>
#define rg register
inline int read(){
rg int x=0,fh=1;
rg char ch=getchar();
while(ch<'0' || ch>'9'){
if(ch=='-') fh=-1;
ch=getchar();
}
while(ch>='0' && ch<='9'){
x=(x<<1)+(x<<3)+(ch^48);
ch=getchar();
}
return x*fh;
}
const int maxn=524289,mod=167772161,G=3;
inline int addmod(rg int now1,rg int now2){
return now1+=now2,now1>=mod?now1-mod:now1;
}
inline int delmod(rg int now1,rg int now2){
return now1-=now2,now1<0?now1+mod:now1;
}
inline int mulmod(rg long long now1,rg int now2){
return now1*=now2,now1>=mod?now1%mod:now1;
}
int ksm(rg int ds,rg int zs){
rg int nans=1;
while(zs){
if(zs&1) nans=mulmod(nans,ds);
ds=mulmod(ds,ds);
zs>>=1;
}
return nans;
}
int w[25][maxn],wz[maxn];
void ntt(rg int A[],rg int lim,rg int typ){
for(rg int i=0;i<lim;i++) if(i<wz[i]) std::swap(A[i],A[wz[i]]);
for(rg int len=1,t0=0;len<lim;len<<=1,t0++){
for(rg int j=0,now=len<<1;j<lim;j+=now){
for(rg int k=0;k<len;k++){
rg int x=A[j+k],y=mulmod(A[j+k+len],w[t0][k]);
A[j+k]=addmod(x,y),A[j+k+len]=delmod(x,y);
}
}
}
if(typ==-1){
std::reverse(A+1,A+lim);
rg int ny=ksm(lim,mod-2);
for(rg int i=0;i<lim;i++) A[i]=mulmod(A[i],ny);
}
}
int a[maxn],b[maxn],jc[maxn],jcc[maxn],ny[maxn],n;
void pre(){
ny[1]=1;
for(rg int i=2;i<=n;i++) ny[i]=mulmod(mod-mod/i,ny[mod%i]);
jc[0]=jcc[0]=1;
for(rg int i=1;i<=n;i++) jc[i]=mulmod(jc[i-1],i),jcc[i]=mulmod(jcc[i-1],ny[i]);
}
int main(){
n=read();
pre();
for(rg int i=0;i<=n;i++){
if(i&1) a[i]=mod-jcc[i];
else a[i]=jcc[i];
b[i]=mulmod(ksm(i,n),jcc[i]);
}
rg int lim=1,bit=0;
for(;lim<=n+n;lim<<=1) bit++;
for(rg int i=0;i<lim;i++) wz[i]=(wz[i>>1]>>1)|((i&1)<<(bit-1));
for(rg int len=1,t0=0;len<lim;len<<=1,t0++){
w[t0][0]=1,w[t0][1]=ksm(G,(mod-1)/(len<<1));
for(rg int i=2;i<len;i++) w[t0][i]=mulmod(w[t0][1],w[t0][i-1]);
}
ntt(a,lim,1),ntt(b,lim,1);
for(rg int i=0;i<lim;i++) a[i]=mulmod(a[i],b[i]);
ntt(a,lim,-1);
for(rg int i=0;i<=n;i++) printf("%d ",a[i]);
printf("\n");
return 0;
}
应用
\(n^k=\sum_ { i=0}^k S(k,i)×i!×C(n,i)\)
左边的含义就是 \(k\) 个球放在 \(n\) 个盒子里
右边的含义是枚举有多少个盒子放
也可以写成下降幂的形式
\(n^k=\sum_{i=0}^k S(k,i) n^{\underline i}\)
