$\LARGE\color{orange}{刷题日记(算法提高课)}$

碎碎念：数位DP，这玩意是大爹，真的是大爹，看都看不懂的那种呜呜呜

下面我们先给出一般数位 DP 的思考过程：

我们先给出「限定值」的定义：某个数位上的最大取值为限定值

对于给定的数 $N$ ，该数有 $n$ 位，其位表示为：$a_{n-1}a_{n-2}\cdots a_{1}a_{0}$

我们从大到小遍历每一位，有：

对于第 $n-1$ 位，限定值为 $a_{n-1}$ ，取值的可能性分两类：不取限定值与取限定值

• 不取限定值，那么取值的范围可以是 $0\sim a_{n-1}-1$ ，这种情况下的数的个数可以直接计算

• 取限定值，那么只能是 $a_{n-1}$ ，这种情况下我们需要进一步考虑第 $n-2$ 位

对于第 $n-2$ 位，限定值为 $a_{n-2}$ 并且此时第 $n-1$ 位为 $a_{n-1}$ ，取值同样分为两类：取限定值和不取限定值

• 不取限定值，第 $n-2$ 位的取值可以是 $0\sim a_{n-2}-1$ ，此时第 $n-1$ 位的取值为 $a_{n-1}$ ，我们在此基础上可以计算出此种情况的数的个数

• 取限定值，那么只能取 $a_{n-2}$ ，因此我们需要进一步考虑第 $n-3$ 位

以此类推，整个是一个树的思考过程

需要注意的是，我们在循环的过程中可以处理掉除最后一位的所有情况，因此最后一位需要特殊判断

而最后一位实际上就是这个数本身，只需要判断这个数本身十分满足条件即可

数位 DP 实际上就是求一个范围内满足条件的数条件的数的个数，本质上还是计数问题

回到本题，我们需要求出区间 $[X,Y]$ 中符合题意的数的个数，考虑前缀和的思想，设 $dp(x)$ 为区间 $[0,x]$ 中符合题意的数的个数，那么 $dp([X,Y])=dp(Y)-dp(X-1)$

题目需要求 $K$ 个互不相等的 $B$ 的整数次幂之和的数的个数

意思就是，在 $B$ 进制表示下，这个数只包含 0 和 1 且 1 的个数恰好为 $K$

对于给定的数 $N$ ，我们先将其转为 $B$ 进制表示，然后从最高位开始枚举，此时不外乎三种情况：

i 为当前枚举到的数，last 为 i 前面已经使用了的 1 的个数

• 限定值为 0 ，只要不是最后一位，我们进入下一位，因为这一位没办法填数

• 限定值为 1 ，这一位既可以填 0 也可以填 1

对于填 0 的情况，往后的 $i$ 个数一共填了 $K-last$ 个 1 ，即求组合数 $C_{i}^{K-last}$

对于填 1 的情况，相当于填了限定值本身，也就是 $last$ 会加一，之后进行下一位

• 限定值大于 1，这一位只能填 0 或者 1 ，并且不需要再进入下一位了（因为满足条件的数不会出现 0 和 1 以外的数，到此为止我们可以直接跳出循环了）

对于填 0 的情况，往后的 $i$ 个数一共填了 $K-last$ 个 1 ，即求组合数 $C_{i}^{K-last}$

对于填 1 的情况，往后的 $i$ 个数一共填了 $K-last-1$ 个 1，即求组合数 $C_{i}^{K-last-1}$

对于组合数的求法，我们用 $C_{a}^{b}=C_{a-1}^{b-1}+C_{a-1}^{b}$ 预处理出来所有的组合数即可

完整代码：

#include <iostream>
#include <cstring>
#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];
}
int dp(int n)
{
    if(!n) return 0;
    int res = 0, last = 0;
    vector<int>nums;
    while(n) nums.push_back(n % B), n /= B;
    for(int i = nums.size() - 1; i >= 0; i--)//倒着存的，因此需要反过来遍历
    {
        int x = nums[i];
        if(x > 0)//限定值为0的情况，除了最后一位都需要跳过
        {
            res += f[i][K - last];//该位填0
            if(x > 1)//限定值大于1
            {
                if(K - last - 1 >= 0) res += f[i][K - last - 1];//当前位填1，后面的i位一共填K-last-1个1的方案数
                //由于每个数只能由0和1组成，导致这一位不能填大于1的数，因此我们计算完之后就需要直接跳出
                break;
            }
            else//限定值为1
            {
                last++;//x == 1，我们已经算过当前位填0的情况了，另一种情况我们直接让last加一然后进入下一位
                if(last > K) break;
            }
        }
        //枚举到最后一位，如果前面已经满足了1的个数，那么最后一位允许为 0
        //允许为 0 是因为这已经是最后一位了，没有办法在退后
        if(i == 0 && K == last) res++;
    }
    return res;
}
int main()
{
    init();
    int l, r;
    cin >> l >> r >> K >> B;
    cout << dp(r) - dp(l - 1) << endl;
    return 0;
}