# 【数位DP】Amount of Degrees

2019/7/22 9:17:22 人评论 次浏览 分类：学习教程

## 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`

### 题解

``````#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;
}
``````

暂无相关的资讯...

-->