给出一个 ，使用一些 的若干次幂的数相加来求之。问有多少种方法。
链接
题解
背包问题，以 作为物品，求出装满背包的方案数即为答案。
时间复杂度 ，空间 ，需要滚动数组。
代码
#include <cstdio>
#include <algorithm>
const int MAXN = 1e6;
const int MAXN_LOG = 20; // Math.log2(1e6) = 19.931568569324174
const int MOD = 1e9;
int main()
{
int n;
scanf("%d", &n);
/*
// 注释里都是泪啊 qnqqqqqqqqq
static int f[MAXN + 1][MAXN_LOG + 1];
for (int i = 0; i <= MAXN_LOG; i++) f[0][i] = 1;
for (int i = 1; i <= n; i++)
{
for (int j = 0; j <= MAXN_LOG; j++)
{
if (j != 0) f[i][j] = f[i][j - 1];
if (i >= (1 << j)) (f[i][j] += f[i - (1 << j)][j]) %= MOD;
// / *
for (int k = 0; k <= j && (1 << k) <= i; k++)
{
// printf(" f(%d, %d) <-- f(%d, %d)\n", i, j, i - (1 << k), k);
(f[i][j] += f[i - (1 << k)][k]) %= MOD;
}
// printf("f(%d, %d) = %d\n", i, j, f[i][j]);
// * /
}
}
*/
static int f[MAXN + 1];
f[0] = 1;
for (int i = 0; (1 << i) <= n; i++)
{
for (int j = 1; j <= n; j++)
{
if (j - (1 << i) >= 0) (f[j] += f[j - (1 << i)]) %= MOD;
}
}
printf("%d\n", f[n]);
}