当前位置：首页 > news >正文

数位dp入门详解

news 来源：原创 2025/9/22 15:21:13

1. 介绍

数位 $d p$ 一般出现在来求一个范围 $[a, b]$ 内满足条件的数有多少。数位 $d p$ 的解决比较公式化，考虑每一位对最终答案的影响。

2. 案例

Luogu P2602：求给定范围 $[a, b]$ 各个数位 $k$ 出现了多少次。

考虑 $n$ 的 $10$ 进制表示
$n=\sum_{i=0}^{m}a_i 10^{i}\\$
我们令 $n$ 的最高位数的数字为 $a_m$ ，最高幂次为 $m$
$\lfloor \lg n \rfloor \\ a_m =\lfloor n /( 10^{m})\rfloor$
一个数 $n$ 中 $k$ 出现的次数
$=\sum_{i=0}^m \phi(a_i)\\ \phi(x) = \begin{cases} 1, \quad a_i=k\\ 0, \quad a_i \ne k \end{cases} \\$
最终我们需要求
$\\ ans(a,b) = \sum_{x=a}^{b} digitCnt(x)$
如果我们直接进行遍历，时间复杂度为 $\log n)$ ，对于稍稍大一点的情况是处理不了的，这时候我们的数位dp出场了。
我们定义 $d p [n] [k]$ 为 $n$ 以内的 $k$ 位出现的次数，那么我们可以把 $n$ 以内的数分为两个部分
$dp[n] =ans(1,a_{m}10^{m}-1) +\\ans(a_{m}10^{m}, n)$
考虑最高位对最终增加的数为
$\begin{cases} 10^{m} \quad , a_{m} > k \\ 0\quad, k=0 \vee a_{m} <k\\ n - a_{m}10^{m}+1 \quad,a_{m} =k \end{cases}$
我们先忽略前导 $0$ , 除去最高位的贡献后可以得到
$dp[n]=MsbCnt(n)+a_m T[10^{m} -1]\\+T[n-a_m10^{m}]$
这里的 $T [n]$ 定义为
$digitCnt(S\{n\})\\ \quad S\{n\}:= \{s_0s_1\cdots s_{m-1} \quad ,0 \le s_i \le 9\\ ,S \le n- a_m 10^{m}\}$
通俗一点就是比如 $n = 123$

那么 $S\{123\} = \{000,001,\cdots,123\}$ 。

也就是把 $n$ 之前的数列出，并加上前导 $0$ 使之与 $n$ 的位数对齐。

前导 $0$ 的添加并不会影响非 $0$ 的其他数位置的计数，因此可以得到

$k\ne0$

我们考虑 $T[10^{d} -1][k]$ 的值， $S\{10^{d}-1\}$ 集合中总共有 $10^{d}$ 个数，每个数有 $d$ 位，而每个数字在排列中等可能出现，因此
$T[10^{d}-1][1]=\cdots=T[10^{d}-1][9] \\=d \times10^{d-1}$
我们再考虑减去前导 $0$ ，容易得到 $10^{d}-1$ 内的数在 $S\{10^{d}-1\}$ 集合中的前导 $0$ 的个数为

$FrontZero(S\{10^{d}-1\}) =\sum_{i=1}^{d-1}10^{i}$

因此
$T[10^d-1][0] =\sum_{i=1}^{d-1} (d-1)10^{i} +d$

对于一个数 $n$ 而言，在它之前有 $\ne 0$ 的个数为
$dp[n][k] = MostCnt(n,k)+ma_{m}10^{m-1}+\\ dp[n-a_m10^{m}][k ]$
如果 $k = 0$ , 还需要减去前导 $0$
$=T[n][0]-\sum_{i=1}^{m}10^{m}$

代码一

