Amount of Degrees

一本通·提高篇 · 代码 · cpp · 难度 4/5 · 共 1165 字

求[X,Y]中能表示为恰好K个互不相同的B的

一本通
例

正文

/*
原题：Amount of Degrees（一本通 5.3 例 1）
题意：求 [X,Y] 中能表示为恰好 K 个互不相同的 B 的整数次幂之和的整数个数。
思路：等价于：在 B 进制下，各位只能是 0 或 1，且恰好有 K 个 1（每个 1 对应一个 B 的幂）。
     对上界 n 做数位 DP，state=(pos,cnt,tight)，每位只放 0 或 1，末态 cnt==K 计数。
     答案 = f(Y) - f(X-1)。
复杂度：时间 O(log_B Y * K)，空间 O(log_B Y * K)
易错点：B 进制下每一位只能是 0 或 1；X-1 可能为 0，需特判。
*/
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int B, K;
int dig[40];
ll memo[40][40][2];
int len;
ll dfs(int pos, int cnt, bool tight){
    if(pos == len){
        return cnt == K ? 1 : 0;
    }
    if(memo[pos][cnt][tight] != -1) return memo[pos][cnt][tight];
    ll ans = 0;
    int up = tight ? dig[pos] : B - 1;
    for(int d = 0; d <= min(up, 1); d++){
        ans += dfs(pos + 1, cnt + (d == 1), tight && d == dig[pos]);
    }
    return memo[pos][cnt][tight] = ans;
}
ll f(ll n){
    if(n < 0) return 0;
    len = 0;
    ll t = n;
    while(t){
        dig[len++] = t % B;
        t /= B;
    }
    if(len == 0) dig[len++] = 0;
    reverse(dig, dig + len);
    memset(memo, -1, sizeof(memo));
    return dfs(0, 0, true);
}
int main(){
    ll X, Y;
    cin >> X >> Y >> K >> B;
    cout << f(Y) - f(X - 1) << "\n";
    return 0;
}

Amount of Degrees

正文

一本通·提高篇的其它内容