AcWing 1081. 度的数量
原题链接
中等
作者:
知恩海
,
2023-11-02 15:25:44
,
所有人可见
,
阅读 63
#include<bits/stdc++.h>
using namespace std;
const int N = 50 ;
int f[N][11][50];
int a,b,K,B;
int C[N][N];
void zuhe(){
for(int i = 0;i<=N;i++){
for(int j = 0 ; j <= N ; j++){
if(!j) C[i][j] = 1;
else C[i][j] = C[i-1][j-1] + C[i-1][j];
}
}
}
void init(){
for(int k=0;k<=20;k++){
for(int i=1;i<N-5;i++){
f[i][0][k] = C[i-1][k];
if(k-1<0) f[i][1][k] = 0;
else f[i][1][k] = C[i-1][k-1];
}
}
}
int dp(int n)
{
vector<int>nums;
while(n)nums.push_back(n%B),n/=B;
int res = 0;
int cnt = 0;
for(int i = nums.size()-1;i>=0;i--){
int x = nums[i];
// cout << "x: " <<x<<endl;
// cout << "res: " << res;
for(int j= i==nums.size()-1 ; j<x ; j++){
res += f[i+1][j][K-cnt];//记得=位数继承下来的时候 选的数量也不一样
}
// cout << " -> " <<res<<endl;
if(x > 1||cnt>K)
break;
if(x==1)cnt++;
if(i==0&&cnt == K)res++;
}
for(int i = nums.size()-2;i>=0;i--){//记得从次一位开始加
// for(int j=1;j<B;j++){//这里就不要考虑j=0了因为f[i][j] 里面j为0时是为了前面有数的时候准备的
// res += f[i+1][j];
// }
res += f[i+1][1][K];//所以直接变成 j=1
}
return res;
}
int main()
{
cin >> a >> b >> K >> B;
zuhe();
init();
cout << dp(b) - dp(a-1);
// cout << dp(14);
// cout << C[0][-1];
return 0;
}