题解 | 整数拆分

#include <stdio.h>

#define MOD 1000000000

int dp[1000001];  // 全局数组，避免栈溢出

int split_number(int n) {
    // 初始化dp数组
    for (int i = 0; i <= n; i++) {
        dp[i] = 0;
    }
    dp[0] = 1;

    // 用位运算生成2的幂次并更新dp
    int power = 1;
    while (power <= n) {
        for (int j = power; j <= n; j++) {
            dp[j] = (dp[j] + dp[j - power]) % MOD;
        }
        power <<= 1;  // 位运算代替乘法
    }

    return dp[n];
}

int main() {
    int n;
    scanf("%d", &n);
    if (n >= 1 && n <= 1000000) {
        printf("%d\n", split_number(n));
    }
    return 0;
}