HDU 4734 F(x)：數位 DP 計算加權數字和不超過閾值的個數

問題描述

定義十進制數 x = AₙAₙ₋₁...A₁ 的權值 F(x) = Aₙ·2ⁿ⁻¹ + Aₙ₋₁·2ⁿ⁻² + ... + A₁·2⁰。給定 A, B (<10⁹)，求 0 到 B 中有多少數 x 滿足 F(x) ≤ F(A)。T ≤ 10000。

核心觀察

• F(x) 最大值：9 位數全 9 → 9×(2⁹-1) = 4599 < 5500。狀態空間極小。
• 可預計算 dp[len][firstDigit][weight]：長度 len、最高位 firstDigit、權值和為 weight 的數字個數。
• 利用前綴和 sum[len][firstDigit][w] = Σ_{k≤w} dp[len][firstDigit][k] 快速查詢區間個數。

DP 預計算

dp[0][0][0] = 1;
for (len = 1; len <= 9; len++)
  for (first = 0; first <= 9; first++)
    for (w = 0; w <= 5000; w++)
      for (prev = 0; prev <= 9; prev++)
        if (w >= first * (1<<(len-1)))
          dp[len][first][w] += dp[len-1][prev][w - first*(1<<(len-1))];
// 構建前綴和 sum[len][first][w]

查詢函數 solve(A, B)

1. 計算 target = F(A)。
2. 從高位到低位遍歷 B 的每一位 digit：
3. 對當前位可能取值 0 ~ digit-1，累加 sum[len][d][target]。
4. 更新 target -= digit * (1<<(len-1))；若 target < 0 提前返回。
5. 所有位處理完後，ans++（B 本身若符合）。

完整代碼

#include 
#include 
#define MOD 1000000007

int dp[10][10][5500], sum[10][10][5500];
int fac[10] = {1,10,100,1000,10000,100000,1000000,10000000,100000000,1000000000};

int main() {
    // 預計算 dp 和 sum
    dp[0][0][0] = 1;
    for (int len = 1; len <= 9; len++) {
        for (int first = 0; first <= 9; first++) {
            for (int w = 0; w <= 5000; w++) {
                int t = 0;
                for (int prev = 0; prev <= 9; prev++) {
                    int need = w - first * (1 << (len-1));
                    if (need >= 0) t += dp[len-1][prev][need];
                }
                dp[len][first][w] = t;
                sum[len][first][w] = (w ? sum[len][first][w-1] : 0) + t;
            }
        }
    }

    int T; scanf("%d", &T);
    for (int cs = 1; cs <= T; cs++) {
        int A, B; scanf("%d%d", &A, &B);
        int target = 0;
        for (int i = 9; i >= 1; i--)
            target += ((A / fac[i-1]) % 10) * (1 << (i-1));
        int ans = 0;
        for (int i = 9; i >= 1; i--) {
            int d = (B / fac[i-1]) % 10;
            for (int dig = 0; dig < d; dig++)
                ans += sum[i][dig][target];
            target -= d * (1 << (i-1));
            if (target < 0) break;
        }
        if (target >= 0) ans++;
        printf("Case #%d: %d\n", cs, ans);
    }
    return 0;
}

複雜度分析

• 預計算：O(9 × 10 × 5000 × 10) ≈ 4.5e6，啟動時一次完成。
• 每查詢：O(9 × 10) = O(1)，T=10000 總時間極短。
• 空間：O(10 × 10 × 5500) ≈ 55 萬整數 ≈ 2.2 MB。

關鍵技巧總結

1. 權值上界小（<5500）使數位 DP 狀態可行。
2. 前綴和優化區間查詢，將內層循環從 O(W) 降為 O(1)。
3. 高位到低位數位 DP 標準模板，配合預計算應對多測試用例。