本題要求計算正整數 N (1 ≤ N ≤ 1,000,000) 表示為 2 的冪次數之和的方法數，僅輸出最後 9 位數字。這是經典的整數分割變體問題，展示動態規劃狀態轉移設計與空間優化技巧。
令 a[n] 表示整數 n 的合法分割數。加數限制為 2^k (k≥0)。觀察奇偶性規律：
n-1 為偶數，分割數等於 a[n-1]n-2 的分割數 a[n-2]n/2 的分割數 a[n/2]遞推公式：
a[1] = 1; a[2] = 2;
for n = 3 to N:
if n % 2 == 1: a[n] = a[n-1]
else: a[n] = (a[n-2] + a[n/2]) % 1000000000
#include <stdio.h>
#include <stdint.h>
#define MOD 1000000000
#define MAXN 1000000
int64_t dp[MAXN + 1];
int main() {
dp[1] = 1;
dp[2] = 2;
for (int i = 3; i <= MAXN; i++) {
if (i & 1) dp[i] = dp[i-1];
else dp[i] = (dp[i-2] + dp[i/2]) % MOD;
}
int64_t n;
while (scanf("%lld", &n) == 1) {
printf("%lld\n", dp[n]);
}
return 0;
}
複雜度：預計算 O(MAXN)，查詢 O(1)。適用於多測試案例場景。
視為硬幣找零問題：硬幣面值為 1, 2, 4, 8, ..., 2^24 (2^24 > 10^6)，每種無限供應，求組合數 (順序不計)。
#include <stdio.h>
#include <string.h>
#include <stdint.h>
#define MOD 1000000000
#define MAXN 1000000
int64_t dp[MAXN + 1];
int coins[25];
int main() {
// 初始化 2 的冪次硬幣
coins[0] = 1;
for (int i = 1; i < 25; i++) coins[i] = coins[i-1] << 1;
int n;
while (scanf("%d", &n) == 1) {
memset(dp, 0, sizeof(dp));
dp[0] = 1; // 和為 0 有 1 種方法 (不選任何硬幣)
for (int i = 0; i < 25 && coins[i] <= n; i++) {
for (int j = coins[i]; j <= n; j++) {
dp[j] = (dp[j] + dp[j - coins[i]]) % MOD;
}
}
printf("%lld\n", dp[n]);
}
return 0;
}
狀態轉移：dp[j] += dp[j - coin] 代表「使用當前硬幣」的方案數累加。外層遍歷硬幣、內層遍歷金額確保組合不重複計數。
| 維度 | 解法一 (遞推) | 解法二 (背包) |
|---|---|---|
| 時間複雜度 | O(N) 預計算 | O(N log N) 每查詢 |
| 空間複雜度 | O(N) | O(N) |
| 多查詢優勢 | 極大 (預計算一次) | 需重複計算 |
| 數學洞察 | 需推導奇偶規律 | 通用背包模型 |
| 擴充性 | 難以推廣 | 易修改硬幣集合 |
int64_t / long long 防止中間結果溢位while (scanf(...) == 1) 處理多測試案例至 EOFdp[0] = 1 為背包 DP 正確性關鍵∏_{k≥0} 1/(1-x^{2^k}) 的係數即為答案本題展示從數學規律推導優化遞推與通用背包模型兩種思維路徑。實戰中根據題目約束 (單查詢/多查詢、N 範圍、時間限制) 靈活選擇策略，是演算法競賽與工程優化的核心能力。