#include <iostream>
#include <vector>
#include <functional>#include <unordered_set>
constexpr static int BASE = 10;
constexpr static int MAX_POW = 12;unsigned long long typeVal;
using int_type = decltype(typeVal);int MaxPowNotGreater(int_type BASE, int_type v) {int ans = 1;auto tb = BASE;for ( ;tb <= v; tb *= BASE, ans++) {}return ans - 1;
}int_type getDigitCntUntil(int_type val, int_type k) {int_type v = val;int digitCnt = MaxPowNotGreater(BASE, v);int_type mod = val % BASE;int_type  ans = ((mod >= k))? 1 : 0;v /= BASE;int_type cpow = BASE;for (int d = 1; d < digitCnt + 1; d++, v/= BASE, cpow *= BASE) {int_type m = v % BASE;if ( m > k)ans += cpow;else if ( m == k) ans += mod + 1;else {}ans += m  * (cpow / BASE) * d; mod += cpow * m;}if ( k == 0) {cpow /= BASE;while (cpow >= 1) {ans -= cpow;cpow /= BASE;}}return ans;
}
int main()
{int_type a = 1;int_type b = 99;std::cin >> a >> b;std::vector<int_type> cal(BASE, 0);for (int i = 0;i < 10;i++) {cal[i] = getDigitCntUntil( b,i) - getDigitCntUntil(a - 1, i);}for (auto num:cal) {std::cout << num << " ";}std::cout << std::endl;return 0;
}

我们可以将整次幂的数位置个数存起来

$TCnt[d][k] = T[10^{d}-1][k]$
容易得到得到递推关系式
$\\ \begin{cases} 10^{d-1} +TCnt[d-1][k],\quad k \ne 0 \\ 9TCnt[d-1][1] + TCnt[d-1][0],\quad k =0 \end{cases}$

代码2


#include <iostream>
#include <vector>
#include <functional>#include <unordered_set>
constexpr static int BASE = 10;
constexpr static int MAX_POW = 12;unsigned long long typeVal;
using int_type = decltype(typeVal);auto  fpow = [](int_type base, int_type cnt) {int_type ans = 1;while (cnt) {if (cnt & 1) ans *= base;base *= base;cnt = cnt >> 1;}return ans; 
};
auto LogFloor = [](int_type base, int_type v) {int_type m = base;int_type kdigits = 1;while ( m <= v) {m *= base;kdigits++;}kdigits--;return kdigits;
};
template<typename T>
void TEST_EQ( T a, T b) {bool ret = (a == b);if (!ret) {std::cout << a << " NOT EQUAL " << b << '\n';}else {std::cout << a << " EQUAL " << b << '\n'; }
}void testEqual(int_type a, int_type b, const std::vector<int_type>& cal) {std::vector<int> tmpCnt(BASE, 0);for (int_type i = a; i <= b; i++) {auto ti = i;while (ti) {tmpCnt[ti % BASE]++;ti /= BASE;}}bool ok = true;for (int i = 0; i < BASE; i++) {if (cal[i] != tmpCnt[i]) {std::cout << i << "failed: Real=" << tmpCnt[i] << " ;Cal= " << cal[i] <<'\n';ok = false;}}if (ok) {std::cout << "ok fine result!!!\n";}
}std::vector<std::vector<int_type>> FCnt( MAX_POW + 1, std::vector<int_type>(BASE, 0));int_type getDigitCntUntil(int_type val, int_type k) {int_type v = val;int digitCnt = LogFloor(BASE, v);int_type mod = val % BASE;int_type  ans = ((mod >= k) && k)? 1 : 0;v /= BASE;for (int d = 1; d < digitCnt + 1;d++, v /= BASE) {int_type lsb = v % BASE ;if (d != digitCnt) {ans += lsb * fpow(BASE, d - 1) * d;if ( lsb > k)ans += fpow(BASE, d);else if (lsb == k)ans += mod + 1;}else {ans += FCnt[digitCnt][k];ans += (lsb - 1) * fpow(BASE, d - 1) * d;if (0 != k) {if ( lsb > k)ans += fpow(BASE, d);else if (k == lsb)ans += mod + 1;else       ans += 0;}}mod += lsb * fpow(BASE, d);}return ans;
}
int main()
{for (int i = 0;i < BASE;i++) {FCnt[1][i] = 1;}for (int i = 2;i <= MAX_POW;i++) {for (int d = 0; d < BASE;d++) {if (d == 0)FCnt[i][d] = 9 * FCnt[i - 1][1] + FCnt[i - 1][0];else {FCnt[i][d] = fpow(10, i - 1) + 10 * FCnt[i - 1][d];} }}    int_type a = 1;int_type b = 99;std::cin >> a >> b;std::vector<int_type> cal(BASE, 0);for (int i = 0;i < 10;i++) {cal[i] = getDigitCntUntil( b,i) - getDigitCntUntil(a - 1, i);}for (auto num:cal) {std::cout << num << " ";}std::cout << std::endl;return 0;
}

1. 介绍

2. 案例

相关文章：