Amount of Degrees
Amount of Degrees
题目描述
求给定区间\([X,Y]\)中满足下列条件的整数个数：这个数恰好等于\(K\)个互不相等的 的整数次幂之和。例如，设\(X=15, Y=20, K=2, B=2\) ，则有且仅有下列三个数满足题意：
\(17 = 2^4+2^0\)
\(18 = 2^4 + 2^1\)
\(20 = 2^4+2^2\)
输入格式
第一行包含两个整数\(X\)和\(Y\)，接下来两行包含整数\(K\)和\(B\)。
输出格式
第一行包含两个整数 和 ，接下来两行包含整数 和 。
样例输入
15 20
2
2
样例输出
3
Hint
对于全部数据，\(1 \leq X \leq Y \leq 2^{31}-1,1 \leq K \leq 20,2 \leq B \leq 10\)。
思路
以二进制为例，统计整数次幂个数也就是代表对应进制下1的个数，我么可以确定一个对用数位的二叉树，每层保存一个数位，左0右1，这样就可以列出所有数，之后在这颗树上记忆化搜索，初始化将符合条件的树记录，则有一个递推式：\(cnt[i][j] = cnt[i-1][j]+cnt[i-1][j-1]\),搜索时，每次移动到右子树则统计左子树的符合条件的结果。
Code
/**********************************************************
* @Author: Kirito
* @Date: 2020-04-12 15:40:43
* @Last Modified by: Kirito
* @Last Modified time: 2020-04-12 17:08:04
* @Remark:
**********************************************************/
#include <bits/stdc++.h>
#define lowbit(x) (x&(-x))
#define CSE(x,y) memset(x,y,sizeof(x))
#define INF 0x3f3f3f3f
#define Abs(x) (x>=0?x:(-x))
#define FAST ios::sync_with_stdio(false);cin.tie(0);
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll , ll> pll;
const int maxn=35;
int cnt[maxn][maxn], digit[maxn];
int x, y, b, k;
void ini()
{
CSE(cnt, 0);
cnt[0][0] = 1;
for(int i = 1; i <= 32; i++)
{
cnt[i][0] = cnt[i - 1][0];
for(int j = 1; j <= i; j++)
{
cnt[i][j] = cnt[i - 1][j] + cnt[i - 1][j - 1];
}
}
return;
}
int get_ans(int x, int k)
{
int pos = 1;
while(x)
{
digit[pos++] = x % b;
x /= b;
}
int ans = 0; pos -= 1;
while(pos >= 1)//因为会用到pos - 1，所以这里用从1开始的下标
{
if(digit[pos] > 1){//如果该位大于1，则比此位数小的所有含有k个1的均成立，直接计算
ans += cnt[pos - 1][k] + cnt[pos - 1][k -1];
break;
}
else if(digit[pos] == 1)//此位为1，那么考虑下一位含有k - 1个1的情况
{
ans += cnt[pos - 1][k];
k--;
}
if(k < 0)//已经找到k个1则直接退出
break;
pos--;
}
return ans;
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("in.in","r",stdin);
#endif
FAST;
ini();
while(cin >> x >> y >> k >> b)
{
cout << get_ans(y + 1, k) - get_ans(x, k) << endl;
}
return 0;
}
