如果数位dp一直是这个难度，我将永远和数位dp告别

我记得有篇博客叫做“刘聪浅谈数位dp”

里面有幅图，挺好看的

很久之前写的了代码

忘了为什么要这么做

QwQ

#include
     
      #define re return #define reg register #define ll long long #define inc(i,l,r) for(int i=l;i<=r;++i)#define dec(i,l,r) for(int i=l;i>=r;--i)using namespace std;ll l,r,k,b,f[44][44],num[44];void vivi(){    f[0][0]=1;    inc(i,1,31){        f[i][0]=f[i-1][0];        inc(j,1,i)            f[i][j]=f[i-1][j]+f[i-1][j-1];    }} ll solve(ll x){    int len=0;    while(x){        num[++len]=x%b;        x/=b;    }        ll ans=0,cnt=0;    dec(i,len,1)    if(num[i]==1)    {        ans+=f[i-1][k-cnt];        ++cnt;        if(cnt==k)re ans+1;    }    else if(num[i]>1)re ans+f[i][k-cnt];        re ans;}int main(){//    freopen("in.txt","r",stdin);    scanf("%lld%lld%lld%lld",&l,&r,&k,&b);    vivi();    printf("%lld ",solve(r)-solve(l-1));        re 0;}