斯特林数学习笔记。
1.第二类斯特林数
虽然被称为第二类，但是应用比第一类更为广泛重要。
第二类斯特林数（斯特林子集数）$\displaystyle {n \brace k}$，也可记作 $S(n,k)$，表示将 $n$ 个两两不同数，划分为 $k$ 个互不区分的非空集合的方案数。
1.1 递推式
边界为 $\displaystyle {n \brace 0}=[n=0]$。
考虑组合意义，设当前元素为 $n$，将 $n$ 放进一个新建的集合的方案数为 $\displaystyle {n-1 \brace k-1}$，或者将其放进任意一个已有的集合的方案数为 $\displaystyle k{n-1 \brace k}$，二者相加得到。
1.2 通项公式
考虑先固定 $n$。发现“非空”的限制条件不好处理。考虑用容斥去掉这一条件。设计 $f(i)$ 表示将 $n$ 个两两不同数，划分为 $i$ 个互相区分的非空集合， $g(i)$ 表示将 $n$ 个两两不同数，划分为 $i$ 个互相区分的集合。根据定义容易得到：
运用二项式反演，得到：
最终得到：
1.3 同一行第二类斯特林数的计算
求出 $\displaystyle {n \brace i}$，其中 $i=0,1,\cdots,n$。
很容易根据通项公式辨识出卷积的形式：$\displaystyle {n \brace k}=\sum_{i=0}^n \frac{i^n}{i!}\frac{(-1)^{k-i}}{(k-i)!}$，直接卷积计算即可。
Code
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
| #include<iostream>
#include<cstdio>
using namespace std;
const int N=4e6+10,mod=167772161,G=3,Gi=(mod+1)/G;
template <class T>
inline void read(T &x)
{
x=0;bool f=0;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=1;ch=getchar();}
while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
if(f)x=-x;
}
template <class T,class ...T1>
inline void read(T &x,T1 &...x1)
{
read(x),read(x1...);
}
int n;
int a[N],b[N],c[N];
int bit,tot,rev[N];
inline void init(int len)
{
bit=0;
while((1<<bit)<len)bit++;
tot=1<<bit;
for(int i=0;i<tot;i++)rev[i]=(rev[i>>1]>>1)|((i&1)<<bit-1);
}
inline int adj(int x){return (x>=mod)?x-mod:x;}
inline int qpow(int x,int k=mod-2)
{
int res=1;
while(k)
{
if(k&1)res=1ll*res*x%mod;
x=1ll*x*x%mod;
k>>=1;
}
return res;
}
inline void NTT(int *a,int inv)
{
for(int i=0;i<tot;i++)if(rev[i]<i)swap(a[rev[i]],a[i]);
for(int mid=1;mid<tot;mid<<=1)
{
int g=qpow(inv==1?G:Gi,(mod-1)/(mid<<1));
for(int i=0;i<tot;i+=(mid<<1))
for(int j=0,cur=1;j<mid;j++,cur=1ll*cur*g%mod)
{
int x=a[i+j],y=1ll*cur*a[i+j+mid]%mod;
a[i+j]=adj(x+y),a[i+j+mid]=adj(x-y+mod);
}
}
if(inv==-1)
{
int inv=qpow(tot,mod-2);
for(int i=0;i<tot;i++)a[i]=adj(1ll*a[i]*inv%mod+mod);
}
}
int main()
{
read(n);
for(int i=0,prod=1;i<=n;i++,prod=1ll*prod*i%mod)
{
int inv=qpow(prod);
a[i]=1ll*qpow(i,n)*inv%mod;
b[i]=((i&1)?mod-inv:inv);
}
n++;
init(n<<1);
NTT(a,1),NTT(b,1);
for(int i=0;i<tot;i++)a[i]=1ll*a[i]*b[i]%mod;
NTT(a,-1);
for(int i=0;i<n;i++)printf("%d ",a[i]);
return 0;
}
|
1.4 同一行第二类斯特林数的计算
2.第一类斯特林数
第一类斯特林数（斯特林轮换数）$\displaystyle {n \brack k}$，也可记作 $s(n,k)$，表示将 $n$ 个两两不同数，划分为 $k$ 个互不区分的非空轮换的方案数。
1.1 递推式
边界为 $\displaystyle {n \brack 0}=[n=0]$。
其组合意义与第二类斯特林数类似，不再赘述。
3.应用
记上升幂 $x^{\overline n}=\prod_{k=0}^{n-1}(x+k)=\frac{(x+n-1)!}{(x-1)!}$，下降幂 $x^{\underline n} =\prod_{k=0}^{n-1}(x-k)=\frac{x!}{(x-n)!}$。
我们发现他跟组合数相乘有很好的性质：
我们很多时候可以利用这一点来处理带组合数的问题。
3.1 普通幂与上升幂的相互转换
3.2 普通幂与下降幂升幂的相互转换
至于证明，$(1),(3)$ 式可以通过斯特林数的递推关系得到。$(2),(4)$ 式根据 $(1),(3)$ 式的结果，利用式子 $x^{\underline n}=(-1)^n (-x)^{\overline n}$ 容易得到。
利用这几条性质，我们可以容易实现普通幂多项式对下降幂多项式或者上升幂多项式的转化。
3.3 点值转下降幂表示
给定 $n$ 次多项式 $F(x)$ 在 $[0,n]$ 的点值，求出它的下降幂表示。
根据定义得到：
将 $F(x)$ 转为 $\text{EGF}$，得到：
于是得到 $b=\hat{F}(x)*e^{-x}$。卷积求出即可。详见
3.4 例题
有组合数？注意到 $n$ 很大，$m$ 比较小，我们尝试将带 $n$ 的枚举项消掉。先将普通幂多项式对下降幂多项式，设 $b_i$ 为 $f(x)$ 下降幂多项式形式的系数，即 $\displaystyle f(k)=\sum_{i=0}^m a_i k^i=\sum_{i=0}^m b_i k^{\underline i}$。
接下来就是推一下式子：
直接计算即可。
Code
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
| #include<iostream>
#include<cstdio>
using namespace std;
const int N=2e3+10;
template <class T>
inline void read(T &x)
{
x=0;bool f=0;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=1;ch=getchar();}
while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
if(f)x=-x;
}
template <class T,class ...T1>
inline void read(T &x,T1 &...x1)
{
read(x),read(x1...);
}
int n,x,mod,m;
int a[N],b[N];
int s[N][N];
inline int adj(int x){return x>=mod?x-mod:x;}
inline int qpow(int x,int k)
{
int res=1;
while(k)
{
if(k&1)res=1ll*res*x%mod;
x=1ll*x*x%mod;
k>>=1;
}
return res;
}
int main()
{
read(n,x,mod,m);
for(int i=0;i<=m;i++)read(a[i]),a[i]%=mod;
s[0][0]=1;
b[0]=a[0];
for(int i=1;i<=m;i++)
for(int j=1;j<=i;j++)
{
s[i][j]=adj(s[i-1][j-1]+1ll*j*s[i-1][j]%mod);
b[j]=adj(b[j]+1ll*a[i]*s[i][j]%mod);
}
x%=mod;
int ans=0;
for(int i=0,now=1;i<=m;now=1ll*now*(n-i)%mod*x%mod,i++)
ans=adj(ans+1ll*b[i]*now%mod*qpow(x+1,n-i)%mod);
printf("%d\n",ans);
return 0;
}
|
和上一道题几乎一模一样。其中 $\displaystyle f(k)=\sum_{i=0}^m a_i k^i=\sum_{i=0}^m b_i k^{\underline i}$，推一下即可得到：
只不过 $m\le 2\times 10^4$。需要将点值转下降幂表示求出 $b$。时间复杂度为 $\mathcal O(m\log m)$。
但是对此我们更简单的做法。我们设 $c_i=b_i\times i!$，容易得到：
于是直接利用二项式反演即可得到：
卷积得到即可 $\mathcal O(n\log n)$ 得到 $c$。这样可以避免点值转下降幂表示求出 $b$。两种方法本质上是一样的。