[TimusOJ1057]Amount of Degrees
[TimusOJ1057]Amount of Degrees
试题描述
Create a code to determine the amount of integers, lying in the set [X;Y] and being a sum of exactly K different integer degrees of B.
Example. Let X=15, Y=20, K=2, B=2. By this example 3 numbers are the sum of exactly two integer degrees of number 2:
17 = 24+20,
18 = 24+21,
20 = 24+22.
18 = 24+21,
20 = 24+22.
输入
The first line of input contains integers X and Y, separated with a space (1 ≤ X ≤ Y ≤ 231−1). The next two lines contain integers K and B (1 ≤ K ≤ 20; 2 ≤ B ≤ 10).
输出
Output should contain a single integer — the amount of integers, lying between X and Y, being a sum of exactly K different integer degrees of B.
输入示例
15 20 2 2
输出示例
3
数据规模及约定
见“输入”
题解
就是看转换成 b 进制之后是不是只有 0 和 1 并且 1 的个数恰好等于 k。
行了，明白了题意，就没啥可说的了。
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <algorithm>
using namespace std;
int read() {
int x = 0, f = 1; char c = getchar();
while(!isdigit(c)){ if(c == '-') f = -1; c = getchar(); }
while(isdigit(c)){ x = x * 10 + c - '0'; c = getchar(); }
return x * f;
}
#define maxn 35
#define maxk 25
int f[maxn][2][maxk], K, b;
int num[maxn];
int sum(int x) {
int cnt = 0, tx = x;
while(x) num[++cnt] = x % b, x /= b;
int ans = 0, Cnt = 0;
for(int i = cnt; i; i--) {
for(int j = 0; j < min(2, num[i]); j++) ans += f[i][j][K-Cnt];
if(num[i] > 1){ Cnt = -1; break; }
Cnt += num[i];
}
ans += (Cnt == K);
return ans;
}
int main() {
f[1][0][0] = 1; f[1][1][1] = 1;
for(int i = 1; i <= 32; i++)
for(int j = 0; j <= 1; j++)
for(int k = 0; k <= i; k++)
for(int x = 0; x <= 1; x++)
f[i+1][x][k+x] += f[i][j][k];
int l = read(), r = read(); K = read(); b = read();
printf("%d
", sum(r) - sum(l - 1));
return 0;
}