AcWing 1081. 度的数量
原题链接
中等
作者:
wangyj
,
2021-01-21 08:43:08
,
所有人可见
,
阅读 249
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
int K,B,f[35][35];
int dp(int n)
{
if(!n)return 0;
vector<int>num;
while(n)num.push_back(n%B),n/=B;
int ans=0,end=0,i,x;
for(i=num.size()-1;i>=0;i--){
x=num[i];
if(x){
ans+=f[i][K-end];
if(x>1){
if(K-end-1>=0)ans+=f[i][K-end-1];
break;
}
else{
end++;
if(end>K)break;
}
}
if(!i&&end==K)ans++;
}
return ans;
}
int main()
{
int i,j,l,r;
for(i=0;i<35;i++)for(j=0;j<=i;j++)if(!j)f[i][j]=1;else f[i][j]=f[i-1][j]+f[i-1][j-1];
scanf("%d%d%d%d",&l,&r,&K,&B);
printf("%d\n",dp(r)-dp(l-1));
return 0;
}