数位DP小记

rlc202204 / 2024-08-30 / 原文

1.基础

1.1. 问题

数位 DP 解决的一般都是和数字相关的计数问题，常见的有 $l \sim r$ 中有多少数符合某个关于数位的条件。

对于这种问题，我们都是先用前缀和转化成小于等于某个数的问题。

下面以 P2602 [ZJOI2010] 数字计数为模板题。

1.2 记忆化搜索

我们先枚举每个数码。

我们考虑设一个状态 $(i,j,0/1,0/1)$ 表示当前处理到了第 $i$ 位，已经填了 $j$ 个当前数码，有无前导 $0$，是否贴着上界。

我们发现，有前导 0 或者贴着上界的状态其实只会搜索到 1 次，所以我们只用记录 $f(i,j)$ 表示 $(i,j,0,0)$ 状态的答案来进行记忆化搜素。

首先，如果 $i = 0$，我们直接返回 $j$。

其次，如果已经计算过了，我们返回答案。

否则，我们根据是否贴着上界算一下这一位的范围，然后枚举每个数码。

枚举的过程中，我们需要特判 0 和前导 0 的情况。

得出答案后在记忆化并返回即可。

时间复杂度是位数乘以进制。

#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 15;

int tmp, num[N] = {0};//表示当前处理的数字
long long f[N][N] = {{0}};//f[i][j] 表示处理到 i 已经有了 j 个 tmp，且没有前导 0 和最高位限制

long long dfs(int pos, int sum, bool hd, bool lim) {
	long long ans = 0ll;
	if (pos == 0)
		return sum;
	if (!hd && !lim && f[pos][sum] != -1)
		return f[pos][sum];
	int up = (lim ? num[pos] : 9);
	for (int i = 0; i <= up; i++) {
		if (i == 0 && hd)
			ans += dfs(pos - 1, sum, hd, lim && i == up);
		else if (i == tmp)
			ans += dfs(pos - 1, sum + 1, false, lim && i == up);
		else
			ans += dfs(pos - 1, sum, false, lim && i == up);
	}
	if (!hd && !lim)
		f[pos][sum] = ans;
	return ans;
}

long long slv(long long n) {
	int len = 0;
	while (n > 0)
		num[++len] = n % 10, n /= 10;
	memset(f, -1, sizeof f);
	return dfs(len, 0, true, true);
}

int main() {
	long long l, r;
	cin >> l >> r;
	for (int i = 0; i <= 9; i++) {
		tmp = i;
		cout << slv(r) - slv(l - 1) << " ";
	}
	return 0;
}

1.3 适合多测的方法

我们从另一个角度看，每次我们相当于需要处理的就是一个数划分成的若干区间。关键就是上界。

所以我们可以直接最开始计算 $f(i,j)$ 表示从低到高确定了 $i$ 位，$j$ 的总个数。

然后对于一个数，我们从高到低处理，枚举每一位用 dp 值计算出答案即可。

这样我们只用一遍 dp 就可以解决问题了。

本质就是我们对于每个数单独考虑，枚举其符合了多少上界的条件

#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 15;

long long pw[N] = {0}, f[N] = {0};
long long cnt[N] = {0};

void DP() {
	pw[0] = 1;
	for (int i = 1; i < N; i++) {
		f[i] = f[i - 1] * 10 + pw[i - 1];
		pw[i] = 10 * pw[i - 1];
	}
}

int num[N] = {0};
void slv(long long n, int op) {
	int len = 0;
	while (n > 0)
		num[++len] = n % 10, n /= 10;
	for (int i = len; i >= 1; i--) {//前面的都是上界
		for (int j = 0; j < 10; j++)
			cnt[j] += f[i - 1] * num[i] * op;
		for (int j = 0; j < num[i]; j++)
			cnt[j] += pw[i - 1] * op;
		long long tot = 0;
		for (int j = i - 1; j >= 1; j--)
			tot = tot * 10ll + num[j];//最高位单独处理
		cnt[num[i]] += (tot + 1) * op;
		cnt[0] -= pw[i - 1] * op;//处理前导0
	}
}

int main() {
	long long l, r;
	cin >> l >> r;
	DP();
	slv(r, 1), slv(l - 1, -1);
	for (int i = 0; i < 10; i++)
		cout << cnt[i] << " ";
	return 0;
}