poj2229
题意：给定一个数，把它拆分成2的n次幂相加的形式，问有多少种方法，结果取后9位
分析：这道题目很有意思，可以把一个数i分成奇数和偶数的情况来讨论，当i是奇数时，i拆分以后的个数与i-1是一样的，而当i是偶数时，相当于将i-1加上一个1以后同时可以把两个1为一组进行合并，故为i-1与i/2的和
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <string> 5 #include <vector> 6 #include <algorithm> 7 #include <set> 8 #include <map> 9 #include <bitset> 10 #include <cmath> 11 #include <queue> 12 #include <stack> 13 using namespace std; 14 const int mod=1000000000; 15 const int maxn=1001000; 16 int dp[maxn]; 17 int n; 18 int main() 19 { 20 while(cin>>n) 21 { 22 memset(dp,0,sizeof(dp)); 23 dp[1]=1; 24 dp[2]=2; 25 for(int i=3;i<=n;i++) 26 { 27 if(i%2) 28 dp[i]=dp[i-1]%mod; 29 else 30 dp[i]=(dp[i-1]+dp[i/2])%mod; 31 } 32 cout<<dp[n]<<endl; 33 } 34 return 0; 35 return 0; 36 }
原文：http://www.cnblogs.com/wolf940509/p/5349448.html
