Description
Input
Output
Sample Input
7
Sample Output
6
本题借鉴了一片博客，博主写的挺好的
题目大意：给定一个数用2的幂次方数，求可以有多少表达方式。
题解：动态规划和递推，如果i为偶数，dp[i]=dp[i/2]+dp[i-2]
偶数的时候分有一和没有一进行考虑，
有一的话就肯定有两个一，那么dp[i]=dp[i-2];
没有一的话，就是都除以2 dp[i]=dp[i/2];
i为奇数,肯定有一个一 dp[i]=dp[i-1];
代码：
#include<iostream> #include<cstring> using namespace std; const int M=1000000000; const int MAXN=1000010; int dp[MAXN]; int main() { int n; while(scanf("%d",&n)!=EOF) { dp[0]=dp[1]=1; for(int i=2;i<=n;i++) { if(i & 0x01) dp[i]=dp[i-1]; else dp[i]=(dp[i-2]+dp[i>>1])%M; } printf("%d\n",dp[n]); } return 0; }
原文：https://www.cnblogs.com/acmblog/p/9575836.html