Timus 1057 Amount of Degrees：數位 DP 求 B 進制下恰含 K 個 1 的數

問題轉化

求區間 [X, Y] 內有多少數可表示為 恰好 K 個不同的 B 的冪之和。即該數的 B 進制表示中恰有 K 個 1，其餘為 0（因為不同冪次對應不同位）。

解法：數位 DP + 狀態壓縮

1. 將上界 n 轉為 B 進制數組 bit[]
2. 若某位 >1，則該位及更低位可任意填 0/1（即後續位全為 1 的二進制掩碼）
3. 問題轉化為：求 ≤ 某二進制掩碼 mask 的數中，含 1 個數為 K 的個數

DP 定義

dfs(pos, cnt, tight, leading)：處理第 pos 位（高→低），已放 cnt 個 1，tight 表示是否受 mask 限制，leading 表示前導零狀態。

遞歸轉移

int dfs(int pos, int cnt, bool tight, bool leading) {
    if (pos < 0) return cnt == K;
    if (!tight && dp[pos][cnt] != -1) return dp[pos][cnt];
    int up = tight ? bit[pos] : 1;
    int ans = 0;
    for (int d = 0; d <= up; ++d) {
        bool nLeading = leading && (d == 0);
        int nCnt = nLeading ? 0 : cnt + d;
        ans += dfs(pos-1, nCnt, tight && (d==up), nLeading);
    }
    if (!tight) dp[pos][cnt] = ans;
    return ans;
}

完整代碼

#include <cstdio>
#include <cstring>
using namespace std;

int X, Y, K, B;
int bit[35], dp[35][65];

int dfs(int pos, int cnt, bool tight, bool leading) {
    if (pos < 0) return cnt == K;
    if (!tight && dp[pos][cnt] != -1) return dp[pos][cnt];
    int up = tight ? bit[pos] : 1;
    int ans = 0;
    for (int d = 0; d <= up; ++d) {
        bool nLeading = leading && (d == 0);
        int nCnt = nLeading ? 0 : cnt + d;
        ans += dfs(pos-1, nCnt, tight && (d==up), nLeading);
    }
    if (!tight) dp[pos][cnt] = ans;
    return ans;
}

int solve(int n) {
    int len = 0;
    while (n) { bit[len++] = n % B; n /= B; }
    int mask = 0;
    for (int i = len-1; i >= 0; --i) {
        if (bit[i] > 1) {
            for (int j = i; j >= 0; --j) mask |= (1<