传送门

分析

我们不难将条件转换为前缀和的形式,即

pre[i]>=pre[i-1]*2,pre[i]>0,pre[k]=n。

所以我们用dp[i][j]表示考虑到第i个数且pre[i]=j的情况下的方案数。我们发现一一转移的复杂度并不行,于是我们考虑只让dp[i-1][j]转移到dp[i][j*2],然后在利用前缀和的思想将dp[i][j]转移到dp[i][j+1],这样可以将复杂度优化到O(nk),然后使用滚动数组就可以了。

代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<cctype>
#include<cmath>
#include<cstdlib>
#include<queue>
#include<ctime>
#include<vector>
#include<set>
#include<map>
#include<stack>
using namespace std;
const int mod = ;
int n,k,dp[][];
int main(){
int i,j,now=;
scanf("%d%d",&n,&k);
for(i=;i<=n;i++)dp[now][i]=;
for(i=;i<=k;i++){
now^=;
memset(dp[now],,sizeof(dp[now]));
for(j=;j*<=n;j++)
dp[now][j*]=(dp[now][j*]+dp[now^][j])%mod;
for(j=;j<=n;j++)
dp[now][j]=(dp[now][j]+dp[now][j-])%mod;
}
printf("%d\n",dp[now][n]);
return ;
}

最新文章

  1. DNS的查询流程
  2. 水晶报表13.x(Crystal Reports for VS2010)的安装部署经验
  3. c++ vector struct 使用
  4. 第十四篇:在SOUI中使用定时器
  5. Django1.9开发博客(11)- 富文本与代码高亮
  6. c语言求平面上2个坐标点的直线距离、求俩坐标直线距离作为半径的圆的面积、递归、菲波那次数列、explode
  7. Markdown 语法说明 (简体中文版)
  8. iPhone 如何设置彩信 ?
  9. 如何关闭android studio开发环境自动保存
  10. 更新Appium中的WebDriverAgent
  11. 初探机器学习之使用百度EasyDL定制化模型
  12. logstash 切分tomcat日志
  13. 浅谈Final
  14. Django中使用bookstarp框架(4)
  15. 【吴恩达课后测验】Course 1 - 神经网络和深度学习 - 第二周测验【中英】
  16. vue-resource获取不了数据,和ajax的区别,及vue-resource用法
  17. Oracle数据库的基本查询
  18. [Python爬虫]煎蛋网OOXX妹子图爬虫(1)——解密图片地址
  19. idea maven 依赖问题
  20. boost::interprocess(1)

热门文章

  1. MonoBehavior lifecycle
  2. git 远程库 创建私钥
  3. UVA - 11922 Permutation Transformer (splay)
  4. 九、python沉淀之路--递归、全局变量、局部变量、作用域
  5. Node中没搞明白require和import,你会被坑的很惨
  6. andriod&amp;linux&amp;c函数原型
  7. 6、Selenium+Python登录案例 -- Github
  8. WPF中ToolTip的自定义
  9. Drools学习笔记3—Conditions / LHS—字段约束连接&amp;字段约束操作符
  10. js笔试题一套(未完待续)