最近在补全提高课所有题目的题解，宣传一下汇总的地方提高课题解补全计划

参考文献：

1. OiWiki - 数位DP ( 2021/8/19 12:33:29 更新的最新篇章，之前该板块几乎为空，今天找资料的时候发现居然更新了)
2. 数位DP笔记(DFS做法) - 风总 (写的很棒，非常推荐，前人栽树，我来 洗稿 乘凉～)

数位DP基本概念

数位：把一个数字按照个、十、百、千等等一位一位地拆开，关注它每一位上的数字。

如果拆的是 十进制数，那么每一位数字都是 $0$ ~ $9$，其他进制可 类比 十进制。

数位 DP：用来解决一类特定问题，这种问题比较好辨认，一般具有这几个特征：

• 要求统计满足一定条件的数的数量（即，最终目的为计数）

• 这些条件经过转化后可以使用「数位」的思想去理解和判断

• 输入会提供一个数字区间（有时也只提供上界）来作为统计的限制

• 上界很大（比如 $10^9$），暴力枚举验证会超时

从题目中分析出 数位DP 的模型后，做法就非常的 套路化 了

题目要求 一段区间 内符合某些条件的数的个数，我们用 前缀和思想 转换为求两个 前缀区间 的问题

$$ res[l,r] = res[1,r] - res[1,l-1] $$

接下来的问题就是统计答案。

统计答案可以选择 记忆化搜索，也可以选择 循环迭代递推。

为了不重不漏地统计所有不超过上限的答案，要 从高到低 枚举每一位

再考虑每一位都可以 填哪些数字，最后利用上述 前缀和思想 统计答案

记忆化搜索 中要引入的参数通常有：

1. 当前枚举到的数位 $pos$ （搜索的深度）
2. 前一位数（或是前几位数）的情况 $st$ （诸如 前一位是什么、前几位总和是多少、某个数出现了几次 等）
3. 前几位的数字是否等于上界的前几位数字 $op~(0/1)$（限制本次搜索的数位范围）
4. 是否有前导零 $lead~(0/1)$

记忆化搜索的 递归搜索树 y总已经画过了，这里就不再额外绘制（本身也不复杂，就留给读者了）

循环迭代递推 的方法，大家可以看 y总 的 算法提高课 以及 lyd 的 蓝书 上的介绍

何时能用 记忆化搜索 优化掉当前搜索分支

当当前 数位 能够枚举集合内所有元素的时候（没有贴着上界），即 !op

题目描述

求给定区间 $[L, R]$ 中满足：这个数恰好等于 $K$ 个互不相等的 $B$ 的整数次幂之和

分析

题目中有明确暗示，是一个 $B$ 进制的 数位问题（每个整数次幂位数的数字选择）

题目中还要求 恰好有 $K$ 个 互不相等 的 $B$ 的整数次幂之和

故对于该 $B$ 进制的数字来说，每一位数要么填 $0$，要么填 $1$，且填 $1$ 的位数个数 恰好等于 $K$

那么本题就是一个 01数位DP问题，接下来就是套模板时间

模板中的 $st$ 在本题里要记录的 参数 就是，前几位中，填 $1$ 的个数

Code（记忆化搜索）

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 35;

int l, r, k, b;
int a[N], al;
int f[N][N];

int dp(int pos, int st, int op) //op: 1=,0<
{
    //枚举到最后一位数位，是否恰有k个不同的1（也是递归的终止条件）
    if (!pos) return st == k;
    //记忆化搜索，前提是不贴着上界（可以枚举满这一位所有的数字）
    if (!op && ~f[pos][st]) return f[pos][st];
    //01数位dp，贴着上界时，本轮能枚举的最大数就是上界数位的数字和1之间的最小值
    int res = 0, maxx = op ? min(a[pos], 1) : 1;
    for (int i = 0; i <= maxx; i ++ )
    {
        if (st + i > k) continue;
        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按照进制分解到数组中
    return dp(al, 0, 1);
}
int main()
{
    cin >> l >> r >> k >> b;
    cout << calc(r) - calc(l - 1) << endl;
    return 0;
}

Code（循环迭代递推）

见y总视频，或者蓝书