斯特林数一共分为两类，较第一类来说，第二类斯特林数更加常用，接下来分别介绍他们。
第一类斯特林数：
定义：
用 (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][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) 个房间所形成的能满足条件的圆排列方案数为：
因为不能使第一个房间单独成为一个圆排列，因此还要将这种情况减去，最终答案为：
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("%.4lfn",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("0n"); 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][n] = 1) 和 S[n][1] = 1$。
第二类斯特林数还有一个重要的通项公式：
至于怎么得出的，我也不知道。知道的可以在评论区里分享一下。
习题：
1.CF1342E Placing Rooks
有这样一个问题：
在 (n times n) 的国际象棋棋盘上放 (n) 个车，要求满足两个条件：
所有的空格子都能被至少一个车攻击到。
恰好有 (k) 对车可以互相攻击到。
答案对 (998244353998244353) 取模。
分析：
好题。
保证每一个格子都要被攻击到，换句话说，就是要每一行都有一个棋子，这就大大简化了问题了。
一个重要的结论：如果有 (k) 对棋子能互相攻击，那么所有棋子应该分成 (n - k) 列。
那么，只是求 (S[n][n - k]) 就结束了吗？这 (n - k) 列在 (n) 列中的放置方案并不只有一种，且排列方式也不止一种（有 ((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)。在这种情况下，因为只用关注奇偶性，可以将递推式变成如下形式：
当 (m) 为奇数时，用 (2m + 1) 表示 (m)。同样只因为关注奇偶性，将递推式变为：
注意到，这两种转移在图上是这样表现的：
可以看出，这个问题就相当于求点 ((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 << "1n"; else cout << "0n"; } } 
