1013 字
5 分钟
斯特林数 (Stirling Numbers)
斯特林数 (Stirling Numbers)
第一类斯特林数(斯特林轮换数)
将 个不同元素,划分为 个非空圆排列的方案数,记作 或 。
递推式:
组合意义: 个人坐 张圆桌的方案数。考虑第 个人:
- 若单独坐一桌,前面 人坐 张桌子,方案数为 ;
- 若坐到已有人的桌子上,先让前 个人坐 张桌子,第 个人可以坐到这 个人中任意一个人的左边,方案数为 。
第二类斯特林数(斯特林子集数)
将 个不同元素,划分为 个非空子集的方案数,记作 或 。
递推式:
组合意义: 个不同的小球放入 个无标号盒子的方案数。考虑第 个小球:
- 若单独放入一个新盒子,前面 个球放入 个盒子,方案数为 ;
- 若放入已有球的盒子中,前面 个球已放入 个盒子,第 个球有 种选择,方案数为 。
容斥通项公式:
经典应用一:P4609 [FJOI2016] 建筑师
高度为 的建筑是一个分水岭,在它左边有 个建筑群(每个建筑群左边一个最高建筑,剩下的建筑自由排列,数量等于圆排列的数量),在它右边有 个建筑群。每个建筑群构成一个圆排列,共计 个圆排列。即把 个建筑划分成 个圆排列,即 。然后从圆排列数中拿出 个放在 的左边,即 。
答案:。
#include <bits/stdc++.h>#define ll long long#define N 50005#define M 205using namespace std;ll t;ll c[N][M];ll s[N][M];const int mod = 1e9 + 7;void init() { for (int i = 0; i < N; i++) { c[i][0] = 1; s[i][0] = (i == 0 ? 1 : 0); } for (int i = 1; i < N; i++) { for (int j = 1; j < M; j++) { c[i][j] = (c[i - 1][j - 1] + c[i - 1][j]) % mod; } } for (int i = 1; i < N; i++) { for (int j = 1; j < M; j++) { s[i][j] = (s[i - 1][j - 1] + (i - 1) * s[i - 1][j]) % mod; } }}int main() { ios::sync_with_stdio(0); cin.tie(nullptr); cout.tie(nullptr); init(); cin >> t; while (t--) { ll n, a, b; cin >> n >> a >> b; if (a + b - 2 >= M || a + b - 2 < 0) { cout << 0 << '\n'; continue; } cout << (s[n - 1][a + b - 2] * c[a + b - 2][a - 1]) % mod << '\n'; } return 0;}经典应用二:第二类斯特林数递推与高精度 (P3904)
将 个互不相同的元素划分为 个非空集合的方案数,递推关系 。
#include <bits/stdc++.h>using namespace std;// 高精度整数辅助类struct BigInt { vector<int> a; BigInt(long long v = 0) { if (v == 0) a.push_back(0); while (v > 0) { a.push_back(v % 10); v /= 10; } } BigInt operator+(const BigInt &o) const { BigInt c; c.a.clear(); int carry = 0, n = max(a.size(), o.a.size()); for (int i = 0; i < n || carry; i++) { if (i < a.size()) carry += a[i]; if (i < o.a.size()) carry += o.a[i]; c.a.push_back(carry % 10); carry /= 10; } return c; } BigInt operator*(int m) const { BigInt c; c.a.clear(); long long carry = 0; for (int i = 0; i < a.size() || carry; i++) { if (i < a.size()) carry += 1LL * a[i] * m; c.a.push_back(carry % 10); carry /= 10; } while (c.a.size() > 1 && c.a.back() == 0) c.a.pop_back(); return c; } void print() const { for (int i = (int)a.size() - 1; i >= 0; i--) cout << a[i]; cout << '\n'; }};BigInt S[105][105];int main() { ios::sync_with_stdio(0); cin.tie(nullptr); int n, m; if (!(cin >> n >> m)) return 0; S[0][0] = BigInt(1); for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { S[i][j] = S[i - 1][j - 1] + S[i - 1][j] * j; } } S[n][m].print(); return 0;}斯特林数 (Stirling Numbers)
https://sanzenin.top/posts/obsidian/斯特林数/分享文章
生成精美分享图或复制链接,与更多人分享本文。
继续阅读
换条路线
从其他文章中稳定抽取
最后更新于 ,距今已过 74 天
部分内容可能已过时