2019.5.31

wzx稳啦/ke

写这个真的累。

Sterling Number Note

在组合数学中,斯特林(Stirling)数可指两类数,第一类斯特林数和第二类斯特林数
这些均由18世纪数学家James Stirling提出的,并在著作Methodous Differentialis中首次使用
自此,斯特林数成为又一广泛运用到处理组合问题的一大利器
${\large\color{SpringGreen}{第一类斯特林数}}$
定义
$\begin{bmatrix}n\m \end{bmatrix}$表示$n$个元素分成$m$个环的方案数
显然:$\begin{bmatrix}n\m \end{bmatrix}=\begin{bmatrix}n-1\m-1 \end{bmatrix}+(n-1)*\begin{bmatrix}n-1\m \end{bmatrix}$
理解:考虑从n-1个元素推过来,如果两个空环肯定是不符合的

空一个环则单独成环,如果n-1的时候就没有空环就任意放在一个元素前
性质

$n!=\sum\limits_{i=0}^n \begin{bmatrix}n\i \end{bmatrix}$

理解:其实本质就是置换,一个环则为一组轮换,每种排列都会对应着唯一 一种置换

归纳法:

证明类上,不再赘述
求第一类斯特林数

其实把表刷出来就差不多了,可以理解为根据

逐渐转移

至此,我们可以通过分治FFT在$O(nlog^2n)$求出一行的第一类斯特林数

还有一种类似于多项式求逆模式$O(nlogn)$的方法
$F(x)^n=\prod\limits_{i=0}^{n-1}(x+i),F(x)^{2n}=F(x)^nF(x+n)^n$

考虑当我们求出$(F(x)^n=\sum\limits{i=0}^{n}a_ix^i):$
$\begin{aligned}\
F(x+n)^{n}=\sum\limits
{i=0}^{n}ai(x+n)^i\
=\sum\limits
{i=0}^nai\sum\limits{j=0}^i{i\choose j}n^{i-j}x^j\
=\sum\limits{i=0}^n(\sum\limits{j=i}^n {j\choose i}n^{j-i}aj)x^i\
=\sum\limits
{i=0}^n(\sum\limits{j=i}^n \frac{j!}{i!(j-i)!}n^{j-i}a_j)x^i\
=\sum\limits
{i=0}^n (i!)^{-1}x^i (\sum\limits_{j=i}^n (\frac{n^{j-i}}{(j-i)!})\cdot (j!a_j))\
\end{aligned}$
我们通过左半部分系数能得到右半部分系数,再相乘一下就得到了总体的系数

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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
#include<bits/stdc++.h>
typedef long long LL;
const LL mod=998244353,g=3,maxn=1e6+9;
inline LL Pow(LL base,LL b){
LL ret(1);
while(b){
if(b&1) ret=ret*base%mod; base=base*base%mod; b>>=1;
}return ret;
}
LL r[maxn];
inline LL Fir(LL n){
LL limit(1),len(0);
while(limit<(n<<1)){
limit<<=1; ++len;
}
for(LL i=0;i<limit;++i) r[i]=(r[i>>1]>>1)|((i&1)<<len-1);
return limit;
}
inline void NTT(LL *a,LL n,LL type){
for(LL i=0;i<n;++i) if(i<r[i]) std::swap(a[i],a[r[i]]);
for(LL mid=1;mid<n;mid<<=1){
LL wn(Pow(g,(mod-1)/(mid<<1))); if(type==-1) wn=Pow(wn,mod-2);
for(LL R=mid<<1,j=0;j<n;j+=R)
for(LL k=0,w=1;k<mid;++k,w=w*wn%mod){
LL x(a[j+k]),y(w*a[j+mid+k]%mod);
a[j+k]=(x+y)%mod; a[j+mid+k]=(x-y+mod)%mod;
}
}
if(type==-1){
LL ty(Pow(n,mod-2)); for(LL i=0;i<n;++i) a[i]=a[i]*ty%mod;
}
}
LL T[maxn],F[maxn],H[maxn],G[maxn],fac[maxn],fav[maxn],tmp[maxn],sum[maxn],B[maxn];
inline void Mul(LL n,LL *a,LL *b,LL *ans){
LL limit(Fir(n));
NTT(a,limit,1); NTT(b,limit,1);
for(LL i=0;i<limit;++i) ans[i]=a[i]*b[i]%mod;
NTT(ans,limit,-1);
}
inline void Solve(LL n,LL *a){
if(!n){ a[0]=1; return; }
if(n==1){ a[1]=1; return; }
LL len(n/2);
Solve(len,a);

LL limit(Fir(len+1));
for(LL i=0;i<=len;++i) F[i]=Pow(len,i)*fav[i]%mod;
for(LL i=0;i<=len;++i) H[i]=fac[i]*a[i]%mod;
for(LL i=0;i<=(len>>1);++i) std::swap(H[i],H[len-i]);
for(LL i=len+1;i<limit;++i) F[i]=H[i]=0;
NTT(F,limit,1); NTT(H,limit,1);
for(LL i=0;i<limit;++i) G[i]=F[i]*H[i]%mod;
NTT(G,limit,-1);
for(LL i=0;i<=len;++i) tmp[i]=G[len-i]*Pow(fac[i],mod-2)%mod;//right

Mul(len+1,a,tmp,B);//left * right
for(LL i=0;i<=(len<<1);++i) a[i]=B[i];
for(LL i=(len<<1)+1;i<=(len<<2);++i) a[i]=tmp[i]=0;

if(n&1){
for(LL i=0;i<n;++i) T[i]=a[i];
for(LL i=1;i<=n;++i) a[i]=(T[i-1]+(n-1)*T[i]%mod)%mod;
}
}
inline LL Get_c(LL n,LL m){
return fac[n]*fav[m]%mod*fav[n-m]%mod;
}
LL n;
LL ans[maxn];
int main(){
scanf("%lld",&n);
fac[0]=fac[1]=1;
for(LL i=2;i<=n;++i) fac[i]=fac[i-1]*i%mod;
fav[n]=Pow(fac[n],mod-2);
for(LL i=n;i>=1;--i) fav[i-1]=fav[i]*i%mod;
Solve(n,ans);
for(LL i=0;i<=n;++i) printf("%lld ",ans[i]);printf("\n");
return 0;
}

