Codeforces Round #818 (Div. 2) D Madoka and The Corruption Scheme
2022/9/3 23:25:10
本文主要是介绍Codeforces Round #818 (Div. 2) D Madoka and The Corruption Scheme,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
Madoka and The Corruption Scheme
组合数 + 思维 + 贪心
首先要思考一开始要如何摆放才是最优秀的
按照完全二叉树(根就是最后赢的那个),给所有的点赋予权值,代表需要转换多少条边,才能使得这个点的数字被选上
显然假设当前点的权值为 \(x\),该点的其中一个节点权值必然为 \(x\)(获胜),另一个点的权值必然是 \(x + 1\)(失败)
图中点的数字代表其权值,贪心地想,我们肯定要将小的数字尽可能的放置在权值低的点上(叶子),让别人尽可能的拿不到大的数字
通过观察发现,每一层的权值的种类与数量是杨辉三角的样子,所以如果能改 \(k\) 次,就相当于第 \(n\) 层的前 \(k\) 个值的和,都可以被调整为最终的胜利者
层 \ 点数量 \ 点权值 | 0 | 1 | 2 | 3 |
---|---|---|---|---|
0 | 1 | |||
1 | 1 | 1 | ||
2 | 1 | 2 | 1 | |
3 | 1 | 3 | 3 | 1 |
第一列代表层数,第一行代表点权值,\(a_{ij}\) 代表第 \(i\) 层,权值为 \(j\) 的点个数
其实,因为每个点都会引申出一个本身权值,以及本身权值加一的点,显然就是杨辉三角了
#include <iostream> #include <cstdio> #include <algorithm> #include <vector> #include <string> #include <queue> #include <functional> #include <map> #include <set> #include <cmath> #include <cstring> #include <deque> #include <stack> #include <ctime> #include <cstdlib> using namespace std; typedef long long ll; #define pii pair<int, int> const ll maxn = 2e5 + 10; const ll inf = 1e17 + 10; const ll mod = 1e9 + 7; ll fac[maxn], invfac[maxn]; ll qpow(ll x, ll n) { ll ans = 1; while(n) { if(n & 1) ans = ans * x % mod; n >>= 1; x = x * x % mod; } return ans % mod; } ll cal(ll up, ll down) { if(up == down || up == 0) return 1; ll ans = fac[down] * invfac[up] % mod; return ans * invfac[down - up] % mod; } int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int n, k; cin >> n >> k; fac[0] = 1; for(int i=1; i<=n; i++) fac[i] = fac[i - 1] * i % mod; invfac[n] = qpow(fac[n], mod - 2); for(int i=n-1; i>=0; i--) invfac[i] = invfac[i + 1] * (i + 1) % mod; ll ans = qpow(2, n); if(k < n) { ans = 0; for(int i=0; i<=k; i++) ans += cal(i, n); } cout << ans % mod << endl; return 0; }
这篇关于Codeforces Round #818 (Div. 2) D Madoka and The Corruption Scheme的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-15PingCAP 黄东旭参与 CCF 秀湖会议,共探开源教育未来
- 2024-05-13PingCAP 戴涛:构建面向未来的金融核心系统
- 2024-05-09flutter3.x_macos桌面os实战
- 2024-05-09Rust中的并发性:Sync 和 Send Traits
- 2024-05-08使用Ollama和OpenWebUI在CPU上玩转Meta Llama3-8B
- 2024-05-08完工标准(DoD)与验收条件(AC)究竟有什么不同?
- 2024-05-084万 star 的 NocoDB 在 sealos 上一键起,轻松把数据库编程智能表格
- 2024-05-08Mac 版Stable Diffusion WebUI的安装
- 2024-05-08解锁CodeGeeX智能问答中3项独有的隐藏技能
- 2024-05-08RAG算法优化+新增代码仓库支持,CodeGeeX的@repo功能效果提升