题目描述

注释版，仅记录。

(暴力枚举) $O(n^2)$

C++ 代码

#include<cstdio>
#include<cstring>
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

const int N=35;

/*第一次写的时候有点懵，下面是我思考时的漏洞。
考虑更多的边界问题：
某个数的B进制表示是7654321，遍历到最高位，也就是x=7,左分支的话是[0000 000]到6(B-1)....，从中选取了k个1后break。那么从[6(B-1)....]到[7654321]就没有计算啊？
这里从6..2开始的话直接就不满足题意了，所以break。

那么另一种想法，19的三进制表示201 ，这里最高位如果选1或者选0，后面都不会出现超过该区间的情况，所以可以直接用组合数去求。
*/

int f[N][N];
int l,r,K,B;

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

//dp数组是求1~n的方案总和，而不是n。
int dp(int n)
{
    if(!n) return 0;

    vector<int> nums;
    while(n) nums.push_back(n%B),n/=B;

    int res=0;
    int last=0;
    for(int i=nums.size()-1;i>=0;i--)
    {
        int x=nums[i];
        if(x)
        {
            res+=f[i][K-last];      //i位为0
            if(x>1)     //i位大于1，则i位可以为1或二；
            {
                if(K-last-1 >=0) res+=f[i][K-last-1];
                break;      //该情况下，树中已经无子节点，需要break掉。当然，如果递归做的话是return掉，这样说可能比较容易理解。
            }
            else    //i为1，则
            {
                last++;
                if(last>K) break;   //如果前面放置1的个数已经大于K，则直接舍弃
            }
        }
        if(!i && last == K) res++;
    }

    return res;
}

int main()
{
    init();

    cin>>l>>r>>K>>B;

    cout<<dp(r)-dp(l-1)<<endl;

    return 0;
}