POJ-2229
2024-08-28 13:28:43
Sumsets
Time Limit: 2000MS Memory Limit: 200000K Total Submissions: 19599 Accepted: 7651 Description
Farmer John commanded his cows to search for different sets of numbers that sum to a given number. The cows use only numbers that are an integer power of 2. Here are the possible sets of numbers that sum to 7:1) 1+1+1+1+1+1+1
2) 1+1+1+1+1+2
3) 1+1+1+2+2
4) 1+1+1+4
5) 1+2+2+2
6) 1+2+4Help FJ count all possible representations for a given integer N (1 <= N <= 1,000,000).
Input
A single line with a single integer, N.Output
The number of ways to represent N as the indicated sum. Due to the potential huge size of this number, print only last 9 digits (in base 10 representation).Sample Input
7Sample Output
6
题意:
给出一个整数n,求n有多少种由2的幂次之和组成的方案.
当n为奇数的时候,那么所求的和式中必有1,则dp[n]==dp[n-1];
当n为偶数的时候,可以分两种情况:
1.含有1,个数==dp[n-1];
2.不含有1,这时每个分解因子都是偶数,将所有分解因子都除以二,所得的结果刚好是n/2的分解结果,并且一一对应,则个数为dp[n/2];
AC代码:
//#include<bits/stdc++.h>
#include<iostream>
#include<cstring>
using namespace std; const long long MOD=; int dp[]; int main(){
ios::sync_with_stdio(false);
int n;
while(cin>>n&&n){
memset(dp,,sizeof(dp));
dp[]=;
for(int i=;i<=n;i++){
if(i&){
dp[i]=dp[i-];
}
else{
dp[i]=(dp[i-]+dp[i>>])%MOD;
}
}
cout<<dp[n]<<endl;
}
return ;
}
最新文章
- SuperMap iClient for JavaScript 新手入门
- Python爬虫利器三之Xpath语法与lxml库的用法
- html input file标签的上传文件 注意点
- 应用上下文配置【AppConfig】
- Mysql设置字符编码及varchar宽度问题
- linux c 实现大数相乘
- Linux中的MyEclipse配置Hadoop
- [置顶] MySQL Cluster初步学习资料整理--安装部署新特性性能测试等
- sql语法:inner join on, left join on, right join on具体用法
- Android 70道面试题汇总
- 绝美Sysinternals
- 内核必看: spinlock、 mutex 以及 semaphore
- oracle中intersect的用法
- SPI模式下MCU对SD卡的控制及操作命令(转)
- ToolBar控件详解
- js的观察者模式
- 第六周助教工作总结——NWNU李泓毅
- ui2code中的深度学习+传统算法应用
- AAC ADTS格式分析
- 【java】注释
热门文章
- IntelliJ IDEA打可执行jar包
- SQL中的四种连接方式
- 在java项目中使用protobuf
- 时间写入文件名 nohup 原理 Command In Background your shell may have its own version of nohup
- POJ - 2031 Building a Space Station 【PRIME】
- Java类的加载与生命周期
- 微信公众号支付 redirect_uri 参数错误
- tensorflow学习官网地址
- zabbix性能优化等
- BZOJ 1600 [Usaco2008 Oct]建造栅栏:dp【前缀和优化】