POJ 3252 Round Numbers：數位 DP 處理前導零統計二進制圓數

POJ 3252 Round Numbers：數位 DP 處理前導零統計二進制圓數

「圓數」定義：二進制表示中 0 的個數 ≥ 1 的個數。求 [x, y] 區間內圓數個數。

DP 狀態設計

dp[len][num0][num1]：處理到第 len 位（高位到低位），已確定部分 0 的個數 num0、1 的個數 num1 的合法方案數。

• 增加 first 標記：是否仍在前導零區間。前導零不計入 0/1 計數。
• 狀態轉移枚舉當前位 0/1，更新計數與 first。

遞歸函數

int dfs(int len, int first, int num0, int num1, int up) {
    if (len == 0) return (num0 >= num1);
    if (!up && !first && dp[len][num0][num1] != -1) return dp[len][num0][num1];
    int n = up ? dig[len] : 1; // 二進制位只能 0/1
    int res = 0;
    for (int i=0; i<=n; i++) {
        if (first) {
            if (i==0) res += dfs(len-1, 1, 0, 0, up&&i==n);
            else res += dfs(len-1, 0, num0, num1+1, up&&i==n);
        } else {
            if (i==0) res += dfs(len-1, 0, num0+1, num1, up&&i==n);
            else res += dfs(len-1, 0, num0, num1+1, up&&i==n);
        }
    }
    if (!up && !first) dp[len][num0][num1] = res;
    return res;
}

區間計算

cal(y) - cal(x-1)，cal 將數轉二進制存入 dig[]（高位在前）。

複雜度

• 狀態數：位數(≤31) × num0(≤31) × num1(≤31) × first(2) ≈ 6e4。
• 每查詢極快。

本題展示了數位 DP 中「前導零標記」處理技巧，將「不計入前導零」邏輯清晰編碼進狀態轉移，是二進制計數問題的標準模板。