AcWing 1081. 度的数量
原题链接
中等
作者:
最后五分钟
,
2023-08-06 03:09:20
,
所有人可见
,
阅读 62
#include<bits/stdc++.h>
using namespace std;
const int N=34;
int c[N][N],k,b;
void init()
{
for(int i=0;i<N;i++)
for(int j=0;j<=i;j++)
if(!j)c[i][j]=1;
else c[i][j]=c[i-1][j-1]+c[i-1][j];
}
int dp(int x)
{
//if(!x)return 0;
int res=0;
int ls=0;
vector<int> nums;
while(x)nums.push_back(x%b),x/=b;
for(int i=nums.size()-1;~i;i--)
{
int t=nums[i];
if(t)
{
res+=c[i][k-ls];
if(t>1)
{
res+=c[i][k-ls-1];
break;
}
ls++;
if(k-ls<0)break;
}
if(!i&&k==ls)res++;
}
return res;
}
int main()
{
int x,y;
cin>>x>>y>>k>>b;
init();
int ans=dp(y)-dp(x-1);
cout<<ans<<endl;
return 0;
}