POJ 3252 Round Numbers：組合數學 + 數位 DP 計數二進制 0≥1 的數

題目大意

查詢區間 [S, E] 中，有多少整數的二進制表示中 **0 的個數 ≥ 1 的個數**。S, E < 2³¹。多測試案例。

核心思路：f(x) = [1, x] 中滿足條件的數個數

答案 = f(E) - f(S-1)。關鍵計算 f(x)。

組合數學直觀解法

• 二進制長度為 L 的數，最高位必為 1。剩餘 L-1 位中，0 的個數需 ≥ 1 的個數。設 1 的個數為 c，則 0 的個數 = L-1-c。條件：L-1-c ≥ c+1 (含最高位 1) ⇒ c ≤ (L-2)/2。即剩餘位中 1 的個數 ≤ floor((L-2)/2)。
• 對於長度 < L 的數，直接累加組合數 C(L-1, c) for c=0..floor((L-2)/2)。
• 對於長度 = L 且 ≤ x 的數，掃描 x 的二進制位（從高到低），遇到 1 時，嘗試將此位設為 0，剩餘位自由組合，累加合法組合數。

代碼框架

int C[35][35];
void initComb() {
    for (int i=0;i<=32;++i) { C[i][0]=1; for(int j=1;j<=i;++j) C[i][j]=C[i-1][j]+C[i-1][j-1]; }
}

int countValid(int x) {
    if (x <= 0) return 0;
    // 獲取二進制位存入 bits[], 高位在前
    // 1. 統計長度 < len 的合法數
    // 2. 掃描 bits，遇 1 時嘗試置 0，剩餘位組合
    // 3. 最後檢查 x 自身是否合法
    // 返回總數
}

數位 DP 替代方案

狀態：`dp[pos][diff][tight]`，`diff = count0 - count1`（可為負，偏移 +16）。轉移嘗試 0/1。最後 `diff ≥ 0` 計入。狀態數 32 × 33 × 2 ≈ 2000，極簡單。

總結

POJ 3252 既可用組合數學直接計算，也可用標準數位 DP。組合數學思路更直觀、常數更小；數位 DP 更通用、易擴展（如改條件為 0 > 1 等）。掌握兩種思維均有益。