斯特林数一共分为两类，较第一类来说，第二类斯特林数更加常用，接下来分别介绍他们。
第一类斯特林数：
定义：
用 \(s(n,m)\) 表示第一类斯特林数，其含义是把 \(n\) 个数分成 \(m\) 个圆排列的方案数。
递推式：
\(s(n,m)\) 由两种构造方式推导而来。
第一种，考虑对于前 \(n - 1\) 个数形成 \(m - 1\) 个圆排列，只要将当前处理的第 \(n\) 个数单独形成一个圆排列，就可以将这 \(n\) 个数分成 \(m\) 个圆排列。
第二种，考虑前 \(n - 1\) 个数形成了 \(m\) 个圆排列，此时只需要任选一个圆排列，将第 \(n\) 个数插入进去，就可以将这 \(n\) 个数分成 \(m\) 个圆排列。其中，在将第 \(n\) 个元素插入的时候，前 \(n - 1\) 个元素形成了 \(n - 1\) 个空位，有 \(n - 1\) 种插入方法。
综上，第一类斯特林数的递推式为：
\[s[n][m] = s[n - 1][m - 1] + (n - 1) * s[n - 1][m] \]边界条件为 \(s[n][1] = (n - 1)!\) 和 \(s[n][n] = 1\)。
应用：
说实话遇到的需要用第一类斯特林数来解决的题目其实并不是很多……这里还是放几道题来分享学习下。
1.[HDU 3625] Examining the Rooms
酒店里发生了一起谋杀案。作为镇上最好的侦探，您应该立即检查酒店的所有 \(N\) 个房间。然而，房间的所有门都被锁上了，钥匙只是锁在房间里，真是一个陷阱！您知道每个房间只有一个密钥，并且所有可能的分布都具有相等的可能性。例如，如果 \(N = 3\)，则有 \(6\) 个可能的分布，每个分布的可能性为 \(1/6\)。为了方便起见，我们将房间从 \(1\) 编号到 \(N\)，房间 \(1\) 的钥匙编号为钥匙 \(1\)，房间 \(2\) 的钥匙是钥匙 \(2\)，依此类推，
要检查所有房间，你必须用力摧毁一些门。但是你不想破坏太多，所以你采取以下策略：起初，你手里没有钥匙，所以你随机摧毁一扇锁着的门，进入房间，检查它，然后拿到里面的钥匙。然后，也许你可以用新钥匙打开另一个房间，检查它并得到第二把钥匙。重复此操作，直到您无法打开任何新房间。如果仍然有房间未检查，您必须随机选择另一扇未打开的门以强制销毁，然后重复上述过程，直到所有房间都检查完毕。
现在，你最多只能用武力摧毁 \(k\) 扇门。更重要的是，\(1\) 号房间里有一个非常重要的人。你不被允许破坏 \(1\) 号房间的门，也就是说，检查 \(1\) 号房间的唯一方法是用相应的钥匙打开它。你想知道你最终能检查所有房间的概率。
分析：
炸开一扇门，拿走里面的钥匙，开启另一扇门，再拿走这个房间里面的钥匙，再打开一扇门……如此循环下去，直到打开的房间里面的钥匙对应的是已经打开过的房间的钥匙。这个过程其实就了一个圆排列。对于 \(N\) 个房间，\(K\) 个炸门机会，如果能打开所有门，那么 \(N\) 个房间所形成的能满足条件的圆排列方案数为：
\[\sum_{i = 0}^ks[n][i] \]因为不能使第一个房间单独成为一个圆排列，因此还要将这种情况减去，最终答案为：
\[\sum_{i = 1}^ks[n][i] - s[n - 1][i - 1] \]Code:
点击查看代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN = 20;
long long s[MAXN + 5][MAXN + 5],n;
int fact(int a){
int ret = 1;
while(a){
ret = (long long)a * ret;
a--;
}
return ret;
}
int t,k;
signed main(){
s[0][0] = 1;
for(int i = 1; i <= MAXN; i++){
s[i][i] = 1;
s[i][1] = fact(i - 1);
}
for(int i = 1; i <= MAXN; i++){
for(int j = 2; j < i; j++){
s[i][j] = (s[i - 1][j - 1] + (long long)(i - 1) * s[i - 1][j]);;
//cout << s[i][j] << "\n";
}
}
cin >> t;
while(t--){
cin >> n >> k;
int ans = 0;
for(int i = 1; i <= k; i++){
ans += s[n][i] - s[n - 1][i - 1];
}
double an = 1.0 * ans / fact(n);
printf("%.4lf\n",an);
}
return 0;
}
2.HDU 4372 Count the Buildings
城市中有 \(N\) 座建筑物直线站立，编号从 \(1\) 到 \(N\)。所有建筑物的高度都是不同的，介于 \(1\) 和 \(N\) 之间。当你站在第一栋建筑前面向前看时，你可以看到 \(F\) 栋，当你站在最后一栋建筑后面向后看时，你可以看到 \(B\) 栋建筑。如果建筑物比您与其之间的任何建筑物都高，则可以看到建筑物。
现在，给定 \(N\)，\(F\)，\(B\)，你的任务是弄清楚所有建筑物可以有多少种方式。
无论从那个方向看，最高的楼都是会被看见的。因此问题变为将剩下的 \(N - 1\) 个数划分成 \(F - 1 + B - 1\) 个集合，保证该集合里最大的元素在前面，求一共有多少方案，并从这 \(F+B - 2\) 个集合中选取 \(F - 1\) 个放到最高楼的左边即可。就是求裸的第一类斯特林数。
点击查看代码
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 2e3;
const int MOD = 1e9 + 7;
int f[MAXN + 5],inv[MAXN + 5],s[MAXN + 5][MAXN + 5],n;
int qpow(int a,int n){
int ret = 1;
while(n){
if(n & 1){
ret = (long long)ret * a % MOD;
}
n /= 2;
a = (long long)a * a % MOD;
}
return ret;
}
void init(){
f[0] = 1;
for(int i = 1;i <= MAXN; i++){
f[i] = (long long)f[i - 1] * i % MOD;
}
inv[MAXN] = qpow(f[MAXN],MOD - 2);
for(int i = MAXN; i >= 1; i--){
inv[i - 1] = (long long)inv[i] * i % MOD;
}
}
int c(int a,int b){
return (long long)f[a] * inv[b] % MOD * inv[a - b] % MOD;;
}
int t,ff,b;
int main(){
cin >> t;
s[0][0] = 1;
init();
for(int i = 1; i <= MAXN; i++){
s[i][i] = 1;
s[i][1] = f[i - 1];
}
for(int i = 1; i <= MAXN; i++){
for(int j = 2; j < i; j++){
s[i][j] = (s[i - 1][j - 1] + (long long)(i - 1) * s[i - 1][j]) % MOD;;
//cout << s[i][j] << "\n";
}
}
while(t--){
cin >> n >> ff >> b;
if(ff + b - 1 > n || max(ff,b) <= 1) {
printf("0\n");
continue;
}
cout << (long long)s[n - 1][b + ff - 2] * c(b + ff - 2,b - 1) % MOD << "\n";;
}
return 0;
}
第二类斯特林数：
定义：令 \(S(n,m)\) 表示将 \(n\) 个元素划分成 \(m\) 个集合的方案数。
递推式：
仍按照递推第一类斯特林数的方法进行思考。如果前 \(n - 1\) 个数形成 了 \(m - 1\) 个集合，那么直接将第 \(n\) 个数单独形成一个集合即可。如果前 \(n - 1\) 个数形成了 \(m\) 个集合，只需要将第 \(n\) 个数插入其中任意一个集合中即可。递推式为：
\[S[n][m] = S[n - 1][m - 1] + m * S[n - 1][m] \]边界条件为 \(S[n][n] = 1\) 和 S[n][1] = 1$。
第二类斯特林数还有一个重要的通项公式：
\[S[n][m] = \frac{1}{m!} \times \sum_{i = 1}^m\{{(-1)^i \times {m \choose i} * (m - i)^n}\} \]至于怎么得出的，我也不知道。知道的可以在评论区里分享一下。
习题：
1.CF1342E Placing Rooks
有这样一个问题：
在 \(n \times n\) 的国际象棋棋盘上放 \(n\) 个车，要求满足两个条件：
所有的空格子都能被至少一个车攻击到。
恰好有 \(k\) 对车可以互相攻击到。
答案对 \(998244353998244353\) 取模。
分析：
好题。
保证每一个格子都要被攻击到，换句话说，就是要每一行都有一个棋子，这就大大简化了问题了。
一个重要的结论：如果有 \(k\) 对棋子能互相攻击，那么所有棋子应该分成 \(n - k\) 列。
那么，只是求 \(S[n][n - k]\) 就结束了吗？这 \(n - k\) 列在 \(n\) 列中的放置方案并不只有一种，且排列方式也不止一种（有 \((n - k）!\) 种排列方式）。
综上，答案为：
\[S[n][n - k] * {n \choose {n - k}} * (n - k)! \]假如当前方案并不只是一列，那么还可以将其旋转一次得到新的方案，此时就应该将答案乘 \(2\)。
Code：
点击查看代码
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 2e5;
const int MOD = 998244353;
int inv[MAXN + 5],f[MAXN + 5];
int qpow(int a,int n){
int ret = 1;
while(n){
if(n & 1){
ret = (long long)ret * a % MOD;
}
n /= 2;
a = (long long)a * a % MOD;
}
return ret;
}
void init(){
f[0] = 1;
for(int i = 1; i <= MAXN; i++){
f[i] = (long long)f[i - 1] * i % MOD;
//cout << f[i] << "\n";
}
inv[MAXN] = qpow(f[MAXN],MOD - 2);
for(int i = MAXN; i > 0; i--){
inv[i - 1] = (long long)inv[i] * i % MOD;
}
}
int c(int a,int b){
return (long long)f[a] * inv[b] % MOD * inv[a - b] % MOD;;
}
int s(int n,int m){
long long ans = 0;
for(int i = 0; i <= m; i++){
int t = (i % 2 == 0) ? 1 : -1;
ans = (1ll * ans % MOD + t * ((long long)c(m,i) % MOD * qpow(m - i,n) % MOD)) % MOD;
ans %= MOD;
// cout << c(m,i) << " " << qpow(m - i,n) << " " << c(m,i) * qpow(m - i,n) % MOD << " " << ans << "\n";
}
ans = 1ll * ans * inv[m] % MOD;
return ans;
}
signed main(){
init();
int a,b;
cin >> a >> b;
if(a - 1 < b){
cout << "0";
return 0;
}
cout << (((b == 0) ? 1 : 2) * (long long)s(a,a - b) * c(a,a - b) % MOD * f[a - b] % MOD + MOD) % MOD;;
}
2.第二类斯特林数的奇偶性分析：
给定 \(n\) \(m\)，求 \(S[n][m] \mod 2\)
（借鉴了大佬@LuckyGlass的思想）
考虑对 \(m\) 的奇偶情况进行分类讨论。
当 \(m\) 为偶数时，用 \(2m\) 表示 \(m\)。在这种情况下，因为只用关注奇偶性，可以将递推式变成如下形式：
\[s[n][2m] = s[n - 1][2m - 1] \]当 \(m\) 为奇数时，用 \(2m + 1\) 表示 \(m\)。同样只因为关注奇偶性，将递推式变为：
\[s[n][2m + 1] = s[n - 1][2m] + s[n - 1][2m + 1] \]注意到，这两种转移在图上是这样表现的：
可以看出，这个问题就相当于求点 \((n,m)\) 到点 \((0,0)\) 的路径的总数。
再细致观察，图中的点大体上分为十字交叉的蓝点和一条直线上的黄点两种点。这两种点分别对应 \(m\) 为奇数和偶数两种情况。
容易证明，从 \((0,0)\) 移动到 \((n,m)\) 只能移动 \(n\) 步，且只有两种移动方式：
- 从 \((x,y)\) 移动到 \((x + 1,y + 1)\)
- 从 \((x,y)\) 移动到 \((x + 1,y)\)
当 \(y\) 为奇数时，只能选择第一种移动方式，当 \(y\) 为偶数时，可以同时选择两种移动方式。
并且，除了第一步以外，所有第一种移动方式都是成对出现的，因为你会移动到 \(y\) 为奇数的点，这样你又只能选择第一种移动方式。
所以，你采用的移动方式必然为：第一种移动方式，若干次第二种移动方式，第一种移动方式，第一种移动方式，若干次第二种移动方式…………第一种移动方式。
由于第一种移动方式是两两一组的，那么在它们之间的间隔，可以放零到若干次第二种移动方式。这样的间隔一共有 \(\frac{m + 1}{2}\) 个。
令 \(a = n - m,b = \frac{m + 1}{2}\)，则答案为：\({a + b - 1} \choose {b - 1}\)
接下来，我们只需要判断组合数的奇偶性即可。这里需要用到一个结论，即如果 \(n \& m == m\) 那么 \(n \choose m\) 为奇数。
Code:
点击查看代码
#include<iostream>
using namespace std;
int t,m,n;
int main(){
cin >> t;
while(t--){
cin >> n >> m;
if((m & 1) == 0){
m--,n--;
}
n = n - m / 2;
m = (m + 1) / 2;
n--,m--;
if((n & m) == m)cout << "1\n";
else cout << "0\n";
}
}