http://acm.timus.ru/problem.aspx?space=1&num=1057
?
1057. Amount of Degrees
Time limit: 1.0 second
Memory limit: 64 MB
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.
Input
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
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.
Sample
/**
Timus OJ 1057 数位dp
题目大意：求出在给定区间内由多少个数可以表示为k个不同的b的幂之和
解题思路：对于一个数n，可以求比它小的数的个数有多少个满足条件，首先将n转化为b进制，然后用二进制表示状态，如果b进制下第i位上的数为1，那么对应二进制数为1，
如果为0对应二进制位为0，如果b进制下第i位上的数大于1，那么从第i为往后的二进制位全部置1，得到一个二进制数ans那么该问题就转化为求所有小于等于ans
的二进制数中含有m个1的数有多少个？dp[i][j]表示i二进制位数含j个1的数有多少个，采用记忆化搜索写挺方便
*/
#include
#include
#include
#include
using namespace std; int x,y,k,b; int bit[35],dp[35][65]; int dfs(int len,int num,int flag,int first) { if(len<0)return num==k; if(flag==0&&dp[len][num]!=-1) return dp[len][num]; int ans=0; int end=flag?bit[len]:1; for(int i=0;i<=end;i++) { int t=first&&(i==0); ans+=dfs(len-1,t?0:num+(i==1),flag&&i==end,t); } if(flag==0) dp[len][num]=ans; return ans; } int solve(int n) { int len=0; while(n) { bit[len++]=n%b; n/=b; } int ans=0; for(int i=len-1;i>=0;i--) { if(bit[i]>1) { for(int j=i;j>=0;j--) ans|=(1<
>=1; } return dfs(len-1,0,1,1); } int main() { while(~scanf("%d%d%d%d",&x,&y,&k,&b)) { memset(dp,-1,sizeof(dp)); printf("%d\n",solve(y)-solve(x-1)); } return 0; }
?