HDU 4734 F(x)：數位 DP 求權重不超過 F(A) 的數字個數

問題描述

定義十進制數 x（n 位）的權重 F(x) = Σ A_i * 2^{n-i}（即把十進制數字當二進制權重求和）。給 A, B (0 ≤ A,B < 10^9)，求 [0, B] 中有多少數 x 滿足 F(x) ≤ F(A)。T ≤ 10000 組測試。

核心觀察

F(x) 只依賴 x 的十進制數字序列。對於固定長度 n，F(x) 最大值為 9 * (2^n - 1)。
B < 10^9 → 最多 10 位。F(A) 最大約 9 * 1023 = 9207。
DP 狀態：dp[pos][sum] 表示處理到第 pos 位（從低到高），當前累積權重為 sum 的合法方案數。

狀態定義

• dfs(pos, sum, limit)：正在填第 pos 位（高位→低位），剩餘可用權重預算 sum，limit 表示前綴是否已達上界 B 的對應位。
• 返回值：填完剩餘位、且總權重 ≤ 原預算的方案數。
• 轉移：枚舉當前位 d = 0..up（up = limit ? digit[pos] : 9），新預算 sum - d * 2^{pos-1}，若 < 0 剪枝。
• 記憶化：!limit 時存 dp[pos][sum]。

代碼實現

#include <bits/stdc++.h>
using namespace std;
using LL = long long;

const int MAXP = 20;
const int MAXS = 20000;
LL dp[MAXP][MAXS];
int digit[MAXP];
LL limit_sum;

LL dfs(int pos, int sum, bool limit) {
    if (pos == 0) return sum >= 0;
    if (sum < 0) return 0;
    if (!limit && dp[pos][sum] != -1) return dp[pos][sum];
    LL ans = 0;
    int up = limit ? digit[pos] : 9;
    for (int d = 0; d <= up; ++d) {
        int cost = d * (1 << (pos - 1));
        ans += dfs(pos - 1, sum - cost, limit && d == up);
    }
    if (!limit) dp[pos][sum] = ans;
    return ans;
}

LL solve(LL x) {  // 計算 [0, x] 中 F(num) ≤ limit_sum 的個數
    int pos = 0;
    while (x) { digit[++pos] = x % 10; x /= 10; }
    return dfs(pos, limit_sum, true);
}

LL weight(LL x) {  // 計算 F(x)
    LL ans = 0, p = 1;
    while (x) { ans += (x % 10) * p; x /= 10; p <<= 1; }
    return ans;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T; cin >> T;
    for (int cas = 1; cas <= T; ++cas) {
        LL A, B; cin >> A >> B;
        limit_sum = weight(A);
        memset(dp, -1, sizeof(dp));
        LL ans = solve(B);
        cout << "Case #" << cas << ": " << ans << '\n';
    }
    return 0;
}

複雜度分析

• 狀態數：pos ≤ 10，sum ≤ 9207 → 約 9 萬狀態。
• 每狀態轉移 10 次 → 約 10⁶ 操作/測試用例。
• T ≤ 10000 但 limit_sum 隨 A 變化，DP 表需重置。實際運行極快（數位 DP 常數小）。

關鍵優化

1. sum < 0 直接返回 0（剪枝）。
2. !limit 時記憶化，避免重複計算。
3. 預計算 1 << (pos-1) 或用移位。