HDU 3555 Bomb：數位 DP 統計「圓數」個數

問題描述

「圓數」定義：二進制表示中 0 的個數 ≥ 1 的個數。給定區間 [L, R] (1 ≤ L < R ≤ 2×10⁹)，求區間內圓數個數。

數位 DP 狀態設計

dfs(pos, first, len, sum, tight)

• pos：當前處理的二進制位（從高到低）
• first：是否已遇到第一個 1（前導零不計入長度）
• len：已確定的有效位長度
• sum：已確定部分中 0 的個數
• tight：是否受上界約束

轉移：枚舉當前位填 0 或 1，更新狀態。終止條件 pos == 0 時判斷 sum >= len - sum。

代碼實現

LL dfs(int pos, int first, int len, int sum, int flag) {
    if (pos == 0) return sum >= len - sum;
    if (!flag && dp[pos][first][len][sum] != -1) return dp[pos][first][len][sum];
    LL ans = 0;
    int ed = flag ? num[pos] : 1;
    for (int i = 0; i <= ed; ++i) {
        int nfirst = first, nlen = len, nsum = sum;
        if (!first && i) nfirst = 1;
        if (first && i == 0) ++nsum;
        if (nfirst) ++nlen;
        ans += dfs(pos - 1, nfirst, nlen, nsum, flag && i == ed);
    }
    if (!flag) dp[pos][first][len][sum] = ans;
    return ans;
}

LL solve(LL x) {
    int pos = 0;
    while (x) { num[++pos] = x % 2; x /= 2; }
    return dfs(pos, 0, 0, 0, 1) - pos + 1; // 減去 0
}

複雜度

狀態數：pos ≤ 31, first ∈ {0,1}, len ≤ 31, sum ≤ 31 → 約 6 萬狀態，每狀態 O(1) 轉移，極快。

關鍵技巧

• 前導零不計入長度與 0 計數，通過 first 標記區分。
• 最終答案需減去 0（題目要求正整數）。
• 記憶化數組 dp[32][2][32][32] 足夠。