1677: [Usaco2005 Jan]Sumsets 求和
Time Limit: 5 Sec Memory Limit: 64 MB
Submit: 610 Solved: 338
[Submit][Status]
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+4 Help FJ count all possible representations for a given integer N (1 <= N <= 1,000,000).
给出一个N(1≤N≤10^6),使用一些2的若干次幂的数相加来求之.问有多少种方法
Input
一个整数N.
Output
方法数.这个数可能很大,请输出其在十进制下的最后9位.
Sample Input
7
Sample Output
6
有以下六种方式
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+4
有以下六种方式
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+4
//#define _TEST _TEST #include <cstdio> #include <cstring> #include <cstdlib> #include <iostream> #include <cmath> #include <algorithm> using namespace std; /************************************************ Code By willinglive ************************************************/ ///////////////////////////////////////////////// #define rep(i,l,r) for(int i=l,___t=(r);i<=___t;i++) #define per(i,r,l) for(int i=r,___t=(l);i>=___t;i--) #define MS(arr,x) memset(arr,x,sizeof(arr)) #define LL long long #define INE(i,u,e) for(int i=head[u];~i;i=e[i].next) ///////////////////////////////////////////////// int n; int dp[1000001]; namespace { ////////////////////////////////// } ////////////////////////////////// ///////////////////////////////////////////////// ///////////////////////////////////////////////// void input() { scanf("%d",&n); } void solve() { ///////////////////init/////////////////// dp[1]=1; ////////////////calculate//////////////// rep(i,2,n) { dp[i]=dp[i-1]; if(!(i&1))dp[i]+=dp[i>>1]; dp[i]%=1000000000; } /////////////////output///////////////// printf("%d\n",dp[n]); } ///////////////////////////////////////////////// int main() { #ifndef _TEST freopen("std.in","r",stdin); freopen("std.out","w",stdout); #endif input(); solve(); #ifdef _TEST for(;;); #endif return 0; }