数位dp

简单写写

引入

思考以下问题：
对于给定范围的整数 $x \in [a,b]$ ，有多少个 $x$ 满足性质 $p$ （ $p$ 与数的各个位都有关，如“该数中有3个1”）。
对于此类问题，我们可以考虑如下方法：

1. 用 $f[i]$ 表示对于所有的整数 $x \in [0,i]$ 中，满足性质 $p$ 的数的个数

2. 则 $ans \ge f[b]-f[a-1]$

那么，我们来考虑如何去求 $f[N]$ 。

分析

设数 $N$ 是一个 $n$ 位数，且 $N=\overline{a_{n-1}a_{n-2}a_{n-3}…a_0} (a_
{n-1} \ne 0)$ 。
辣么，对于 $\forall x \in [0,N],x=\overline{b_{n-1}b_{n-2}b_{n-3}…b_0}$ ，有两种情况：

1. $b_{n-1}=a_{n-1}$

2. $0 \le b_{n-1} < a_{n-1}$

我们发现，对于第二种情况，当 $b_{n-1}$ 确定时，方案数可以直接计算。如当 $N=7654321$ ， $p$ 为“该数中有3个1” 时，若 $0 \le b_6 < 7$ 那么 $b_6=1$ 时，有 $C_{6}^{2}$ 种方案，而当 $b_6 \ne 1$ 时，有 $C_{6}^{3}$ 种方案。
对于第一种情况，我们只需继续讨论 $b_{n-2}$ 。
如图：

例题

代码如下：

#include <bits/stdc++.h>
using namespace std;
const int N = 35;
int k, B; //B进制数
int C[N][N];
//预处理组合数
void init()
{
    for (int i = 0; i < N; ++i)
        for (int j = 0; j <= i; ++j)
            if (!j)
                C[i][j] = 1;
            else
                C[i][j] = C[i - 1][j] + C[i - 1][j - 1];
}
//计算0到n中的数
int dp(int n)
{
    if (!n)
        return 0;
    vector<int> nums;
    while (n)
        nums.push_back(n % B), n /= B;

    int res = 0;
    int last = 0;
    for (int i = nums.size() - 1; i >= 0; --i)
    {
        int x = nums[i];
        //求左边分支
        if (x)
        {
            res += C[i][k - last];
            if (x > 1)
            {
                if (k > last)
                    res += C[i][k - last - 1];
                break;
            }
            else
            {
                last++;
                if (last > k)
                    break;
            }
        }
        //加上最右侧分支上的方案
        if (!i && last == k)
            res++;
    }
    return res;
}
int main()
{
    init();
    int l, r;
    cin >> l >> r >> k >> B;
    cout << dp(r) - dp(l - 1) << endl;
    return 0;
}