题目描述

求给定区间 [X,Y] 中满足下列条件的整数个数：这个数恰好等于 K 个互不相等的 B 的整数次幂之和。

例如，设 X=15,Y=20,K=2,B=2，则有且仅有下列三个数满足题意：

$17=2^4+2^0$
$18=2^4+2^1$
$20=2^4+2^2$

样例

输入
15 20
2
2

输出
3

数位DP

K个互不相同的B的整数次幂，等价于求数字num在B进制表示下是否是由K个1且其他位全是0组成，可用数位Dp来做。

对于数字num，存放其每一位上的数字(B进制表示下)，从高位向低位枚举，假设枚举到第i位，第i位上的数字是x，那么分以下几种情况讨论：

• 1.x == 0
  那么第i位只能是0，后面数位上现在都不能确定，只能继续向后看.
• 2.x == 1
  这里第i位可以分成两种情况：
  • 1.第i位放0，那么后面的数位上可以放k-last个1，res += f[i][k-last];
  • 2.第i位放1，那么后面数位上的情况不能用组合数计算，因为要保证答案中的数字比原数字要小
• 3.x > 1
  同样第i位分成两种情况
  • 1.第i位放0，那么后面的数位上可以放k-last个1，res += f[i][k-last];
  • 2.第i位放1，那么后面的数位上可以放k-last-1个1，res += f[i][k-last-1];

C++ 代码

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

using namespace std;

const int N = 34;

int f[N][N];  //组合数
int k,b;
int l,r;

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

int dp(int n){
    int res = 0, last = 0;
    if(!n) return res;

    vector<int> a;
    while(n) a.push_back(n%b),n/=b;

    int len = a.size()-1;
    for(int i = len; i>=0; --i){
        int x = a[i];
        if(x){
            res += f[i][k-last];  //第i位放0，后i-1位放k-last个1(0~i-1位，所以第i位后面有i位)
            if(x>1){
                //第i位放1,后i-1位放k-last-1个1
                if(k-last-1>=0) res += f[i][k-last-1];
                break;  //这一位已经不合法了，所以上一步结束后直接break
            }else{
                //如果x为1，考虑到组成的数必须比原数字小，所以这里不能用组合数计算
                last++;
                if(last>k) break;  //1如果放完了，直接break
            }
        }
        if(!i && last == k) res ++;  //树的最右侧的分支
    }
    return res;
}
int main()
{
    init();  //预处理出组合数

    cin>>l>>r>>k>>b;
    cout<<dp(r) - dp(l-1);
    return 0;
}