AcWing 1081. 度的数量

求给定区间 [X,Y]中满足下列条件的整数个数：
这个数恰好等于K个互不相等的B的整数次幂之和。

例如，设 X=15,Y=20,K=2,B=2，
则有且仅有下列三个数满足题意：

17=24+20

18=24+21

20=24+22

输入格式
第一行包含两个整数 X和 Y，接下来两行包含整数K和B。

输出格式
只包含一个整数，表示满足条件的数的个数。

数据范围
1≤X≤Y≤2^31−1
1≤K≤20，2≤B≤10

#include<bits/stdc++.h>

using namespace std;

const int N = 35;

int l,r,K,B;
int f[N][N];//f[a][b]从a个数中选b个数

//预处理
void init()
{
    for(int i=0;i<N;i++)
        for(int j=0;j<=i;j++)
            if(!j) f[i][j]=1;
            else f[i][j]=f[i-1][j]+f[i-1][j-1];
}

// 0 ～ n 中符合条件的数的个数
int dp(int n)
{
    if(!n) return 0;//边界返回

    vector<int> nums;
    while(n)//处理为B进制下的
    {
        nums.push_back(n%B);
        n/=B;
    }

    int res=0,last=0;//res表示一共有几个数 last表示前i位（包括i)已经有几个1
    for(int i=nums.size()-1;i>=0;i--)//枚举每一位数
    {
        int x=nums[i];//取出每一位数
        if(x)//该分支上在B进制下的数（0~B-1）已排除当前位 == 0 的情况
        {
            //左分支，当前位可以填0(x>=1 该数位都可以填 0 ）
            res+=f[i][K-last];

            //当前位 > 1
            //左分支，当前位可以填1
            if(x>1)
            {
                if (K - last - 1 >= 0) res+=f[i][K-last-1];
                break;//分支不存在
            }

            //当前位 x == 1
            else
            {
                last++;
                if(last>K) break;//当当前1个数超过目标时 分支不存在
            }
        }
        //右分支（无法用组合数计算的） 到了最右下角 符合题目条件时
        if(!i && last==K) res++;
    }

    return res;
}

int main()
{
    init();

    cin>>l>>r>>K>>B;

    cout<<dp(r)-dp(l-1)<<endl;

    return 0;
}