题目描述
Solution with Some notes in the lecture
C++ 代码
#include<iostream>
#include<vector>
using namespace std;
const int N = 35;
int f[N][N];
int K,B;
void init(){
for(int i=0; i < N; ++i) {
for(int j =0; j<=i; ++j) {
if(j == 0) f[i][j] = 1;
else f[i][j] = f[i-1][j-1] + f[i-1][j];
}
}
return;
}
int dp(int num_x){
if(num_x == 0) return 0;
vector<int> num;
while(num_x){
num.emplace_back(num_x %B);
num_x /= B;
}
int res = 0;
int last = 0;
for(int i=num.size()-1; i>=0; --i) {
int x = num[i];
if(x>0){
//not select 1
res += f[i][K-last];
if(x >1){
// select 1
if(K-last-1>=0) res += f[i][K-last-1];
// this case it is impossible for us to go to the right branch anymore break here.
break;
// hit x==1, come to the right branch
}else {
last++;
if(last > K) break;
}
}
// we calcualte the whole right branch together
if(i==0 && last == K) res ++;
}
return res;
};
int main () {
int l, r;
cin >> l >> r;
cin >> K >> B;
init();
cout << dp(r) - dp(l-1) << endl;
return 0;
}
编译错误什么鬼?
不会吧。你是不是拷贝后,没有把最后几行的中文删除呢。