1.定义与原理
2.例题一：
题目
思路
我们做数位 \(DP\) 时，一般有如下两个技巧方便做题，理清思路：
-
1.对于求一段数中满足条件的数的个数，可以用前缀和的方法完成，即 $ans=dp (r)-dp(l-1) $；
-
2.在想思路时，可以把问题转换成 树 的形式，对每个步骤分情况讨论，下面拿这道题来举例子：
首先分析样例，把 \(15\) 到 \(20\) 中的所有数转化为二进制：
\(15=1111,16=10000,17=10001,18=10010,19=10011,20=10100\)
总结规律，得出结论，问题转化为：从 \(l\) 到 \(r\) 中所有数的 \(b\) 进制中恰好有 \(k\) 个 \(1\) 的数的个数。
那么我们结合这张图具体分析：
我们令一个 \(N\) 位数，其每一位为 \(a_{(n-1)},a_{(n-2)}...a_{0}\)，然后我们把每一位竖着写好，在从高到低对每一位分情况讨论。
比如我们对 \(a_{(n-1)}\) 讨论，因为这是个 \(N\) 进制数，所以其每一位都小于 \(N\)。
然后我们分出两种情况：小于 \(a_{(n-1)}\) 和等于 \(a_{(n-1)}\)。
比如这个数为 \(76543210\)，我们取第一位时可以取 \(0\) 到 \(6\) 之间的任何数，也可以取 \(7\)。
-
1.当取 \(0\) 到 \(6\) 时，又分为取非 \(1\) 和取 \(1\) 两种情况。当取的数不是 \(1\) 时，意味着我们将在剩下的 \(N-1\) 个数中填 \(k\) 个 \(1\)，总方案数为 \(C_{N-1}^{k}\)；否则，说明已经填入了一个 \(1\)，总方案数为 \(C_{N-1}^{k-1}\)。
-
2.当取的数为 \(7\) 时，说明这一位已经被固定，于是我们继续用同样思路推下一位即可。
最后，当我们推到 \(a_0\) 时，同样分两种情况，但此时已经不能再往下分支了，所以最后的答案就是图中所有左边的分支和 \(a_0\) 这一块。
代码
#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
// #define int long long
using namespace std;
#define N 1010
#define For(i,j,k) for(int i=j;i<=k;i++)
#define IOS ios::sync_with_stdio(0),cin.tie(),cout.tie()
int l, r, k, b;
int c[N][N];
void init () {
For (i, 0, N - 1) {
For (j, 0, i) {
if (j == 0) c[i][j] = 1;
else c[i][j] = c[i - 1][j] + c[i - 1][j - 1];
}
} //初始化组合数
}
int dp (int n) {
if (n == 0) return 0; //特判边界
vector <int> nums;
while (n) nums.push_back (n % b), n /= b; //将n转化成b进制数
int res = 0, lst = 0; //前面是模板
//res是答案，lst是计算右分支时的前缀信息(已经填好的数中1的个数)
for (int i = nums.size () - 1; i >= 0; i --) { //倒序循环，因为进制转换时存的数是倒序的
int x = nums[i];
if (x) { //只有x>0时才有左右分支
res += c[i][k - lst]; //首先肯定可以填0,，就在剩下i位中填k-lst个数
if (x > 1) { //如果可以取1,那就假设取的就是1
if (k - lst - 1 >= 0) res += c[i][k - lst - 1];
//还需取1的个数减1，记得判断一下是否还能再取
//因为对于右边分支取的就是x本身（x>1），所以不合法，直接break！
break;
} else { //当x==1时，只能取0，所以交给下一位，下一位可使用的1的个数会少1，体现在代码上是last+1
lst ++;
if (lst > k) break; //如果已经填了k个1，就退出
}
}
if (i == 0 && lst == k) { //最右侧分支上的方案
res ++;
} //如果算到最后一位且已经填了k个1，就退出
}
// cout << endl;
return res;
}
int main () {
IOS;
init ();
cin >> l >> r >> k >> b;
cout << dp (r) - dp (l - 1) << endl; //前缀和思想
return 0;
}