POJ 3252 Round Numbers：數位 DP 入門詳解

題目大意

給定區間 [L, R]，求區間內「合法數」的個數。合法數定義：其二進制表示中 0 的個數 ≥ 1 的個數（二進制無前導 0）。

核心思路：數位 DP + 組合數學

預處理組合數與前綴和

• C[i][j]：組合數 C(i, j)。
• cnt[i]：二進制長度恰為 i 位（最高位為 1）的合法數個數。枚舉剩餘 i-1 位中 0 的個數 j，若 j ≥ i-j 則合法，累加 C[i-1][j]。
• sum[i]：二進制長度 ≤ i 位的合法數個數，sum[i] = sum[i-1] + cnt[i]。

DFS 遞歸求解

dfs(len) 返回 ≤ 當前數 x 的合法數個數：

1. 初始答案為 sum[len-1]（長度 < len 的所有合法數）。
2. 從高位向低位遍歷，維護當前已確定的 0 的個數 zero。
3. 若當前位為 1，考慮將其設為 0，後續位任意填，利用組合數快速計算合法方案數。
4. 最後檢查 x 本身是否合法（zero >= len - zero）。

完整代碼

#include <cstdio>
#include <cstring>
#include <vector>
#include <iostream>
using namespace std;
typedef long long ll;
const int N = 100;
int bit[N];
ll cnt[N], C[N][N], sum[N];

ll dfs(int len) {
    ll ans = sum[len - 1];
    int zero = (bit[len] == 0);
    for (int i = len - 1; i; i--) {
        if (bit[i] == 0) { zero++; continue; }
        int tmp = zero + 1;
        int siz = i - 1;
        if (tmp >= len - tmp) ans += 1LL << siz;
        else {
            for (int j = 0; j <= siz; j++)
                if (tmp + j >= len - tmp - j) ans += C[siz][j];
        }
    }
    ans += (zero >= len - zero);
    return ans;
}

ll solve(ll x) {
    if (x <= 1) return 1;
    int len = 0;
    for (ll tmp = x; tmp; tmp >>= 1) bit[++len] = tmp & 1;
    return dfs(len);
}

int main() {
    memset(C, 0, sizeof C);
    C[1][0] = C[1][1] = 1;
    for (int i = 2; i < N; i++) {
        C[i][0] = 1;
        for (int j = 1; j < N; j++) C[i][j] = C[i-1][j] + C[i-1][j-1];
    }
    cnt[1] = 1; sum[1] = 1;
    for (int i = 2; i < N; i++) {
        cnt[i] = 0;
        for (int j = 0; j <= i-1; j++)
            if (j >= i - j) cnt[i] += C[i-1][j];
        sum[i] = cnt[i] + sum[i-1];
    }
    long long l, r;
    while (cin >> l >> r)
        cout << solve(r) - solve(l - 1) << endl;
    return 0;
}

關鍵點總結

• 數位 DP 核心：將「≤ x」轉化為「長度 < len」+「長度 = len 且 ≤ x」。
• 組合數預處理避免重複計算，利用二進制位獨立性快速統計。
• 注意邊界：x=0,1 直接返回 1（0 的二進制視為 "0"，0 的個數 1 ≥ 0）。