前言

看过了视频，以及各位大佬的题解，感觉自己还是有很多东西想不明白，因此总结了一下各位大佬的思路，顺道记录一下自己关于小细节的理解

做法

基本思想

数位dp的两个核心
（1）将一段区间l-r，转换为从1-r的方案数f，然后利用类似前缀和的思想，最终求出答案
（2）用树的形式考虑问题

具体做法

给定一个数X，1-X中，恰好有K个互不相等的B的整数次幂纸和，可以转换为如下形式
将数转化为B进制表示
不妨设X的b进制表示为$a_{n-1},a_{n-2},....,a_{0} $,则对于每一个1-
，其中对于每个数字的各个位数，只有K个1，其余全为0，问满足这样的条件的数字有多少个。
证明：若某位上的数字大小超过1，则至少为2，则至少有两个每次相同的B的整数次幂和，产生矛盾；
同理也不能有多余K个1，否则也会产生矛盾
注意 ： 我们不能直接用组合数求出究竟有多少个方案。
因为对于每一位，并不是都能完整的取到0和1，
例如，对于X=19,三进制表示为$(201)_{3} $则第二位显然不可能取1.
具体来看，
对于X的每一位数字，先记为x，
（1）若x>1,则可以取0或1，此时已经可以算出所有可能结果了,因此此时可以直接结束。
（2）若x=1，此时答案分为两部分，x可以取0，后边数无大小限制，直接用组合数算出答案；x取1，还需要继续向后找。
（3）若x=0，直接略过

关于视频中的一些理解

图片可以看视频中相应位置。
实际上，这个树形分支并不是总两边都存在的。
x>1时，两个分支都有，但是右半部分的分支由于是>1的因此没有必要继续讨论下去，直接break了；而左边可以直接用组合数求出来
x=1时，左部分分支为0，右部分分支为1，左部分可以直接用组合数求出来，右部分需要继续讨论接下来的位置
x=0时，只有右部分分支，可以直接略过这个位置（因为左半部分没有）。

细节

对于最后一位时，有可能会存在特殊情况，此部分结合代码看。
注意到，前面所有位置，最大位都是0或者1，且last<=k,且每个位置都取了最大值。
换句话说，仅剩下最右分支没有讨论。
（1）x>1,
显然此时左部分会通过最后一次循环计算出来
(2)x=1，若last==k，则由于$C_{0}^{0}=1$，左分支0已经被算好并且右分支直接break，last=k+1，最后不会额外计算
若last<k，则此时左分支显然贡献为0，右分支若能保证更新后为last=k，则最后会额外判断一个+1.
(3)x=0,若前面已经选够了k个（last==k），则此时显然是一个合理答案，res++。
最后，综上理解，特判仅仅是看是否可以更新右半边

代码同之前题解

#include <iostream>
#include <algorithm>
using namespace std;

const int N = 37;

int f[N][N];  //组合数
int k,b;
int l,r;

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-1] + f[i-1][j];
}

int dp(int n){
    int res = 0, last = 0;
    if(!n) return res;

    vector<int> a;
    while(n) a.push_back(n%b),n/=b;

    int len = a.size()-1;
    for(int i = len; i>=0; --i){
        int x = a[i];
        if(x){
            res += f[i][k-last];  //第i位放0，后i-1位放k-last个1(0~i-1位，所以第i位后面有i位)
            if(x>1){
                //第i位放1,后i-1位放k-last-1个1
                if(k-last-1>=0) res += f[i][k-last-1];
                break;  //这一位已经不合法了，所以上一步结束后直接break
            }else{
                //如果x为1，考虑到组成的数必须比原数字小，所以这里不能用组合数计算
                last++;
                if(last>k) break;  //1如果放完了，直接break
            }
        }
        if(!i && last == k) res ++;  //树的最右侧的分支
    }
    return res;
}
int main()
{
    init();  //预处理出组合数

    cin>>l>>r>>k>>b;
    cout<<dp(r) - dp(l-1);
    return 0;
}