题目地址：POJ 2229 题意：给定一个正整数，求有多少种方法把它写成若干个2幂次的和 思路：可以用递推，，对于一个整数n，分为奇数和偶数，我们应该分情况讨论。 1.如果为奇数，那么在这个表示中一定含有一个1，把这个1减去，就是n-1 即dp[n]=dp[n-1]。 2.如果为偶数，那么也分两种情况，有1和没1。对于有1的情况可以直接拆出两个1，然后变为n-2的情况。对于没有1的情况可以直接将其转化为n/2，因为n拆分出所有的数字都是2的倍数，只需要将每种拆分结果中的数字都除以2就会与n/2的一种拆分相对应。
;typedef __int64 LL;const int inf=0x3f3f3f3f;const double pi= acos(-1.0);const double esp=1e-6;;const int Maxn=1e6+10;const int mod=1000000000;int dp[Maxn];int main(){int n;dp[1]=1;dp[2]=2;for(int i=3;i<Maxn;i++){if(i&1)dp[i]=dp[i-1]%mod;elsedp[i]=(dp[i-2]+dp[i>>1])%mod;}while(~scanf(“%d”,&n)){printf(“%d\n”,dp[n]);}return 0;}
转动心中的期待，血在澎湃，吃苦流汗算什么。
