【Ural 1057】Amount of Degrees / 题解

好像很久没有发过题解了。。。

最近沉迷阅读无法自拔，《作为意志和表象的世界》和 The Great Gatsby 真好看。

Ural 原题地址

LibreOJ 原题地址

Statement

Create a code to determine the amount of integers, lying in the set [X;Y] and being a sum of exactly K different integer degrees of B.
Example. Let X=15, Y=20, K=2, B=2. By this example 3 numbers are the sum of exactly two integer degrees of number 2:
$17 = 2^4+2^0$,
$18 = 2^4+2^1$,
$20 = 2^4+2^2$.

Input

The first line of input contains integers X and Y, separated with a space $(1 ≤ X ≤ Y ≤ 2^{31}−1)$. The next two lines contain integers K and B $(1 ≤ K ≤ 20; 2 ≤ B ≤ 10)$.

Output

Output should contain a single integer — the amount of integers, lying between X and Y, being a sum of exactly K different integer degrees of B.

思路

一道经典的数位 DP 题。
这道题说白了就是直接求前缀和然后相减得到区间的答案。对于一个上限，直接把它转化成 b 进制数，然后讨论每一位的情况。

代码

#include 
using namespace std;
int k,b,f[50][50];
void init(){
    f[0][0]=1;
    for (int i=1;i<50;i++){
        f[i][0]=f[i-1][0];
        for (int j=1;j<=i;j++){
            f[i][j]=f[i-1][j]+f[i-1][j-1];
        }
    }
}
int solve(int l){
    vectorv;
    while(l){
        v.push_back(l%b);
        l/=b;
    }
    int cnt=0,ans=0;
    for (int i=v.size()-1;~i;i--){
        if (v[i]==1){
            ans+=f[i][k-cnt];
            cnt++;
            if (cnt==k) break;
        }
        if (v[i]>1){
            ans+=f[i+1][k-cnt];
            break;
        }
    }
    if (cnt==k) ans++;
    return ans;
}
int main(){
    ios::sync_with_stdio(false);
    init();int x,y;
    cin>>x>>y>>k>>b;
    cout<