BZOJ 1677 求和

题目链接

设\(f[i]\)表示凑成\(i\)的方案数。
枚举所有\(f[i-2^k]\)加上是错误的，因为有些方案可能会重复。

比如现在要凑\(7\)
有可能从\(5=1+2+2\)或者\(6=2+2+2\)转移过来。
显然是重复了。

正确的姿势是做完全背包，也就是交换一下枚举顺序...
把\(2^k\)当作物品凑\(i\)

#include <bits/stdc++.h>
using namespace std;

const int N = 1e6 + 5, MOD = 1e9;
int n, f[N];

int main() {
    scanf("%d", &n);
	f[0] = 1;
	/*for (int i = 1; i <= n; i++) {
		for (int j = 0; (1 << j) <= i; j++) {
			f[i] = (f[i] * 1ll + f[i - (1 << j)] * 1ll) % MOD;
		}
	}*/
	for (int j = 0; (1 << j) <= n; j++) {
		for (int i = 1; i <= n; i++) {
			if(i >= (1 << j)) f[i] = (f[i] * 1ll + f[i - (1 << j)] * 1ll) % MOD;
		}
	}
	printf("%d\n", f[n]);
	return 0;
}