灵神模版,细节很多
/*
样例分析:k=2,b=2
满足题意的数字
17 = 0001,0001
18 = 0001,0010
20 = 0001,0100
其余数字
19 = 0001,0011 至少三个整次幂
总结:转换成 b 进制后的数,只能包含 0 和 1,答案是其中有 k 个 1 的数的个数
*/
#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
const int N = 32;
int x, y, k, B;
vector<int> a, b;
int memo[N][N];
int dfs(vector<int>& s, int i, int cnt, bool is_limit, bool is_num) {
if (i == s.size()) {
return cnt == k;
}
if (!is_limit && is_num && memo[i][cnt] != -1) return memo[i][cnt];
int res = 0;
if (!is_num) {
res += dfs(s, i+1, cnt, false, false);
}
int low = is_num ? 0 : 1;
// 由于每一位只能选 0 或者 1
// 那么有限制时就要 min(1, s[i]) 没限制就无脑 1
int up = is_limit ? min(1, s[i]) : 1;
for (int j = low; j <= up; j++) {
// 注意接下来有限制的条件应该是 is_limit && j == s[i]
// 不能使用 up 因为 up(取值 0 或者 1) 不一定是 s[i] 或者 9
res += dfs(s, i+1, cnt + (j == 1), is_limit && j == s[i], true);
}
if (!is_limit && is_num) memo[i][cnt] = res;
return res;
}
int main() {
cin >> x >> y >> k >> B;
x--;
while (x) {
a.push_back(x % B);
x /= B;
}
reverse(a.begin(), a.end());
// for (int x: a) cout << x << " ";
// cout << endl;
while (y) {
b.push_back(y % B);
y /= B;
}
reverse(b.begin(), b.end());
// for (int x: b) cout << x << " ";
// cout << endl;
memset(memo, -1, sizeof memo);
int r1 = dfs(a, 0, 0, true, false);
memset(memo, -1, sizeof memo);
int r2 = dfs(b, 0, 0, true, false);
// cout << "r2: " << r2 << " r1: " << r1 << endl;
cout << r2 - r1;
return 0;
}