引入

数位是指把一个数字按照个、十、百、千等等一位一位地拆开，关注它每一位上的数字。如果拆的是十进制数，那么每一位数字都是 0~9，其他进制可类比十进制。

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

要求统计满足一定条件的数的数量（即，最终目的为计数）；
这些条件经过转化后可以使用「数位」的思想去理解和判断；
输入会提供一个数字区间（有时也只提供上界）来作为统计的限制；
上界很大（比如 10^18），暴力枚举验证会超时。

数位 DP 的基本原理

考虑人类计数的方式，最朴素的计数就是从小到大开始依次加一。但我们发现对于位数比较多的数，这样的过程中有许多重复的部分。例如，从 7000 数到 7999、从 8000 数到 8999、和从 9000 数到 9999 的过程非常相似，它们都是后三位从 000 变到 999，不一样的地方只有千位这一位，所以我们可以把这些过程归并起来，将这些过程中产生的计数答案也都存在一个通用的数组里。此数组根据题目具体要求设置状态，用递推或 DP 的方式进行状态转移。

数位 DP 中通常会利用常规计数问题技巧，比如把一个区间内的答案拆成两部分相减。

那么有了通用答案数组，接下来就是统计答案。统计答案可以选择记忆化搜索，也可以选择循环迭代递推。为了不重不漏地统计所有不超过上限的答案，要从高到低枚举每一位，再考虑每一位都可以填哪些数字，最后利用通用答案数组统计答案。

典型例题

数字计数

using LL = long long;

const int N = 15;
LL dp[N], ten[N];
LL ans1[N], ans2[N];
LL a[N];

void solve(LL n, LL* ans) {
    LL temp = n;
    int len = 0;
    while (n) a[++len] = n % 10, n /= 10;
    for (int i = len; i >= 1; i--) {
        for (int j = 0; j < 10; j++) ans[j] += dp[i - 1] * a[i];
        for (int j = 0; j < a[i]; j++) ans[j] += ten[i - 1];
        temp -= ten[i - 1] * a[i];
        ans[a[i]] += temp + 1;
        ans[0] -= ten[i - 1];
    }
}

int main() {
    LL l, r;
    cin >> l >> r;
    ten[0] = 1;
    for (int i = 1; i <= 13; i++) {
        dp[i] = dp[i - 1] * 10 + ten[i - 1];
        ten[i] = ten[i - 1] * 10;
    }
    solve(l - 1, ans1);
    solve(r, ans2);
    for (int i = 0; i < 10; i++) cout << ans2[i] - ans1[i] << " ";
}