${\large\color{SpringGreen}{第二类斯特林数}}$

定义

$\begin{Bmatrix}n\m\end{Bmatrix}$表示n个有区别的小球丢进m个无区别的盒子,无空盒子的方案数
显然:$\begin{Bmatrix}n\m\end{Bmatrix}=\begin{Bmatrix}n-1\m-1\end{Bmatrix}+m*\begin{Bmatrix}n-1\m\end{Bmatrix}$
理解:考虑从n-1个小球推过来,如果两个空盒子肯定是不符合的
空一个盒子则只能放到那个空盒子里面了,如果n-1的时候就没有空箱子就随便放
性质

当然也可以写成:

到后面反演时我们会这样写:

看看后面的$m^{\underline i}$就懂了
理解:$m^n$为$n$个有区别的小球丢进$m$个有区别的盒子,允许空盒子
枚举有效盒子的个数,再从$m$个盒子选$i$个盒子,然后$n$个小球丢进$i$个盒子
转换到组合表示
第二类斯特林数显然是和排列组合有关系的,转换过来:

理解:如果空箱子的情况我们也算进去,答案显然是$\frac{m^n}{m!}$
反过来求第二类斯特林数,又得减掉这种情况:
选$k$个空盒子,然后小球放到其他的盒子里
但最后我们求出来的答案为有区别的盒子,转换过来要$×\frac{1}{m!}$

求第二类斯特林数

大概都能猜到是卷积形式了吧,随手展开一下:

至此,我们能实现O(nlogn)求出S(n)这一行的第二类斯特林
第二类斯特林数与自然数幂的关系

关于$\sum\limits{i=0}^nC_i^j=C{n+1}^{j+1}$的理解:枚举j+1的右端点i+1,则相当于从$i$个点中选$j$个点
${\large\color{SpringGreen}{斯特林反演}}$
定义
斯特林反演:

总结上面我们所推倒的性质

补充

前置
我们先证这个反转公式

反转公式1:

反转公式2:

推式

已知:

则有