AcWing
3382. 整数拆分
完全背包问题。定义二维状态数组f[i][j]表示取前i种物品，背包容量为j时，恰好能装满背包的所有方案的总数量。
可以将f[i][j]分为以下若干个集合：
- 背包装
0个物品i，恰好装满容量为j的背包； - 背包装
1个物品i，恰好装满容量为j的背包； - ……
- 背包装
k个物品i，恰好装满容量为j的背包； - ……
保证将f[i][j]分为这些集合之后不重不漏。则对于普遍的f[i][j]，有:
f[i][j] = f[i-1][j] + f[i-1][j-v[i]] + f[i-1][j-2v[i]] + ...
同时注意到：
f[i][j-v[i]] = f[i-1][j-v[i]] + f[i-1][j-2v[i]] + ...
所以：
f[i][j] = f[i-1][j] + f[i][j-v[i]]
考虑边界条件，f[0][0] = 1, f[0][1] = 0, f[0][2] = 0, ...，即当不取任何一个物品，使容量恰好为0，此时算一种方案。
考虑优化空间，使用一维数组，外层循环依次枚举物品种类，内层循环必须从小到大枚举背包容量，这样f[j]取得的是上一种物品时的值，f[j-v[i]]取得的是本种物品时的值。
在执行状态转移时，顺手取个模，以满足题目要求。
#include <bits/stdc++.h>
using namespace std;
const int M = 1e6 + 10, MOD = 1e9;
int m, f[M];
int main(){
cin >> m;
f[0] = 1;
for(int v = 1; v <= m; v *= 2)
for(int j = v; j <= m; j++)
f[j] = (f[j] + f[j - v]) % MOD;
cout << f[m] << endl;
return 0;
}