大专学历怎么自考/seo公司上海牛巨微

描述

农夫约翰命令他的母牛搜索不同数量的数字，总和到一个给定的数字。母牛只使用整数幂为2的数字。这是可能的数字组合，总和为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 

帮助FJ计算给定整数N的所有可能表示（1 <= N <= 1,000,000）。

 

当 n 是奇数，其方法数与 n-1 一样。 n 是偶数，则 n-1 的方法数加上 n/2 的方法数。（相比于 n-1 多出来的方法，就是把 n 拆成 （n/2）个 2，然后这些 2 合并的方法数。（n/2）个 2 与 （n/2）个 1 的方法数是一样多的）。

代码：

#include <iostream>
#include <cstring>
using namespace std;const int MAX = 1000001;
const int mod = 1000000000;long long dp[MAX];int main(){memset(dp, 0, sizeof(dp));dp[1] = 1;for(int i=2; i<MAX; i++){if(i & 1){dp[i] = dp[i-1];}else{dp[i] += (dp[i/2] % mod + dp[i-1] % mod) % mod;}}int n;while(cin >> n){cout << dp[n] << endl;}
}