洛谷P2602 [ZJOI2010] 数字计数 题解 & 数位dp 模板

题目链接：P2602 [ZJOI2010] 数字计数

题意：

给定两个正整数 \(l\) 和 \(r\)，求在 \([l,r]\) 中的所有整数中，每个数码(digit)各出现了多少次。

输入格式：

仅包含一行两个整数 \(l,r\)，含义如上所述。

输出格式：

包含一行十个整数，分别表示 \(0\sim 9\) 在 \([l,r]\) 中出现了多少次。

数据范围：

保证 \(1\le l\le r\le 10^{12}\)。

本题是 数位dp 的模板题（鉴于本人竟然没有数位dp的板子）

设 \(f(i,j)\) 表示（从低到高）考虑到第 \(i\) 位，当前枚举的数码 \(d\) 出现了 \(j\)​ 次时的方案数

这样设计的好处在于边界是 \(f(0,j)=j\) ，可以很方便的得到答案，而且状态数很少，只有 \(12 \times 12\) 。

数位dp一般使用记忆化搜索，复杂度一般等于 \(\mathcal{O}\left(\texttt{状态数}\right)\)​ 乘上一个小常数（没人会卡这个常数的）

代码：（内有丰富注释，开心吧）

// 2024年05月29日 17:29:00
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)())

int tot, num[25], f[20][20][2][2];
// u 表示当前位, st(states) 表示需要特别记录的状态（本题中是当前数码的出现个数）
// d 表示当前考察的数码, limit 表示下一位是否有最高位限制, qd0 表示是否允许前导0
int dfs(int u, int st, int d, bool limit, bool qd0)
{
    if(!u) return st;
    if(~f[u][st][limit][qd0]) return f[u][st][limit][qd0];
    int sum = 0, up = limit ? num[u] : 9; // 例如 12999 <= 14567 的后三位可以枚举到 9
    for(int i = 0; i <= up; i++)
    {
        if(qd0 && !i) sum += dfs(u - 1, st, d, limit && i == up, 1); // 前导0不影响st
        else sum += dfs(u - 1, st + (i == d), d, limit && i == up, 0);
    }
    return f[u][st][limit][qd0] = sum;
}
int solve(int x, int d)
{
    tot = 0; memset(f, -1, sizeof(f));
    while(x) { num[++tot] = x % 10, x /= 10; }
    return dfs(tot, 0, d, 1, 1);
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    int l, r; cin >> l >> r; // [l, r] 的答案可以用 [0, r] 的答案减去 [0, l - 1] 的答案得到
    for(int i = 0; i <= 9; i++) cout << solve(r, i) - solve(l - 1, i) << " \n"[i == 9];
    return 0;
}

---

参考文献：

[1] https://www.luogu.com.cn/article/n0yqd8h9