题目链接

Sumsets POJ - 2229

思路

$$ 转化为完全背包问题，物品为2^j,转移方程为 \\\\dp[0] = 1 \\\\dp[i] += \sum_{j = 0}^{20}dp[i - 2^j] $$

时间复杂度

$$ O(Nlog(N)) $$

代码

#include <cstdio>

using namespace std;

const int MAXN = 1e6 + 10;
const int MOD = 1e9;

int dp[MAXN];

int main() {
    int n;
    scanf("%d", &n);// don't forget &
    int cur = 1;
    dp[0] = 1;
    for (int i = 0; i < 20; i++) {
        for (int j = 1; j <= n; j++) {
            if (j - cur >= 0) {
                dp[j] += dp[j - cur];
                if (dp[j] >= MOD) {
                    dp[j] -= MOD;
                }
            }
        }
        cur *= 2;
    }
    printf("%d", dp[n]);
    return 0;
}