AtCoder Grand Contest 009 E:Eternal Average
2024-08-26 17:11:54
题目传送门:https://agc009.contest.atcoder.jp/tasks/agc009_e
题目翻译
纸上写了\(N\)个\(1\)和\(M\)个\(0\),你每次可以选择\(k\)个数字擦掉,然后再写一个他们的平均值上去。保证\(N+M-1\)可以整除\(k-1\),请问最后留下来的那个数有多少种。\(N,M,K\leqslant 2000\)
题解
这题可以转化一下题意:有一棵\(k\)叉树,有\(n+m\)个叶子,每个叶子的权值是\(0\)或\(1\),其他结点的权值是子结点权值的平均值。问根节点的权值有多少种情况。
假设权值为\(0\)的叶子的深度分别为\(x_i\),权值为\(1\)的叶子的深度分别为\(y_i\)。
显然:\(\sum k^{-x_i}+\sum k^{-y_i}=1\)
所以对于所有的有理数\(s\),根的权值可能等于他必然满足:
\(s=\sum k^{-y_i}\)
\(1-s=\sum k^{-x_i}\)
把\(s\)写成\(k\)进制\(0.s_1s_2s_3...s_{len}\),如果\(s\)可以被\(N\)个\(k^{-1}\)的幂的和表示,那么一定满足:
\(\sum\limits_{i=1}^{len}s_i\leqslant N\)且\(\sum\limits_{i=1}^{len}s_i\equiv N(\bmod k-1)\)
我们还可以把\(k^{-a}\)拆成\(k\)个\(k^{-a-1}\)来凑出恰好\(N\)。
然后我们就可以\(N^2dp\)求\(s\)的方案数了。
时间复杂度:\(O(nm)\)
空间复杂度:\(O(nm)\)
代码如下:
#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn=2e3+5,pps=1e9+7;
int n,m,k,ans,len;
int f[maxn<<1][maxn];
int read() {
int x=0,f=1;char ch=getchar();
for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=-1;
for(;ch>='0'&&ch<='9';ch=getchar())x=x*10+ch-'0';
return x*f;
}
int main() {
n=read(),m=read(),k=read();
len=(n+m-1)/(k-1);
for(int i=1;i<k;i++)
f[1][i]=1;
for(int i=2;i<=len;i++)
for(int j=1;j<=n;j++) {
f[i][j]=(f[i-1][j]+f[i][j-1])%pps;
if(j>=k)f[i][j]=(f[i][j]+pps-f[i-1][j-k])%pps;
}
for(int i=1;i<=len;i++) {
int limit=max(0,i*(k-1)-m)+1;
for(int j=n;j>=limit;j-=k-1)
ans=(ans+f[i][j])%pps;
}
printf("%d\n",ans);
return 0;
}
最新文章
- mysq l错误Table ‘./mysql/proc’ is marked as crashed and should be repaired
- shell 计算2
- 关于CefSharp的坎坷之路
- SQL Server 参数化 PARAMETERIZATION
- Ubuntu进不去,显示error:unknown filesystem (最简单解决方案总结)
- win7(32/64)+apache2.4+php5.5+mysql5.6 环境搭建配置
- procps包里面的sysctl命令
- UITableView详解(转)
- html5 canvas画布尺寸与显示尺寸
- java8 按条件过滤集合
- 怎么给PDF文件交换页面
- hosts文件被修改后的惨案
- win10电脑怎么录制视频 电脑录制视频软件
- 【UML】NO.70.EBook.9.UML.4.001-【PowerDesigner 16 从入门到精通】- 基础概念
- centos 7 安装 php 5.5 5.6 7.0
- python如何进行内存管理的
- Git冲突与解决方法
- online learning,batch learning&批量梯度下降,随机梯度下降
- linux中的vim编辑器的使用
- C++11中decltype的使用