链接：
https://www.papamelon.com/problem/305
思路
这道题就是一个完全背包求方案数，物品是2的次幂，体积是n，求体积是n时有几种方案，其实很简单，可是我却突然想到一个问题就是为什么不可以先遍历体积再遍历2的次幂，我是非常不理解。
代码
/* 这题怎么都想不通的一点是为什么不能先遍历体积，再遍历2的次幂 */
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e6 + 10, mod = 1e9;int f[N] = {
0};
signed main()
{
int n;while (scanf("%lld", &n) != EOF){
memset(f, 0, sizeof f);f[0] = 1;for (int i = 1; i <= n; i *= 2){
for (int j = 1; j <= n; j ++ ){
if (j >= i){
f[j] = (f[j - i] + f[j]) % mod;}}}cout << f[n] << endl;}return 0;
}
总结
完全背包求方案数模板题