斯特林数 - 腾云今天首飞了吗
source link: https://www.cnblogs.com/CZ-9/p/16610466.html
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
斯特林数一共分为两类，较第一类来说，第二类斯特林数更加常用，接下来分别介绍他们。
第一类斯特林数：
用 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("%.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][n]=1 和 S[n][1] = 1$。
第二类斯特林数还有一个重要的通项公式：
至于怎么得出的，我也不知道。知道的可以在评论区里分享一下。
1.CF1342E Placing Rooks
有这样一个问题：
在 n×n 的国际象棋棋盘上放 n 个车，要求满足两个条件：
所有的空格子都能被至少一个车攻击到。
恰好有 k 对车可以互相攻击到。
答案对 998244353998244353 取模。
好题。
保证每一个格子都要被攻击到，换句话说，就是要每一行都有一个棋子，这就大大简化了问题了。
一个重要的结论：如果有 k 对棋子能互相攻击，那么所有棋子应该分成 n−k 列。
那么，只是求 S[n][n−k] 就结束了吗？这 n−k 列在 n 列中的放置方案并不只有一种，且排列方式也不止一种（有 ）(n−k）! 种排列方式）。
综上，答案为：
假如当前方案并不只是一列，那么还可以将其旋转一次得到新的方案，此时就应该将答案乘 2。
Code：
点击查看代码
2.第二类斯特林数的奇偶性分析：
给定 nm，求 S[n][m]mod2
（借鉴了大佬@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 为奇数的点，这样你又只能选择第一种移动方式。
所以，你采用的移动方式必然为：第一种移动方式，若干次第二种移动方式，第一种移动方式，第一种移动方式，若干次第二种移动方式…………第一种移动方式。
由于第一种移动方式是两两一组的，那么在它们之间的间隔，可以放零到若干次第二种移动方式。这样的间隔一共有 m+12 个。
令 a=n−m,b=m+12，则答案为：(a+b−1b−1)
接下来，我们只需要判断组合数的奇偶性即可。这里需要用到一个结论，即如果 n&m==m 那么 (nm) 为奇数。
Code:
点击查看代码
__EOF__
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK