代码注释应该写的还行

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N=110;
int al,l,r,b;
int f[N][N],k,a[N];
int dp(int pos,int st,int op){
    if(!pos) return st == k;//后面再没有更低的位了，返回当前方案是否成立
    if(!op && f[pos][st] != -1) return f[pos][st];//当前方案不是需要限制的（边界）且已经被搜过，返回方案数
    int res=0,maxx=op?min(a[pos],1):1;//能不能填1
    for(int i=0;i <= maxx;i++){
        if(st+i>k) continue;//不符合限制
        res += dp(pos-1,st+i,op && i == a[pos]);//加上下一位（更低的位）的情况（回溯时的情况）
    }
    return op?res:f[pos][st]=res;//当前方案数是否顶着边界（是否能够记录）
}
int calc(int x){//将当前数转化为B进制
    al=0;
    memset(f,-1,sizeof(f));
    while(x) a[++al]=x%b,x /= b;//类比十进制
    return dp(al,0,1);//数位dp
}
int main(){
    scanf("%d%d%d%d",&l,&r,&k,&b);
    printf("%d\n",calc(r)-calc(l-1));//前缀和
}

/*
sasakure.UK is the only god.
*/