套用数位DP模板

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll x,y,k,b,ans;
int a[100],tot;
int C(int x,int y)
{
    if(y==0)
        return 1;
    if(y>x)
        return 0;
    ll ans=1;
    for(int i=x-y+1;i<=x;i++)
        ans*=i;
    for(int i=1;i<=y;i++)
        ans/=i;
    return ans;
}
void dfs(int x,int s,int eg)
{
    if(!eg||!s||!x)
    {
        ans+=C(x,s);
        return;
    }
    if(a[x]==1)
        dfs(x-1,s-1,1);
    else if(a[x]>1)
        dfs(x-1,s-1,0);
    if(a[x]==0)
        dfs(x-1,s,1);
    else
        dfs(x-1,s,0);
}
int sss(int x)
{
    tot=ans=0;
    memset(a,0,sizeof(a));
    while(x)
    {
        a[++tot]=x%b;
        x/=b;
    }
    dfs(tot,k,1);
    return ans;
}
int main()
{

    cin>>x>>y;
    cin>>k>>b;
    cout<<sss(y)-sss(x-1)<<endl;
    return 0;
}