题解 | #整数拆分#完全背包问题

#include <iostream>
using namespace std;

int dp[1000001];

int main() {
    int m;
    while (scanf("%d", &m) != EOF) { // 注意 while 处理多个 case
        dp[0] = 1;
        for (int i = 1, v = 1; v <= m; v *= 2) {
            for (int j = v; j <= m; j++) {
                dp[j] = (dp[j] + dp[j - v]) % 1000000000;
            }
        }
        printf("%d\n", dp[m]);
    }
}
// 64 位输出请用 printf("%lld")