题解 | 整数拆分

#include <iostream>
#include <cstdio>
using namespace std;

const int MAXN = 1000001;
const int MOD = 1000000000;
int dp[MAXN];

int main() {
    int n;
    scanf("%d", &n);

    // 初始化 dp 数组
    for (int i = 0; i <= n; i++) {
        dp[i] = 0;
    }
    dp[0] = 1; // 数字 0 的拆分方案数为 1

    // 遍历所有 2 的幂
    for (int pos = 0; (1ll << pos) <= n; pos++) {
        long long temp = 1ll << pos; // 计算 2^pos
        for (int j = temp; j <= n; j++) {
            dp[j] = (dp[j] + dp[j - temp]) % MOD;
        }
    }

    printf("%d\n", dp[n]);
    return 0;
}