第一類和第二類斯特林數【學習總結】

（哪天頹廢的時候來填坑吧。。）

• 定義

• 應用

• 模闆：

  第一類：

  落谷模闆

#include<bits/stdc++.h>
using namespace std;
#define sf scanf
#define pf printf
#define cs const
#define ll long long
cs int mod=167772161,N=262154;
inline int mul(cs int &a,cs int &b){return 1ll*a*b%mod;}
inline int add(cs int &a,cs int &b){return a+b>mod? a-mod+b : a+b;} 
inline int dec(cs int &a,cs int &b){return a-b<0 ? a+mod-b:a-b;}
inline int ksm(int a,int b){int ans=1;for(;b;b>>=1,a=mul(a,a))if(b&1)ans=mul(ans,a); return ans;}
typedef vector<int> node;
int lim,tim,inv[30],w[30],maxn,ifac[N],fac[N];
node rev[30];
#define ri register int
inline void init_w(){
	w[23]=ksm(3,(mod-1)>>24);inv[0]=1;
	for(ri i=22;~i;--i)w[i]=mul(w[i+1],w[i+1]);
	for(ri i=1,mt=(mod+1)>>1;i<24;++i)inv[i]=mul(inv[i-1],mt);
	ifac[0]=1;fac[0]=1;
	for(ri i=1;i<=maxn;++i)fac[i]=mul(fac[i-1],i),ifac[i]=mul(ifac[i-1],ksm(i,mod-2));
} 
inline void init(cs int &top){
	for(lim=1,tim=0;lim<=top;lim<<=1,++tim);
	if(rev[tim].size())return;
	rev[tim].resize(lim);
	for(ri i=1;i<lim;++i)rev[tim][i]=(rev[tim][i>>1]>>1)|((i&1)*(lim>>1)); 
}
inline void ntt(node &f,int kd){
	for(ri i=0;i<lim;++i)if(rev[tim][i]<i)swap(f[i],f[rev[tim][i]]);
	for(ri mid=1,t=0;mid<lim;mid<<=1,++t)
		for(ri i=0,dlt=mid<<1;i<lim;i+=dlt)
			for(ri j=0,p0,p1,now=1;j<mid;++j,now=mul(now,w[t])){
				p0=f[i+j],p1=mul(now,f[i+j+mid]);
				f[i+j]=add(p0,p1);f[i+j+mid]=dec(p0,p1);
			}
	if(~kd)return;
	reverse(++f.begin(),f.end());
	for(ri i=0;i<lim;++i)f[i]=mul(f[i],inv[tim]);
}
inline node operator *(node a,node b){
	int n=a.size(),m=b.size(),t=n+m-1;
	if(t<=168){
		node c(t);
		for(ri i=0;i<n;++i)for(ri j=0;j<m;++j)c[i+j]=add(c[i+j],mul(a[i],b[j]));
		return c;
	}
	init(t);
	a.resize(lim);ntt(a,1);
	b.resize(lim);ntt(b,1);
	for(ri i=0;i<lim;++i)a[i]=mul(a[i],b[i]);
	ntt(a,-1);
	return a.resize(t),a; 
}
node ltmp,rtmp;
inline void shift(int n,node &f){
	int m=n+1;
	ltmp.resize(m);rtmp.resize(m);
	for(ri i=0;i<=n;++i)ltmp[i]=mul(ksm(n,n-i),ifac[n-i]),rtmp[i]=mul(fac[i],f[i]);	
	ltmp=ltmp*rtmp;
	for(ri i=0;i<=n;++i)ltmp[i]=ltmp[i+n],ltmp[i]=mul(ltmp[i],ifac[i]);
	ltmp.resize(m);
	f=f*ltmp;
}
inline void dfs(int n,node &f){
	if(n==1){
		f.resize(2);f[1]=1;return;
	}
	if(n%2){
		dfs(n-1,f);
		node tmp(2);tmp[0]=n-1;tmp[1]=1;
		f=f*tmp;
		return;
	}
	dfs(n/2,f);
	shift(n/2,f);
}
signed main(){
	sf("%d",&maxn);
	init_w();
	node f;
	dfs(maxn,f);
	for(ri i=0;i<=maxn;++i)cout<<f[i]<<' ';
	return 0;
}

           

第二類：

落谷模闆

#include<bits/stdc++.h>
using namespace std;
#define sf scanf
#define pf printf
#define cs const
#define ll long long
cs int mod=167772161,N=2e5+10;
inline int mul(cs int &a,cs int &b){return 1ll*a*b%mod;}
inline int add(cs int &a,cs int &b){return a+b>mod? a-mod+b : a+b;} 
inline int dec(cs int &a,cs int &b){return a-b<0 ? a+mod-b:a-b;}
inline int ksm(int a,int b){int ans=1;for(;b;b>>=1,a=mul(a,a))if(b&1)ans=mul(ans,a); return ans;}
typedef vector<int> node;
int lim,tim,inv[30],w[30],maxn,ifac[N];
node rev[30];
#define ri register int
inline void init_w(){
	w[23]=ksm(3,(mod-1)>>24);inv[0]=1;
	for(ri i=22;~i;--i)w[i]=mul(w[i+1],w[i+1]);
	for(ri i=1,mt=(mod+1)>>1;i<24;++i)inv[i]=mul(inv[i-1],mt);
	ifac[0]=1;
	for(ri i=1;i<=maxn;++i)ifac[i]=mul(ifac[i-1],ksm(i,mod-2));
} 
inline void init(cs int &top){
	for(lim=1,tim=0;lim<=top;lim<<=1,++tim);
	if(rev[tim].size())return;
	rev[tim].resize(lim);
	for(ri i=1;i<lim;++i)rev[tim][i]=(rev[tim][i>>1]>>1)|((i&1)*(lim>>1)); 
}
inline void ntt(node &f,int kd){
	for(ri i=0;i<lim;++i)if(rev[tim][i]<i)swap(f[i],f[rev[tim][i]]);
	for(ri mid=1,t=0;mid<lim;mid<<=1,++t)
		for(ri i=0,dlt=mid<<1;i<lim;i+=dlt)
			for(ri j=0,p0,p1,now=1;j<mid;++j,now=mul(now,w[t])){
				p0=f[i+j],p1=mul(now,f[i+j+mid]);
				f[i+j]=add(p0,p1);f[i+j+mid]=dec(p0,p1);
			}
	if(~kd)return;
	reverse(++f.begin(),f.end());
	for(ri i=0;i<lim;++i)f[i]=mul(f[i],inv[tim]);
}
inline node operator *(node a,node b){
	int n=a.size(),m=b.size(),t=n+m-1;
	if(t<=168){
		node c(t);
		for(ri i=0;i<n;++i)for(ri j=0;j<m;++j)c[i+j]=add(c[i+j],mul(a[i],b[j]));
		return c;
	}
	init(t);
	a.resize(lim);ntt(a,1);
	b.resize(lim);ntt(b,1);
	for(ri i=0;i<lim;++i)a[i]=mul(a[i],b[i]);
	ntt(a,-1);
	return a.resize(t),a; 
}
signed main(){
	sf("%d",&maxn);
	init_w();
	int n=maxn+1;
	node a(n),b(n);
	for(ri i=0;i<=maxn;++i)a[i]=i%2==0?ifac[i] : mod-ifac[i],b[i]=mul(ksm(i,maxn),ifac[i]);
	a=a*b;
	for(ri i=0;i<=maxn;++i)cout<<a[i]<<' ';
	return 0;
}