斯特林数
斯特林数解决什么问题？
第二类斯特林数：将
n
n
n 个不同的元素划分为
k
k
k 个无标号的非空集合的方案数。
例：把
5
5
5 个球放在
3
3
3 张相同的盒子里，每个盒子至少一个球，有多少种放法？
第一类斯特林数：将
n
n
n 个不同的元素划分为
k
k
k 个无标号的非空轮换的方案数。
例：把
5
5
5 个人安排在
3
3
3 张相同的圆桌旁就坐，每张桌子至少一个人，有多少种坐法？
第二类斯特林数
定义：
第二类斯特林数记作
S
(
n
,
k
)
S(n,k)
S(n,k)，表示将
n
n
n 个不同的元素划分为
k
k
k 个无标号的非空集合的方案数。
核心性质：
- 集合无标号：交换两个集合的位置不算新方案
- 集合非空：每个集合至少包含一个元素
- 元素不同：元素有区别。
边界条件：
-
S
(
n
,
0
)
=
0
(
n
>
0
)
S(n,0)=0(n>0)
S(n,0)=0(n>0) -
S
(
0
,
k
)
=
0
(
k
>
0
)
S(0,k)=0(k>0)
S(0,k)=0(k>0) -
S
(
0
,
0
)
=
1
S(0,0)=1
S(0,0)=1 -
S
(
n
,
n
)
=
1
S(n,n)=1
S(n,n)=1 -
S
(
n
,
1
)
=
1
S(n,1)=1
S(n,1)=1 -
S
(
n
,
k
)
=
0
(
k
>
n
)
S(n,k)=0(k>n)
S(n,k)=0(k>n)
递推公式：
S
(
n
,
k
)
=
k
×
S
(
n
−
1
,
k
)
+
S
(
n
−
1
,
k
−
1
)
S(n,k)=k\\times S(n-1,k)+S(n-1,k-1)
S(n,k)=k×S(n−1,k)+S(n−1,k−1)
通项公式
S
(
n
,
k
)
=
1
k
!
∑
i
=
0
k
(
−
1
)
i
C
k
i
(
k
−
i
)
n
S(n,k)=\\frac{1}{k!}\\sum_{i=0}^k(-1)^iC_k^i(k-i)^n
S(n,k)=k!1i=0∑k(−1)iCki(k−i)n
重要性质
1. 幂次展开为下降幂
n
k
=
∑
i
=
0
k
S
(
k
,
i
)
i
!
C
n
i
=
∑
i
=
0
k
S
(
k
,
i
)
n
i
‾
n^k=\\sum_{i=0}^kS(k,i)i!C_n^i=\\sum_{i=0}^kS(k,i)n^{\\underline i}
nk=i=0∑kS(k,i)i!Cni=i=0∑kS(k,i)ni
其中
n
i
‾
=
n
×
(
n
−
1
)
⋯
×
(
n
−
i
+
1
)
n^{\\underline i}=n\\times (n-1)\\dots\\times (n-i+1)
ni=n×(n−1)⋯×(n−i+1)
第一类斯特林数
定义：
第一类斯特林数记作
s
(
n
,
k
)
s(n,k)
s(n,k)，表示将
n
n
n 个不同的元素划分为
k
k
k 个无标号的非空轮换的方案数。
核心性质：
- 集合无标号：交换两个轮换的位置不算新方案
- 集合非空：每个轮换至少包含一个元素
- 元素不同：元素有区别。
边界条件：
-
S
(
n
,
0
)
=
0
(
n
>
0
)
S(n,0)=0(n>0)
S(n,0)=0(n>0) -
S
(
0
,
k
)
=
0
(
k
>
0
)
S(0,k)=0(k>0)
S(0,k)=0(k>0) -
S
(
0
,
0
)
=
1
S(0,0)=1
S(0,0)=1 -
S
(
n
,
n
)
=
1
S(n,n)=1
S(n,n)=1 -
S
(
n
,
1
)
=
(
n
−
1
)
!
S(n,1)=(n-1)!
S(n,1)=(n−1)! -
S
(
n
,
k
)
=
0
(
k
>
n
)
S(n,k)=0(k>n)
S(n,k)=0(k>n)
递推公式：
S
(
n
,
k
)
=
(
n
−
1
)
×
S
(
n
−
1
,
k
)
+
S
(
n
−
1
,
k
−
1
)
S(n,k)=(n-1)\\times S(n-1,k)+S(n-1,k-1)
S(n,k)=(n−1)×S(n−1,k)+S(n−1,k−1)
重要性质
1. 下降幂展开为幂次
n
k
‾
=
∑
i
=
0
k
(
−
1
)
k
−
i
s
(
k
,
i
)
n
i
n^{\\underline k}=\\sum_{i=0}^k(-1)^{k-i}s(k,i)n^i
nk=i=0∑k(−1)k−is(k,i)ni
其中
n
i
‾
=
n
×
(
n
−
1
)
⋯
×
(
n
−
i
+
1
)
n^{\\underline i}=n\\times (n-1)\\dots\\times (n-i+1)
ni=n×(n−1)⋯×(n−i+1)
2. 上升幂展开为幂次
n
k
‾
=
∑
i
=
0
k
s
(
k
,
i
)
n
i
n^{\\overline k}=\\sum_{i=0}^ks(k,i)n^i
nk=i=0∑ks(k,i)ni
其中
n
i
‾
=
n
×
(
n
+
1
)
⋯
×
(
n
+
i
−
1
)
n^{\\overline i}=n\\times (n+1)\\dots\\times (n+i-1)
ni=n×(n+1)⋯×(n+i−1)
二项式反演
形式一：前缀和型
正变换：若数列
g
(
n
)
g(n)
g(n) 满足
g
(
n
)
=
∑
k
=
0
n
S
(
n
,
k
)
⋅
f
(
k
)
g(n)=\\sum_{k=0}^{n} S(n,k)\\cdot f(k)
g(n)=k=0∑nS(n,k)⋅f(k)
反演公式：则
f
(
n
)
=
∑
k
=
0
n
(
−
1
)
n
−
k
⋅
s
(
n
,
k
)
g
(
k
)
f(n)=\\sum_{k=0}^{n}(-1)^{n-k}\\cdot s(n,k)\\,g(k)
f(n)=k=0∑n(−1)n−k⋅s(n,k)g(k)
其中
s
(
n
,
k
)
s(n,k)
s(n,k) 为第一类斯特林数，适用场景为普通幂与下降幂的互相表示。
形式二：后缀和型
正变换：若数列
f
(
k
)
f(k)
f(k) 满足
f
(
k
)
=
∑
i
=
k
n
S
(
i
,
k
)
⋅
g
(
i
)
f(k)=\\sum_{i=k}^{n} S(i,k)\\cdot g(i)
f(k)=i=k∑nS(i,k)⋅g(i)
反演公式：则
g
(
k
)
=
∑
i
=
k
n
(
−
1
)
i
−
k
⋅
s
(
i
,
k
)
⋅
f
(
i
)
g(k)=\\sum_{i=k}^{n}(-1)^{i-k}\\cdot s(i,k)\\cdot f(i)
g(k)=i=k∑n(−1)i−k⋅s(i,k)⋅f(i)
组合意义
-
g
(
i
)
g(i)
g(i)：恰好将元素划分为i
i
i 个非空、有标号组的方案数 -
f
(
k
)
f(k)
f(k)：先把元素任意划分，再将组合并成k
k
k 个有标号大类的方案数（即至少k
k
k 个非空类的加权计数）
从组合意义理解正变换： 要得到
k
k
k 个大类，可以先将元素恰好分成
i
i
i 个小非空组，再把这
i
i
i 个小组划分成
k
k
k 个非空大类（对应第二类斯特林数
S
(
i
,
k
)
S(i,k)
S(i,k)）。因此：
f
(
k
)
=
∑
i
=
k
n
S
(
i
,
k
)
⋅
g
(
i
)
f(k)=\\sum_{i=k}^{n} S(i,k)\\cdot g(i)
f(k)=i=k∑nS(i,k)⋅g(i)
斯特林数的正交性
∑
k
=
m
n
(
−
1
)
n
−
k
s
(
n
,
k
)
S
(
k
,
m
)
\\sum_{k=m}^{n} (-1) ^ {n – k} s(n, k) S(k, m)
k=m∑n(−1)n−ks(n,k)S(k,m)
在
n
=
m
n=m
n=m 时答案为
1
1
1 否则答案为
0
0
0。
例题
P10591 BZOJ4671 异或图
传送门
n
n
n 个点一种划分；
g
(
k
)
g(k)
g(k) 表示将所有点恰好划分为k个连通块的方案数；答案为
g
(
1
)
g(1)
g(1);
f
(
k
)
f(k)
f(k) 固定有
k
k
k 个组，所有元素划分到k个组中，且组间没有连边，组内的选边任意的方案数。
i
i
i 个连通块(不同的小球)，放入
k
k
k 个相同的盒子，不允许空盒，则重复次数
S
(
i
,
k
)
S(i,k)
S(i,k)，因此，可以进行正变换，所以问题转化为求
f
(
k
)
f(k)
f(k)。
2
2
2 个大组中，则这条边在异或图中不能出现，设有
c
n
t
cnt
cnt 条这样的边，每条边看作一个方程，
s
s
s 张图看作
s
s
s 个未知数，取值为1或者0，转化为异或方程组；
f
(
k
)
f(k)
f(k), 则线性基求出异或方程组的自由元的数量
c
c
c,
f
(
k
)
=
2
c
f(k)=2^c
f(k)=2c;
g
(
1
)
=
∑
i
=
1
n
(
−
1
)
i
−
1
⋅
S
(
i
,
1
)
⋅
2
c
g(1)=\\sum_{i=1}^n (-1)^{i-1}\\cdot S(i,1)\\cdot 2^c
g(1)=i=1∑n(−1)i−1⋅S(i,1)⋅2c
g
(
1
)
=
∑
i
=
1
n
(
−
1
)
i
−
1
⋅
(
i
−
1
)
!
⋅
2
c
g(1)=\\sum_{i=1}^n (-1)^{i-1}\\cdot (i-1)!\\cdot 2^c \\quad
g(1)=i=1∑n(−1)i−1⋅(i−1)!⋅2c
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MAXX = 5e4 + 5;
int n, num[MAXX], pw[MAXX], s[MAXX], arr[MAXX / 100], zrr, ans, vis[MAXX], len, N;
string S[MAXX];
int qpow(int a, int b){
int res = 1;
while(b){
if(b & 1) res = res * a;
a = a * a, b >>= 1;
}
return res;
}
void init(){
num[0] = pw[0] = 1;
for(int i = 1; i <= 60; i++) num[i] = num[i – 1] * i;
for(int i = 1; i <= 60; i++) pw[i] = pw[i – 1] * 2;
}
void check(int x){
for(int i = 60; i >= 0; i—){
if((x >> i) & 1){
if(!arr[i]){
arr[i] = x, zrr++;
break;
}else x ^= arr[i];
}
}
}
void dfs(int x, int cnt){
if(x == n + 1){
int res = 0, id = 0;
for(int i = 1; i <= n; i++){
for(int j = i + 1; j <= n; j++){
if(vis[i] != vis[j]) res |= (1ll << id); id++;
}
}
memset(arr, 0, sizeof(arr)); zrr = 0;
for(int i = 1; i <= N; i++) check(s[i] & res);
int tot = N – zrr;
if(cnt & 1) ans += num[cnt – 1] * pw[tot];
else ans -= num[cnt – 1] * pw[tot];
return;
}else{
for(int i = 1; i <= cnt + 1; i++){
vis[x] = i, dfs(x + 1, max(i, cnt));
}
}
}
signed main(){
cin >> N; init();
for(int i = 1; i <= N; i++){
cin >> S[i]; len = S[i].size();
if(i == 1){
for(int j = 2; j <= 10; j++){
if(j * (j – 1) / 2 == len){
n = j; break;
}
}
}
int id = 0;
s[i] = 0;
for(int j = 1; j <= n; j++){
for(int k = j + 1; k <= n; k++){
if(S[i][id] == '1') s[i] |= (1ll << id);
id++;
}
}
}
dfs(1, 0);
cout << ans << '\\n';
return 0;
}
