papamelon 305. 求和方案 Sumsets

https://www.papamelon.com/problem/305

给你一个数N,只能用2的幂次求和组成,问总共有多少种方案.

输入
包含多组测试数据,输入以EOF作为结束标志.
每组测试数据包含一个整数NN.
1≤N≤1,000,000
输出
输出一个整数. 由于结果可能会非常大,因此输出末尾的九位数.
样例 1
输入
7
输出
6

例子说明
7 =
1+1+1+1+1+1+1
1+1+1+1+1+2
1+1+1+2+2
1+2+2+2
1+2+4
1+1+1+4

一种方法是观察找规律
所有的n都有可以由上一个数的所有组合方案+1得到自己的一种组合方案
假设dp[x]表示x的2次幂数的组合方案数
那么dp[x]一部分可以由dp[x-1]转化而来
当x为偶数的时候 x的2次幂组合可以从 x/2的2次幂组合所有元素乘以2转化，而且和dp[x-1]的方案不重合
综上所述
当x为偶数的时候 dp[x] = dp[x/2]+dp[x-1]
当x为奇数的时候 dp[x]=dp[x-1]

#include <iostream>

using  namespace std;

const int N = 1000010;
long long dp[N];
int n;

void solve() {
	dp[0] = 0; dp[1] = 1; dp[2] = 2; dp[3] = 2; dp[4] = 4;

	for (int i = 5; i <= n; i++) {
		if (i % 2 == 0) {
			dp[i] = dp[i - 1] + dp[i / 2];
		}
		else {
			dp[i] = dp[i - 1];
		}
		dp[i] = dp[i] % 1000000000;
	}

	cout << dp[n] << endl;

}

int main()
{
	cin >> n;

	solve();

	return 0;
}

另一种解法从背包的角度来看待
dp[x][y]表示在可选取(2^0,21,...z^x)的多个元素下 组合成y的方案数
那么可得dp[x][y] = dp[x-1][y-2^{x]+dp[x-1][y-2*2}x]+...+dp[x-1][y-z*2^x]
还可以优化成1维数组，代码如下

#include <iostream>

using  namespace std;

const int N = 1000010;
long long dp[N];
int n;
const int MOD = 1000000000;

int main() {
	cin >> n;
	dp[0] = 1;

	for (int i = 1; i <= n; i <<= 1) {
		for (int j = 1; j <= n; j++) {
			if (j >= i) {
				dp[j] += dp[j - i];
				dp[j] %= MOD;
			}
		}
	}

	cout << dp[n] << endl;

	return 0;
}

我的视频题解空间