[CF1342E] Placing Rooks - 第二类斯特林数
2021/4/13 18:25:08
本文主要是介绍[CF1342E] Placing Rooks - 第二类斯特林数,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
[CF1342E] Placing Rooks - 第二类斯特林数
Description
在 \(n \times n\) 的国际象棋棋盘上放 \(n\) 个车,要求满足两个条件:所有的空格子都能被至少一个车攻击到。恰好有 \(k\) 对车可以互相攻击到。
Solution
如果 \(k \ge n\) 那么显然是不可能的
行和列至少有一个是满的,现在我们假设行是满的,看列
每缺一个列,就意味着有两个家伙可以共列,也就多了一对相互攻击
现在我们令 \(m=n-k\),也就是实际有东西的列数
首先我们要把这些列选出来,贡献一个二项式系数
然后我们要对 \(n\) 行每行让它选一列,同时保证 \(m\) 列都至少出现一次
第二类斯特林数是把 \(n\) 个不同的元素分为 \(m\) 个不可分别的集合,我们再送它一个 \(m!\) 就变成了可分的集合,因此答案就是
\[\binom n m S_2(n,m) m! \]第二类斯特林数可以转化为线性多个组合数等玩意的和计算
#include <bits/stdc++.h> using namespace std; #define int long long const int mod = 998244353; int qpow(int p, int q) { return (q & 1 ? p : 1) * (q ? qpow(p * p % mod, q / 2) : 1) % mod; } int inv(int p) { return qpow(p, mod - 2); } const int N = 1e6 + 5; int fac[N]; void init() { fac[0] = 1; for (int i = 1; i < N; i++) fac[i] = fac[i - 1] * i % mod; } int binom(int n, int m) { return fac[n] * inv(fac[m]) % mod * inv(fac[n - m]) % mod; } int stirling(int n, int m) { int ans = 0; for (int i = 0; i <= m; i++) { int k = i; ans += (k & 1 ? mod - 1 : 1) * binom(m, k) % mod * qpow(m - k, n) % mod; ans %= mod; ans += mod; ans %= mod; } ans *= inv(fac[m]); ans %= mod; return ans; } signed main() { ios::sync_with_stdio(false); init(); int n, k; cin >> n >> k; if (k >= n) cout << 0 << endl; else cout << stirling(n, n - k) * binom(n, n - k) % mod * (k == 0 ? 1 : 2) % mod * fac[n - k] % mod << endl; }
这篇关于[CF1342E] Placing Rooks - 第二类斯特林数的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-06-30uniAPP 实现全屏左右滚动滚动的效果-icode9专业技术文章分享
- 2024-06-30如何在本地使用授权或插件-icode9专业技术文章分享
- 2024-06-30伪静态规则配置方法汇总-icode9专业技术文章分享
- 2024-06-29易优CMS安装常见问题汇总-icode9专业技术文章分享
- 2024-06-28易优新手必读安装教程-icode9专业技术文章分享
- 2024-06-28忘记eyoucms后台密码怎么办?-icode9专业技术文章分享
- 2024-06-26终极指南:Scrum中如何设置需求优先级
- 2024-06-26AI大模型企业应用实战(25)-为Langchain Agent添加记忆功能
- 2024-06-26小白家庭 nas 搭建方案-icode9专业技术文章分享
- 2024-06-23AI大模型企业应用实战(14)-langchain的Embedding