| input | output |
|---|---|
15 20 2 2 |
3 |
题目大意：
求给定区间
[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 ≤ 231?1，1 ≤ K ≤ 20， 2 ≤ B ≤ 10。 分析：
所求的数为互不相等的幂之和，亦即其B进制表示的各位数字都只能是0和1。因此，我们只需讨论二进制的情况，其他进制都可以转化为二进制求解。
很显然，数据范围较大，不可能采用枚举法，算法复杂度必须是log(n)级别，因此我们要从数位上下手。
参考链接：http://wenku.baidu.com/view/d2414ffe04a1b0717fd5dda8.html
#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-8
typedef __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 pf printf
#define bug pf("Hi\n")
using namespace std;
#define INF 0x3f3f3f3f
#define N 35
int 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;
}
ural 1057 Amount of degrees （数位dp）
原文：http://blog.csdn.net/u014737310/article/details/44628613