1057. Amount of Degrees
Time limit: 1.0 secondMemory limit: 64 MB
Create a code to determine the amount of integers, lying in the set [X;Y] and being a sum of exactlyKdifferent integer degrees ofB.
Example.LetX=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.
Input
The first line of input contains integersXandY, separated with a space (1≤X≤Y≤2311). The next two lines contain integersKandB(1≤K≤20; 2≤B≤10).
Output
Output should contain a single integer— the amount of integers, lying betweenXandY, being a sum of exactlyKdifferent integer degrees ofB.
Sample
inputoutput
15 20223
题目大意：
求给定区间
[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
。
输入
：第一
行包含两
个
整
数
X
和
Y
。
接下来两行包含整
数
K
和
B
。
输出
：
只包含
一个
整
数，
表示
满足条件的数的个数。
数
据规模
：
1
≤
X
≤
Y
≤
2
31
1
，
1
≤
K
≤
20
，
2
≤
B
≤
10
。
浅谈数位类问题 刘聪第 1页，共 12页浅谈数位类统计问题山东省青岛第二中学 刘聪【摘要】在信息学竞赛中，有一类与数位有关的区间统计问题。这类问题往往具有比较浓厚的数学味道，无法暴力求解，需要在数位上进行递推等操作。本文通过几个例子，简要介绍了解决此类问题的基本思想和方法。【关键字】数位 区间 统计 递推 树 二进制【正文】在信息学竞赛中，有这样一类问题：求给定区间中，满足给定条件的某个D进制数或此类数的数量。所求的限定条件往往与数位有关，例如数位之和、指定数码个数、数的大小顺序分组等等。题目给定的区间往往很大，无法采用朴素的方法求解。此时，我们就需要利用数位的性质，设计log(n)级别复杂度的算法。解决这类问题最基本的思想就是“逐位确定”的方法。下面就让我们通过几道例题来具体了解一下这类问题及其思考方法。【例题1】Amount of degrees (ural 1057)题目大意：求给定区间[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 ≤ 2311，1 ≤ K ≤ 20， 2 ≤ B ≤ 10。 分析：所求的数为互不相等的幂之和，亦即其B进制表示的各位数字都只能是0和1。因此，我们只需讨论二进制的情况，其他进制都可以转化为二进制求解。很显然，数据范围较大，不可能采用枚举法，算法复杂度必须是log(n)级别，因此我们要从数位上下手。
参考链接：
#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#include<cmath>#include<queue>#include<stack>#include<vector>#include<set>#include<map>#define L(x) (x<<1)#define R(x) (x<<1|1)#define MID(x,y) ((x+y)>>1)#define eps 1e-8typedef __int64 ll;#define fre(i,a,b) for(i = a; i <b; i++)#define free(i,b,a) for(i = b; i >= a;i–)#define mem(t, v) memset ((t) , v, sizeof(t))#define ssf(n)scanf("%s", n)#define sf(n)scanf("%d", &n)#define sff(a,b) scanf("%d %d", &a, &b)#define sfff(a,b,c) scanf("%d %d %d", &a, &b, &c)#define pfprintf#define bugpf("Hi\n")using namespace std;#define INF 0x3f3f3f3f#define N 35int f[N][N],le,ri;int k,b;int a[40];void inint(){int i,j;f[0][0]=1;fre(i,1,N){f[i][0]=f[i-1][0];fre(j,1,i+1)f[i][j]=f[i-1][j]+f[i-1][j-1];}}int solve(int x){ int i,j,p=0; while(x) {a[p++]=x%b;x/=b; }int tot=0; int ans=0;free(i,p-1,0) {if(a[i]==1){ans+=f[i][k-tot];tot++;if(tot>k) break;}else if(a[i]>1){ans+=f[i][k-tot-1];ans+=f[i][k-tot];break;}} return ans;}int main(){ int i,j; inint(); while(~scanf("%d%d",&le,&ri)) {scanf("%d%d",&k,&b);pf("%d\n",solve(ri+1)-solve(le)); } return 0;}
关于爱情的句子：情不知所起，一往而情深。
