二刷提高课，题解目录在这里— 提高课的题解目录

数位DP的开篇，这一篇均是从数的角度开思考问题
首先使用了前缀和思想若是问我们l~r的问题我们转换为0~r-0~l-1的问题
其次（以r为例）我们将r以十进制位数展开（这里因题目而异此题是以B进制展开）
从高位向低位思考，从而看符合要求的数目
这一题问将某个数看为K个互不相等的B的整数次幂之和，其实言外之意就是问
某个数能否被B进制表示且只有k个1其他全为0（不是1就是0）
所以我们使用数位DP可以解决

#include<iostream>
#include<vector>
using namespace std;
const int N=35;
int f[N][N];
int l,r,k,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];
        }
    }
}
int dp(int x)
{
    if(!x)return 0;//一定要注意处理边界问题！
    vector<int >sum;
    int res=0,last=0;
    while(x)sum.push_back(x%b),x/=b;
    for(int i=sum.size()-1;i>=0;i--)
    {
        int xx=sum[i];
        if(xx)
        {
            res+=f[i][k-last];
            if(xx>1)
            {
                if(k-last-1>=0)res+=f[i][k-last-1];
                break;
                //注意因为只有选1或0两种选择所以不存在选xx-1直接break
            }
            last++;
            if(last>k)break;
            //当等于k的时候可能后面还有1的情况让他们取0也是一种情况
        }
        if(!i&&last==k)res++;
        //i==0是顺利从头到尾，均取了1，last==k是判断是否用了k个1
    }
    return res;
}
int main()
{
    cin>>l>>r>>k>>b;
    init();
    cout<<dp(r)-dp(l-1);
    return 0;
}