【Ural 1057】Amount of Degrees / 题解
好像很久没有发过题解了。。。
最近沉迷阅读无法自拔,《作为意志和表象的世界》和 The Great Gatsby 真好看。
Ural 原题地址
LibreOJ 原题地址
Statement
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 = 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 ≤ 2^{31}−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.
思路
一道经典的数位 DP 题。
这道题说白了就是直接求前缀和然后相减得到区间的答案。对于一个上限,直接把它转化成 b 进制数,然后讨论每一位的情况。
代码
#include
using namespace std;
int k,b,f[50][50];
void init(){
f[0][0]=1;
for (int i=1;i<50;i++){ f[i][0]="f[i-1][0];" for (int j="1;j<=i;j++){" f[i][j]="f[i-1][j]+f[i-1][j-1];" } int solve(int l){ vectorv;
while(l){
v.push_back(l%b);
l/=b;
}
int cnt=0,ans=0;
for (int i=v.size()-1;~i;i--){
if (v[i]==1){
ans+=f[i][k-cnt];
cnt++;
if (cnt==k) break;
}
if (v[i]>1){
ans+=f[i+1][k-cnt];
break;
}
}
if (cnt==k) ans++;
return ans;
}
int main(){
ios::sync_with_stdio(false);
init();int x,y;
cin>>x>>y>>k>>b;
cout<