一、数位DP基础知识
数位\(dp\)的题目一般会问，某个区间内，满足某种性质的数的个数。
对应的数位\(dp\)问题有相应的解题技巧：
-
利用前缀和，比如求区间\([x,y]\)中的个数，转化成求\([0,y]\)的个数 -\([0,x-1]\)的个数
-
利用树的结构来考虑（按位分类讨论）
何时能用 记忆化搜索 优化掉当前搜索分支
当当前 数位 能够枚举集合内所有元素的时候（没有贴着上界），即 !op
二、解题思路
题目就是在一个区间\([x,y]\)内，找出有多少个符合题意的数，这里的符合题意是指：这个数的\(B\)进制表示中，其中有\(K\)个位置上是\(1\)、其他位上全是\(0\)。
比如样例中\(B=2\)，\(K=2\)，这个数是\(18\).就是把18化为二进制，\(18\) 化为二进制数为：\(10010\)，其中有\(2\)位\(1\)，其他位都是\(0\)
再比如 \(B=3\)，\(K=2\)，这个数是\(12\).就是把\(12\)化为三进制，\(12\)化为三进制为\(110\) ，其中也有\(2\)个\(1\)，其余都是\(0\).
该类题目的核心就是根据数位进行分类讨论。
第一步
先将数\(x\)转化成为\(B\)进制，记为\(N\)。
//这是一段将n转化为B进制的代码
//输入：n 和进制B
#include<bits/stdc++.h>
using namespace std;
int main(){
int n,B;
cin >> n >> B;
vector<int> a;
while(n) a.push_back( n % B) , n /= B;
for(int i = a.size()-1; i>= 0; i--) cout<< a[i]<<" ";
}
第二步
数位DP，还是背模板来的快，提高课的数位DP讲解的东西太不好想了，也容易遗漏分枝，感觉\(dfs\)模板大法才是正解：
#include <bits/stdc++.h>
using namespace std;
const int N = 32; //输入的数据范围2^31-1,也就是整数上界。2进制是最小的进制，32也够了
int l, r, k, b;
int a[N], al;
int f[N][N]; //f[i][j] i:枚举到的位置 j:标记是1的个数
/**
*
* @param pos 当前枚举到的数位
* @param st 数字1出现了几次
* @param op 是否贴上界
* @return 在当前情况下，它“后面”符合条件的一共有多少个数
*/
int dp(int pos, int st, int op) {
//枚举到最后一位数位，是否恰有k个不同的1（也是递归的终止条件）
if (!pos) return st == k;
//记忆化搜索，前提是不贴着上界（可以枚举满这一位所有的数字）
if (!op && ~f[pos][st]) return f[pos][st];
//01数位dp，贴着上界时，本轮能枚举的最大数就是上界数位的数字和1之间的最小值
int res = 0, up = op ? min(a[pos], 1) : 1;
for (int i = 0; i <= up; i++) { //讨论每个后续可能，分拆的过程
//剪枝，其实不剪枝也一样能过
if (st + i > k) continue; //出现的次数+ （0 或者 1） > k
//累加后面所有的可能个数。合并的过程
res += dp(pos - 1, st + i, op && i == a[pos]);
}
//模板，只记录不受上限限制的个数，受上限限制的每次重新计算
return op ? res : f[pos][st] = res;
}
int calc(int x) {
al = 0;
memset(f, -1, sizeof f); //模板的必要初始化步骤
while (x) a[++al] = x % b, x /= b; //把x按照进制分解到数组中,下标从1开始
return dp(al, 0, 1);
}
int main() {
cin >> l >> r >> k >> b;
cout << calc(r) - calc(l - 1) << endl;
return 0;
}