URAL 1057 Amount of Degrees：數位 DP 統計 B 進制下恰好 K 個不同冪次和的數

問題轉化

求區間 [X,Y] 中滿足：數 = K 個互不相同的 B 的整數次冪之和的整數個數。
即：該數的 B 進制表示中恰好有 K 個 1，其餘為 0（因為每個冪次最多取一次）。

關鍵技巧：B 進制 → 等價二進制

對於 B 進制數，只需關心每位是否為 1。將數從高位到低位掃描，首個非 0/1 位置為 1，其後所有位置為 1，得到一個等價的二進制數，其 1 的個數與原數在合法範圍內的計數邏輯一致。

預處理組合數

f[i][j] = C(i,j) 表示 i 位中選 j 個 1 的方案數。f[0][0]=1; f[i][0]=1; f[i][j]=f[i-1][j]+f[i-1][j-1]。

計數函數 cal(x, k)

統計 [0, x] 中二進制 1 個數 = k 的數：
從高位向低位，遇 1 累加 C(剩餘位數, k-已選1數)，已選 1 數 +1；最後若總 1 數 == k 則 +1（含 x 本身）。

主流程

1. 讀入 X,Y,K,B
2. 將 X-1、Y 轉為等價二進制 trans(x)
3. 答案 = cal(trans(Y), K) - cal(trans(X-1), K)

轉換函數 trans(x)

int trans(int x) {
    vector<int> v;
    while(x) { v.push_back(x%B); x/=B; }
    int ans=0;
    for(int i=v.size()-1;i>=0;--i) {
        if(v[i]==0 || v[i]==1) { ans += (v[i]? (1<<i) : 0); }
        else { // 首個非 0/1 位
            ans += (1<<i);
            for(int j=i-1;j>=0;--j) ans += (1<<j); // 後續全置 1
            break;
        }
    }
    return ans;
}

複雜度

預處理 O(32²)，單次查詢 O(log_B Y) ≈ 32，極快。