本文共 968 字，大约阅读时间需要 3 分钟。

题意

给定一个数字，问用2的次方数凑，一共有几种情况

AC

• 完全背包

int dp[N];  //long long超时。。。int mod = 1e9;int main(){#ifndef ONLINE_JUDGE    freopen("in.txt", "r", stdin);#endif    int n;    cin >> n;    int a[22];    for (int i = 0; i < 22; i++) {        a[i] = 1 << i;    }    dp[0] = 1;    for (int i = 0; i < 22; i++) {        if (a[i] > n)   break;        for (int j = a[i]; j <= n; ++j) {            dp[j] += dp[j - a[i]];            dp[j] %= mod;        }    }    cout << dp[n] << endl;    return 0;}

• 规律
  

using namespace std;int dp[N];int mod = 1e9;int main(){#ifndef ONLINE_JUDGE    // freopen("in.txt", "r", stdin);#endif    int n;    cin >> n;    dp[1] = 1;    dp[2] = dp[3] = 2;    for (int i = 4; i <= 1000000; ++i) {        if (i > n)  break;        if (i % 2) dp[i] = dp[i - 1] % mod;        else    dp[i] = (dp[i - 2] % mod + dp[i / 2] % mod) % mod;    }    cout << dp[n] << endl;    return 0;}