$\huge \color{orange}{成魔之路->}$ $\huge \color{purple}{算法提高课题解}$

思路：

1. 预处理组合数，公式 f[i][j] = f[i - 1][j - 1] + f[i - 1][j]
2. dp(n) 表示 0 ～ n 中符合有 K 个 1 的 B 进制数的个数，last 表示已经确定的 1 的个数
3. 对于 abcdefg，当前位可以填 0 ～ a - 1 ......
4. 如果可以填 0，则 res += f[i][K - last]
5. 如果可以填 1，则 res += f[i][K - last - 1]，然后 break
6. 如果说当前位就是 1，那么 last ++
7. 最后如果当前数字也符合条件，那么 res ++

完整代码

#include<bits/stdc++.h>

using namespace std;

const int N = 35;

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

//预处理
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];
}

// 0 ～ n 中符合条件的数的个数
int dp(int n)
{
    if(!n) return 0;

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

    int res=0,last=0;
    for(int i=nums.size()-1;i>=0;i--)
    {
        int x=nums[i];
        if(x)
        {
            //左分支，当前位可以填0
            res+=f[i][K-last];

            //左分支，当前位可以填1
            if(x>1)
            {
                res+=f[i][K-last-1];
                break;
            }

            //当前位就是1
            else
            {
                last++;
                if(last>K) break;
            }
        }
        if(!i&&last==K) res++;
    }

    return res;
}

int main()
{
    init();

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

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

    return 0;
}