【数位DP】洛谷P2602 [ZJOI2010]题解分析

一、题目描述

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

二、算法分析

1、文字解释

参考了OI Wiki的解释：

发现对于满 $i$ 位的数，所有数字出现的次数都是相同的，故设数组 ${dp}_i$ 为满 i 位的数中每个数字出现的次数，此时暂时不处理前导零。则有 ${dp}_i=10\times {dp}_{i?1}+10^{i?1}$，这两部分前一个是来自前 $i?1$ 位数字的贡献，后一个是来自第 $i$ 位的数字的贡献。

有了 $dp$ 数组，我们来考虑如何统计答案。将上界按位分开，从高到低枚举，不贴着上界时，后面可以随便取值。贴着上界时，后面就只能取 $0$ 到上界，分两部分分别计算贡献。最后考虑下前导零，第 $i$ 位为前导 $0$ 时，此时 $1$ 到 $i?1$ 位也都是 $0$，也就是多算了将 $i?1$ 位填满的答案，需要额外减去。

重点理解${dp}_i$的含义

2、代码块分析(以12345外循环i=len为例，后面同理）

以下计数分为两部分：
1、最高位计数
2、非最高位计数

将12345按位存到数组

while (n) a[++len] = n % 10, n /= 10;

计算非最高位（即后4位）0-9出现次数（不包含1****）

for (int j = 0; j < 10; j++) ans[j] += dp[i - 1] * a[i];

计算最高位的所有可能数的个数，仅0****

for (int j = 0; j < a[i]; j++) ans[j] += mi[i - 1];

最高位1****出现次数另算，为12345-10000+1=2346

tmp -= mi[i - 1] * a[i], ans[a[i]] += tmp + 1;

最高位为0时（0****）位数不满，0不能作为计数，需要减去

ans[0] -= mi[i - 1];

初始准备。计算满位时非最高位次数和第高位次数（详见文字解释）

for (int i = 1; i <= 13; ++i) {
    dp[i] = dp[i - 1] * 10 + mi[i - 1];
    mi[i] = 10ll * mi[i - 1];
}

本文主要是为了记录解决我当初不理解的一个问题：

1、对于12345，第一层外循环i=len时仅处理了10000内的数，而剩余的2345没有处理。尽管下一循环着手处理2了，也依旧没有完全处理边界数12345，那么题目是怎么解出来的呢？
2、处理12345的2345和处理的2345这两个会有重复吗？

我草草画了一张图，接下来围绕这个图来解答上述问题。

循环次数	i	主要执行操作
①	5（len）	统计$[0,10000]$内的数的0-9出现次数
②	4	统计$[0,2000]$内的数的0-9出现次数
③	3	统计$[0,300]$内的数的0-9出现次数
④	2	统计$[0,40]$内的数的0-9出现次数
⑤	1	统计$[0,5]$内的数的0-9出现次数

①解决$[0,10000]$内的数的统计，计算了2345+1个最高位1的次数，剩余12345-10000=2345没有统计

②解决$[0,2000]$内的数的统计，计算了345+1个最高位2的次数，剩余2345-2000=345没有统计

③解决$[0,300]$内的数的统计，计算了45+1个最高位3的次数，剩余345-300=45没有统计

④解决$[0,40]$内的数的统计，计算了5+1个最高位4的次数，剩余45-40=5没有统计

⑤解决$[0,5]$内的数的统计，计算了1个最高位5的次数，完成统计

从上述过程中我们可以发现并不会重复计数，计数的范围越来越小，就像一串十进制数，每次循环减少一个最高位。

三、参考代码

#include <bits/stdc++.h>
using namespace std;
const int N = 15;
typedef long long ll;
ll l, r, dp[N], mi[N];
ll ans1[N], ans2[N];
int a[N];

void solve(ll n, ll *ans) {
  ll tmp = 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] += mi[i - 1];
    tmp -= mi[i - 1] * a[i], ans[a[i]] += tmp + 1;
    ans[0] -= mi[i - 1];
  }
}
int main() {
  scanf("%lld%lld", &l, &r);
  mi[0] = 1ll;
  for (int i = 1; i <= 13; ++i) {
    dp[i] = dp[i - 1] * 10 + mi[i - 1];
    mi[i] = 10ll * mi[i - 1];
  }
  solve(r, ans1), solve(l - 1, ans2);
  for (int i = 0; i < 10; ++i) 
    printf("%lld ", ans1[i] - ans2[i]);
  return 0;
}

---

参考来源：
1、洛谷P2602 [ZJOI2010]
2、OI Wiki 数位 DP

---

本文入有描述不当之处还请指点一二