题目描述
求给定区间 [X,Y] 中满足下列条件的整数个数:这个数恰好等于K个互不相等的B的整数次幂之和。
例如,设 X=15,Y=20,K=2,B=2,则有且仅有下列三个数满足题意:
17=24+20
18=24+21
20=24+22
输入格式
第一行包含两个整数 X 和 Y,接下来两行包含整数 K 和 B。
输出格式
只包含一个整数,表示满足条件的数的个数。
数据范围
1≤X≤Y≤231−1,1≤K≤20,2≤B≤10
样例
blablabla
算法
数位DP
详细见代码注释
时间复杂度
参考文献
C++ 代码
/*
思路: //注:此题解中的组合数C(a, b)中a在下,b在上
题意可转化为:[X, Y]中,求二进制只包含两个1的数的个数
数位DP的技巧:
1.[X, Y] => f(y) - f(x-1) (f(x)为[1, x]满足条件的数的个数,类似于前缀和)
2.从树的角度:
本题求f(N):
设N的每一位从高到低为:a[n-1],a[n-2],...,a[0] (N是n位数)
当前数的,每一位取法的分类(填k个1)(每一位那你能取0~a[i],每一位能选择填1与不填1):
根
/ \
第一位: 0~a[n-1]-1 a[n-1]
(组合数C(n-1, k)与C(n-1, k-1)) / \
第二位: 0~a[n-2]-1 a[n-2]
(C(n-2, k)) / \
第三位: 0~a[n-3]-1 a[n-3]
. .
. .
. .
/ \
第n位: 0~a[0]-1 a[0]
总:所有左边分支的组合数和右边分支最后的a[0]
细节:
1.C(a, b) = C(a-1, b-1) + C(a-1, b)
*/
#include <bits/stdc++.h>
using namespace std;
const int N = 35;
int 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]; //组合数C
}
int dp(int n)
{
if (!n) return 0; //特判边界区间中没有数字有1
vector<int> nums; //存储n的B进制
while (n) nums.push_back(n % B), n /= B;
int res = 0; //答案
int last = 0; //前面的信息(前面有多少个1)
for (int i = nums.size() - 1; i >= 0; i -- )
{
int x = nums[i];
//分两类:
if (x) //左边分支:只有x > 0,才有左边分支,这里求左边分支中的满足要求数的个数
{
res += f[i][K-last]; //当前数填0
if(x > 1) //当前数填1
{
if(K - last - 1 >= 0) res += f[i][K-last-1];
break; //因为题目中说过只能填0和1,所以填a[i-1]的情况不存在,没有右边分支
}
else
{
last ++ ;
if(last > K) break; //当前1的个数大于要求的个数,不存在合法方案
}
}
if (!i && last == K) res ++ ; //已经走到最后一位且个一走右边分支
}
return res;
}
int main()
{
init();
int l, r;
cin >> l >> r >> K >> B;
cout << dp(r) - dp(l-1) << endl;
return 0;
}