【AGC009E】Eternal Average
2021/4/23 18:57:07
本文主要是介绍【AGC009E】Eternal Average,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
题目
题目链接:https://atcoder.jp/contests/agc009/tasks/agc009_e
黑板上有 \(n\) 个 \(0\) 和 \(m\) 个 \(1\),我们每次选择 \(k\) 个数字将其擦除,然后把它们的平均数写上去,这样一直操作直到只剩下一个数字,问剩下的这个数字有多少种不同的情况。
答案对 \(10^9+7\) 取模。
\(1 \leq n,m \leq 2000,2 \leq k \leq 2000\)。保证 \(n+m-1\) 能被 \(k-1\) 整除。
思路
考虑这样一个过程:一开始有 \(n\) 个点权为 \(0\) 的点,\(m\) 个点权为 \(1\) 的点,然后每次操作选择任意 \(k\) 没有父亲的点,把他们的父亲设为一个全新的点,这个新点的权值为所选 \(k\) 个点的平均值。最后我们需要求根节点的权值的可能数量。
显然这个过程构成了一棵树,我们设第 \(i\) 个点权为 \(1\) 的点的深度为 \(a_i\),第 \(i\) 个点权为 \(0\) 的点的深度为 \(b_i\)(根节点深度为 \(0\)),那么我们需要求
有多少种可能。限制条件为
\[\sum_{m}^{i=1}k^{-a_i}+\sum_{n}^{i=1}k^{-b_i}=1 \]这个条件可以理解为把根节点看作 \(1\),然后每一个节点的权值为其父亲的 \(\frac{1}{k}\),这样所有的叶子(也就是 \(n+m\) 个初始的点)的权值和等于 \(1\)。不难发现这个限制条件是充要的。
这个限制条件等价于 \(1-s=\sum_{n}^{i=1}k^{-b_i}\)。
将 \(s\) 看作一个 \(k\) 进制数,其小数点后第 \(i\) 位为 \(s_i\),手玩一下进位的过程,一定有
\(1-s=\sum_{n}^{i=1}k^{-b_i}\) 同理可以得到
\[len(k-1)-\sum_{i}s_i+1\equiv n\pmod {k-1} \]并且 \(s\) 每一位之和不能超过 \(m\),\(1-s\) 每一位之和不能超过 \(n\)。
考虑原题,小数点后最多只有 \(\frac{n+m-1}{k-1}\leq n+m\) 位,那么可以设 \(f[i][j][0/1]\) 表示现在考虑到第 \(i\) 位,前 \(i\) 位和为 \(j\),第 \(i\) 位为 \(0\) / 非 \(0\) 的方案数。
显然
前缀和优化一下即可做到 \(O(m(n+m))\)。
代码
#include <bits/stdc++.h> using namespace std; const int N=2010,MOD=1e9+7; int n,m,k,ans,f[N*2][N][2],g[N]; int main() { scanf("%d%d%d",&n,&m,&k); f[0][0][0]=1; for (int i=1;i<=n+m;i++) { g[0]=(f[i-1][0][0]+f[i-1][0][1])%MOD; for (int j=0;j<=m;j++) { if (j) g[j]=((g[j-1]+f[i-1][j][0])%MOD+f[i-1][j][1])%MOD; f[i][j][0]=(f[i-1][j][0]+f[i-1][j][1])%MOD; if (j>=k) f[i][j][1]=(g[j-1]-g[j-k])%MOD; if (j && j<k) f[i][j][1]=g[j-1]; if (j%(k-1)==m%(k-1) && (i*(k-1)-j+1)%(k-1)==n%(k-1) && i*(k-1)-j+1<=n) ans=(ans+f[i][j][1])%MOD; } } printf("%d",(ans%MOD+MOD)%MOD); return 0; }
这篇关于【AGC009E】Eternal Average的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 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功能效果提升