数位 \(dp\) 大多使用高位计算的时候使用低位计算后的结果，从而做到优化效率
[ZJOI2010] 数字计数
题目描述
给定两个正整数 \(a\) 和 \(b\)，求在 \([a,b]\) 中的所有整数中，每个数码各出现了多少次。
- 保证 \(1\le a\le b\le 10^{12}\)。
求解策略
第一种方法 - 递推法
定义 \(dp_i\) 为 \(i\) 位数中，每种数字出现的次数，这里我们每种数字出现的次数都是相同的，随便用一个数字即可
- 一位数 \(0\) ~ \(9\)，每种数字只有 \(dp_1 = 1\) 个
- 两位数 \(00\) ~ \(99\)，每种数字有 \(dp_2 = 20\) 个，这里是 \(00\) 而不是 \(0\)，实际上是不合法的，但是先按照统一处理，到后面会减去
- 三位数 \(000\) ~ \(999\)，每种数字有 \(dp_3 = 300\) 个
那么 \(dp[]\) 有两种计算方法，分别是递推和数学组合
- \(dp_i\) = \(dp_{i - 1} * 10 + 10^{i-1}\)。以数字 \(2\) 为例，计算 \(dp_2\) 的时候，\(2\) 在个位上出现了 \(dp_{i-1} * 10 = dp_1 * 10 = 10\) 次，即 \(2,12,22,...,92\)。那么十位出现了 $10^{i-1} = 10 $ 次，即 \(21,22,23,...29\)。以此类推即可
- \(dp_i = \frac {i * 10^i}{10}\)，从 \(i\) 个 \(0\) 递增到 \(i\) 个 \(9\)，所有的字符共出现了 \(i * 10 ^ i\) 次，\(0\) ~ \(9\) 每个数字出现了 \(\frac {i * 10^i}{10}\) 次
那么考虑如何实现，我们以 \(0\) ~ \(324\) 为例，设 \(cnt\) 为答案，\(num_i\) 为 \(i\) 位上的数字:
- 对于普通情况，也就是符合 \(00\) ~ \(99\) 的情况，先拆分成 \(000\) ~ \(099\)，\(100\) ~ \(199\)，\(200\) ~ \(299\)，这些的后两位是符合普通情况的，我们直接使用 \(cnt_{0..9} = dp_{i-1} * num[i]\) 统计
- 对于最高位，我们需要特殊判断，首先看 \(0\) ~ \(num_i - 1\) 的这些数字，他们都对应着所有的 \(00\) ~ \(99\) 这 \(10^{i-1}\) 个数字，所以对于这些最高位，都有 \(cnt_{0..num_i-1} += 10^{i-1}\)。对于 \(3\) 来说，对应的只有 \(00\) ~ \(24\) 这 \(25\) 个，特殊处理即可，最后我们要把最高位为 \(0\) 的处理掉，也就是 \(cnt_0 -= 10^{i-1}\)
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 15, mod = 1e9 + 7;
int dp[N], ten[N], num[N];
void init(){
ten[0] = 1;
for(int i = 1; i <= N; i++){
dp[i] = i * ten[i - 1];
ten[i] = ten[i - 1] * 10;
}
}
vector<int> make(int x){
int len = 0;
while(x){
num[++len] = x % 10, x /= 10;
}
vector<int> cnt(N);
for(int i = len; i >= 1; i--){
for(int j = 0; j <= 9; j++){
cnt[j] += num[i] * dp[i - 1];
}
for(int j = 0; j < num[i]; j++){
cnt[j] += ten[i - 1];
}
int num2 = 0;
for(int j = i - 1; j >= 1; j--) num2 = num2 * 10 + num[j];
cnt[num[i]] += num2 + 1;
cnt[0] -= ten[i - 1];
}
return cnt;
}
signed main()
{
std::ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
int a, b; cin >> a >> b;
init();
vector<int> ans1 = make(a - 1), ans2 = make(b);
for(int i = 0; i <= 9; i++){
cout << ans2[i] - ans1[i] << ' ';
}
return 0;
}
第二种方法 - 记忆化搜索
定义 \(dp_{pos,sum,lead,limit}\)
- \(dp_{pos,sum}\) 表示最后 \(pos\) 位的范围是 \(00..0\) ~ \(99..9\)，前面 \(2\) 的个数为 \(sum\) 时 \(2\) 的总个数，例如 \(dp_{1,3}\) 表示区间 \(2220\) ~ \(2229\) 内 \(2\) 的个数为 \(31\) 个
- \(lead\) 表示是否有前导零
- \(limit\) 表示是否有最高位限制，即若计算最高位 \(3\) 开始的数字，有数位限制
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 15, mod = 1e9 + 7;
int dp[N][N][2][2];
int now, num[N];
int dfs(int pos, int sum, int lead, int limit){
int ans = 0;
if(pos == 0) return sum;
if(dp[pos][sum][lead][limit] != -1) return dp[pos][sum][lead][limit];
int to = limit ? num[pos] : 9;
for(int i = 0; i <= to; i++){
if(i == 0 && lead) ans += dfs(pos - 1, sum, true, limit && i == to);
else if(i == now) ans += dfs(pos - 1, sum + 1, false, limit && i == to);
else if(i != now) ans += dfs(pos - 1, sum, false, limit && i == to);
}
dp[pos][sum][lead][limit] = ans;
return ans;
}
int solve(int x){
int len = 0;
while(x){
num[++len] = x % 10;
x /= 10;
}
memset(dp, -1, sizeof dp);
return dfs(len, 0, true, true);
}
signed main()
{
std::ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
int a, b; cin >> a >> b;
for(int i = 0; i <= 9; i++){
now = i;
cout << solve(b) - solve(a - 1) << ' ';
}
return 0;
}
求出ｎ之前的所有数满足位数和整除当前数
见题：E - Digit Sum Divisible (atcoder.jp)
P4127 [AHOI2009] 同类分布 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
考虑数位动规，设方程 $dp[i][j][k][l]$ 为状态:
$i$：搜到了第 $i$ 位（倒着枚举，也就是指 $i$ 到最高位都填完了）。
$j$: 表示当前的数位总和
$k$: 表示当前的数位总和模上我们枚举的数位和
$l$: 是否 $i$ 前面的位（包括 $i$）都填满了。这里的填满指填的与原数 $n$ 相同。例如 $114514$ 就是在 $n = 119198$ 时第五到最高位的填满。
那么状态转移方程就是：对于ｌ＝０，也就是当前位前面的没有被填满，那么我们在这个位置可以枚举到９
$f_{i, 0, k, l} = \sum\limits_{t = 0}^9 f_{i - 1,j + t, (10k + t) \bmod m, 0}$。表示枚举第 $i$ 位填的数为 $t$。那么因为前面存在某一位没填满，那么后面的位 $0 \sim 9$ 都是可以填的。因此 $t$ 的范围为 $[0, 9]$。
$f_{i, 1, k, l} = \sum\limits_{t = 0}^pf_{i - 1, j + t, (10k + t) \bmod m, [t == p]}$，其中 $p$ 表示给定的 $n$ 的第 $i$ 位，$[t = p]$ 表示 $t$ 是否等于 $p$（真为 $1$，假为 $0$）。表示枚举的第 $i$ 位为 $t$。那么因为前面每一位都填满了，那么这一位肯定不能超过 $n$ 原来的这一位，所以枚举到 $p$.
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e6 + 10, mod = 1e9 + 7;
int dp[20][300][300][2], dep[20];
int dfs(int u, int s, int x, int k, int lim)
{
if (u == 0)
return s == k && x == 0;
if (dp[u][s][x][lim] != -1)
return dp[u][s][x][lim];
int ed = lim ? dep[u] : 9;
dp[u][s][x][lim] = 0;
for (int i = 0; i <= ed; i++)
dp[u][s][x][lim] += dfs(u - 1, s + i, (x * 10 + i) % k, k, lim && (i == ed));
return dp[u][s][x][lim];
}
signed main()
{
std::ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
int a, b;
cin >> a >> b;
int len = 0;
a--;
while (a)
dep[++len] = a % 10, a /= 10;
int res = 0;
for (int i = 1; i <= 9 * 18; i++)
{
memset(dp, -1, sizeof dp);
res += dfs(len, 0, 0, i, 1);
}
len = 0;
while (b)
dep[++len] = b % 10, b /= 10;
int ans = 0;
for (int i = 1; i <= 9 * 18; i++)
{
memset(dp, -1, sizeof dp);
ans += dfs(len, 0, 0, i, 1);
}
cout << ans - res;
return 0;
}