思路

具体举例

比如B进制数:653420,填3个1
因为只能填1或者0,所以可以用最高位来划分方案数:
一.最高位填0,即 0 _ _ _
因为最高位为6,所以后面5个位次可以随便填,在5个位次中找3个1;
所以方案数为c[5][3];
二.最高位填1,即 1 _ _ _
因为最高位为6,6>1,所以后面5个位次可以随便填,在五个位次中找2个1;
所以方案数为c[5][2];

再比如B进制数:13132,填3个1;
一.最高位填0即0 _ _
因为1>0,所以后面4个位次随便填,在四个位次中找三个1;
所以方案数为c[4][3];
二.最高位填1,即 1 _ _ _
因为最高位就是1,所以后面的数并不能乱填
(比如B进制数:10101,11010就大于B,为不合法方案)
继续划分到下一位次 3 ,再对该位次进行讨论;

#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>

using namespace std;

int c[35][35];//存储组合数
int K,B;

void cbp()
{
    for(int i=0;i<35;i++)
     for(int j=0;j<=i;j++)
     {
         if(!j) c[i][j]=1;
         else c[i][j]=c[i-1][j]+c[i-1][j-1];
     }
}

int dp(int n)
{
    if(!n) return 0;

    vector<int> num;

    while(n) num.push_back(n%B),n/=B;

    int ans=0,one=0;//one表示已经填了多少个1

    for(int i=num.size()-1;i>=0;i--)
    {
        int t=num[i];
        //若t=0,那t只能等于0,到下一位次继续进行划分;
        if(t)//对第i为进行讨论
        {
            ans+=c[i][K-one];//第i位填0,剩下i-1位填K-one个1
            //第i位填1的情况
            if(t>1)
            {
                if(K-one-1>=0) ans+=c[i][K-one-1];//第i位填1,剩下的i-1位填剩余个1
                break;//方案数已经枚举完毕,无须再进行讨论
            }
            else
            {
                one++;//t=1,剩下的位次不能乱填,所以再进行讨论划分
                if(one>K) break;
            }
        }

        if(!i&&one==K) ans++;//进行到底了,那么也算一种方案数,算上
    }

    return ans;
}

int main()
{
    int x,y;
    scanf("%d%d%d%d",&x,&y,&K,&B);

    cbp();

    cout<<dp(y)-dp(x-1)<<endl;

    return 0;
}