题目描述
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 Kdifferent 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 = 2^4+2^0,
18 = 2^4+2^1,
20 = 2^4+2^2.
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
input | output |
---|---|
15 20 2 2 |
3 |
Problem Source: Rybinsk State Avia Academy
Tags: none (hide tags for unsolved problems)
输入
15 20 2 2
输出
3
样例输入
15 20 2 2
样例输出
3
题解
题目的意思是找在区间[x,y]之间满足能够由k个b的不同次幂相加得到的数的总数。这题的关键是转换进制,之前几道题我们保存的是数的每位数,其实也就是10进制,这题我们要保存的是b进制,所以在solve函数中要把原来的对10求余和除10都要改成对b进行操作,dp[pos][sta]数组表示第pos位由sta个b的不同次幂相加得到的数的总数。在判断进入递归的if条件语句中,i的上界要同时满足小于上界且小于等于1,因为根据题意,只有类似3^4次方能够算进去,2*3^4并不能计入,也就是说系数必须小于等于0,且只有等于1时,sta才能增1。还有最后一个要注意的是当pos=0递归结束时,只有当sta=k时,才是符合条件的数,ans才能增加。
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
int n,m,k,b;
int a[20],dp[20][10];
int dfs(int pos,int sta,bool limit)
{
if(pos==0)
return sta==k;//是否满足条件
if(!limit&&dp[pos][sta]!=-1)
return dp[pos][sta];
int ans=0;
int up=limit?a[pos]:b-1;
for(int i=0;i<=up&&i<=1;i++)
//因为题意规定了系数为,即不允许*4^2这样的形式,只能^2这样的形式,所以满足条件的系数一定为
ans+=dfs(pos-1,sta+(i==1),limit&&i==a[pos]);
if(!limit)
dp[pos][sta]=ans;
return ans;
}
int solve(int x)
{
int pos=0;
while(x)
{
a[++pos]=x%b;
x/=b;
}
return dfs(pos,0,1);
}
int main()
{
cin>>n>>m>>k>>b;
memset(dp,-1,sizeof(dp));
cout<<solve(m)-solve(n-1)<<endl;
return 0;
}