Skip to content

Digit DP

This page provides a brief introduction to Digit DP.

Introduction

Digit refers to splitting a number into its individual digits according to place values such as ones, tens, hundreds, thousands, etc. If splitting a decimal number, each digit ranges from 0 to 9; other bases can be analogized to decimal.

Digit DP: Used to solve a specific class of problems, which are generally recognizable by the following characteristics:

  1. It requires counting the number of integers satisfying certain conditions (i.e., the ultimate goal is counting);
  2. These conditions can be understood and judged using the idea of "digits" after transformation;
  3. The input provides a numeric interval (sometimes only an upper bound) as a constraint for counting;
  4. The upper bound is large (e.g., \(10^{18}\)), making brute-force enumeration and verification time out.

The basic principle of Digit DP:

Consider how humans count; the most naive counting method is incrementing one by one from small to large. However, we notice that for numbers with many digits, this process has many repetitive parts. For example, counting from 7000 to 7999, from 8000 to 8999, and from 9000 to 9999 are very similar processes: the last three digits change from 000 to 999, with only the thousands digit differing. Therefore, we can merge these processes and store the counting answers generated during these processes in a general array. This array sets states according to the specific requirements of the problem and performs state transitions using recursion or DP.

Digit DP often utilizes general counting problem techniques, such as splitting the answer within an interval into two parts by subtraction (i.e., \(\mathit{ans}_{[l, r]} = \mathit{ans}_{[0, r]}-\mathit{ans}_{[0, l - 1]}\)).

With the general answer array, the next step is to compute the answer. The answer can be computed using memoized search or iterative DP. To count all answers not exceeding the upper bound without repetition or omission, we enumerate each digit from high to low, consider which digits can be filled in each position, and finally use the general answer array to compute the answer.

Next, let's look at a few specific problems.

Example 1

Example 1 Luogu P2602 Digit Count

Problem summary: Given two positive integers \(a,b\), find how many times each digit appears in all integers in \([a,b]\).

Method 1

Explanation

Observe that for numbers with exactly \(\mathit{i}\) digits, the occurrence counts of all digits are the same. Let array \(\mathit{dp}_i\) represent the occurrence count of each digit in numbers with exactly \(i\) digits, ignoring leading zeros for now. Then \(\mathit{dp}_i=10 \times \mathit{dp}_{i−1}+10^{i−1}\), where the first part comes from the contribution of the first \(i-1\) digits, and the second part comes from the contribution of the \(i\)-th digit.

With the \(\mathit{dp}\) array, we consider how to compute the answer. Split the upper bound into digits, enumerate from high to low. When not tight to the upper bound, the remaining digits can be chosen arbitrarily. When tight to the upper bound, the remaining digits can only range from \(0\) to the corresponding digit of the upper bound. Compute contributions in two parts separately. Finally, consider leading zeros: when the \(i\)-th digit is a leading \(0\), the first \(1\) to \(\mathit{i-1}\) digits are also \(0\), meaning we overcounted the answer for filling the first \(i-1\) digits, which needs to be subtracted.

Implementation

Reference Code 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <cstdio>
using namespace std;
constexpr int N = 15;
using ll = long long;
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;
}

Method 2

Explanation

This problem can also be solved using memoized search. \(\mathit{dp}_i\) represents the answer for numbers with \(i\) digits when not tight to the upper bound and without leading zeros.

See code comments for details.

Process

Reference Code 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
using ll = long long;
constexpr int N = 50005;
ll a, b;
ll f[15], ksm[15], p[15], now[15];

ll dfs(int u, int x, bool f0,
       bool lim) {  // u: digit position, f0: has leading zero, lim: tight to upper bound
  if (!u) {
    if (f0) f0 = false;
    return 0;
  }
  if (!lim && !f0 && (~f[u])) return f[u];
  ll cnt = 0;
  int lst = lim ? p[u] : 9;
  for (int i = 0; i <= lst; i++) {  // enumerate digit to fill
    if (f0 && i == 0)
      cnt += dfs(u - 1, x, 1, lim && i == lst);  // handle leading zero
    else if (i == x && lim && i == lst)
      cnt += now[u - 1] + 1 +
             dfs(u - 1, x, 0,
                 lim && i == lst);  // current prefix is tight to upper bound
    else if (i == x)
      cnt += ksm[u - 1] + dfs(u - 1, x, 0, lim && i == lst);
    else
      cnt += dfs(u - 1, x, 0, lim && i == lst);
  }
  if ((!lim) && (!f0)) f[u] = cnt;  // memoize only when not tight and no leading zero
  return cnt;
}

ll gans(ll d, int dig) {
  int len = 0;
  memset(f, -1, sizeof(f));
  while (d) {
    p[++len] = d % 10;
    d /= 10;
    now[len] = now[len - 1] + p[len] * ksm[len - 1];
  }
  return dfs(len, dig, 1, 1);
}

int main() {
  scanf("%lld%lld", &a, &b);
  ksm[0] = 1;
  for (int i = 1; i <= 12; i++) ksm[i] = ksm[i - 1] * 10ll;
  for (int i = 0; i < 9; i++) printf("%lld ", gans(b, i) - gans(a - 1, i));
  printf("%lld\n", gans(b, 9) - gans(a - 1, 9));
  return 0;
}

Example 2

Example 2 HDU 2089 Don't 62

Problem summary: Count how many numbers in an interval do not have the digit 4 nor the consecutive digits 62.

Explanation

For the constraint of no 4, simply skip 4 when enumerating digits to ensure state validity, so this constraint does not require memoization. For 62, since it involves two digits, the counting differs depending on whether the previous digit is 6 or not. Therefore, we need states to record different counts. \(\mathit{dp}_{\mathit{pos},\mathit{sta}}\) represents the current digit position \(\mathit{pos}\) and whether the previous digit is 6. Here \(\mathit{sta}\) only needs two states: 0 and 1. Cases where the previous digit is not 6 can be treated as the same, which does not affect counting.

Implementation

Reference Code 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
int x, y, dp[15][3], p[50];

void pre() {
  memset(dp, 0, sizeof(dp));
  dp[0][0] = 1;
  for (int i = 1; i <= 10; i++) {
    dp[i][0] = dp[i - 1][0] * 9 - dp[i - 1][1];
    dp[i][1] = dp[i - 1][0];
    dp[i][2] = dp[i - 1][2] * 10 + dp[i - 1][1] + dp[i - 1][0];
  }
}

int cal(int x) {
  int cnt = 0, ans = 0, tmp = x;
  while (x) {
    p[++cnt] = x % 10;
    x /= 10;
  }
  bool flag = false;
  p[cnt + 1] = 0;
  for (int i = cnt; i; i--) {  // enumerate digits from high to low
    ans += p[i] * dp[i - 1][2];
    if (flag)
      ans += p[i] * dp[i - 1][0];
    else {
      if (p[i] > 4) ans += dp[i - 1][0];
      if (p[i] > 6) ans += dp[i - 1][1];
      if (p[i] > 2 && p[i + 1] == 6) ans += dp[i][1];
      if (p[i] == 4 || (p[i] == 2 && p[i + 1] == 6)) flag = true;
    }
  }
  return tmp - ans;
}

int main() {
  pre();
  while (~scanf("%d%d", &x, &y)) {
    if (!x && !y) break;
    if (x > y) swap(x, y);
    printf("%d\n", cal(y + 1) - cal(x));
  }
  return 0;
}

Example 3

Example 3 SCOI2009 windy numbers

Problem summary: Given an interval \([l,r]\), count the numbers satisfying the condition: no leading zeros and the absolute difference between adjacent digits is at least 2.

Explanation

First, transform the problem into a simpler form. Let \(\mathit{ans}_i\) denote the count of numbers satisfying the condition in interval \([1,i]\). Then the desired answer is \(\mathit{ans}_r-\mathit{ans}_{l-1}\).

For a number less than \(n\), there must be some digit from high to low where its value is less than the corresponding digit in \(n\), while all previous digits equal those of \(n\).

Using this property, we can define \(f(i,st,op)\) as the number of numbers when considering the \(i\)-th digit from high to low, with current prefix state \(st\) and relation \(op\) to the number being solved (\(op=1\) means equal, \(op=0\) means less). In this problem, the prefix state is the value of the previous digit, because the digits that cannot be chosen for the current position depend only on the previous digit. In other problems, this value could be: the digit sum of the prefix, the \(\gcd\) of all digits in the prefix, the remainder of the prefix modulo some number, or a combination of two or more.

Write the state transition equation: \(f(i,st,op)=\sum_{k=1}^{\mathit{maxx}} f(i+1,k,op=1~ \operatorname{and}~ k=\mathit{maxx} )\quad (|\mathit{st}-k|\ge 2)\)

Here \(k\) is the value of the next digit being enumerated, and \(\mathit{maxx}\) is the maximum digit allowed at the current position. If \(\mathit{op}=1\), the digit chosen cannot exceed the corresponding digit of the number being solved; otherwise, there is no restriction.

We observe that even if the prefix states differ, as long as the three parameters of \(f\) are the same, the answer remains identical. To avoid computing this answer multiple times, we can implement it using memoized search.

Implementation

Reference Code 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
int dfs(int x, int st, int op)  // op=1 =; op=0 <
{
  if (!x) return 1;
  if (!op && ~f[x][st]) return f[x][st];
  int maxx = op ? dim[x] : 9, ret = 0;
  for (int i = 0; i <= maxx; i++) {
    if (abs(st - i) < 2) continue;
    if (st == 11 && i == 0)
      ret += dfs(x - 1, 11, op & (i == maxx));
    else
      ret += dfs(x - 1, i, op & (i == maxx));
  }
  if (!op) f[x][st] = ret;
  return ret;
}

int solve(int x) {
  memset(f, -1, sizeof f);
  dim.clear();
  dim.push_back(-1);
  int t = x;
  while (x) {
    dim.push_back(x % 10);
    x /= 10;
  }
  return dfs(dim.size() - 1, 11, 1);
}

Example 4

Example 4.SPOJMYQ10

Problem summary: If we write down all integers between \([n,m]\) by hand, how many numbers look exactly the same when viewed in a mirror? (\(n,m<10^{44}, T<10^5\))

Explanation

Note: Considering mirror images, only \(0,1,8\) are mirror-symmetric to themselves. Therefore, "look exactly the same" here does not mean traditional palindromes, but palindromes consisting only of \(0,1,8\).

First, during Digit DP, obviously only \(0,1,8\) can be selected.

Second, since the numbers exceed long long range, the formula \([n,m]=[1,m]-[1,n-1]\) is no longer applicable (high-precision comparison is cumbersome). Instead, we need to check whether \(n\) itself is valid, leading to: \([n,m]=[1,m]-[1,n]+\mathrm{check}(n)\).

Mirror symmetry is handled. How to check for palindrome?

We need a small array to record previous digits. Before exceeding half the length, we only need to ensure the digit does not exceed the upper bound. After exceeding half the length, we also need to check if the digit equals its "mirror-symmetric" counterpart.

An additional note: for memoization in this problem, memset cannot be used, as it would cause timeouts.

Implementation

Reference Code 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
int check(char cc[]) {  // special check for n
  int strc = strlen(cc);
  for (int i = 0; i < strc; ++i) {
    if (!(cc[i] == cc[strc - i - 1] &&
          (cc[i] == '1' || cc[i] == '8' || cc[i] == '0')))
      return 0ll;
  }
  return 1ll;
}

// now: current digit, eff: effective digits, fulc: tight to upper bound, ful0: all zeros
int dfs(int now, int eff, bool ful0, bool fulc) {
  if (now == 0) return 1ll;
  if (!fulc && f[now][eff][ful0] != -1)  // memoization
    return f[now][eff][ful0];

  int res = 0, maxk = fulc ? dig[now] : 9;
  for (int i = 0; i <= maxk; ++i) {
    if (i != 0 && i != 1 && i != 8) continue;
    b[now] = i;
    if (ful0 && i == 0)  // all leading zeros
      res += dfs(now - 1, eff - 1, 1, 0);
    else if (now > eff / 2)                                  // before halfway
      res += dfs(now - 1, eff, 0, fulc && (dig[now] == i));  // after halfway
    else if (b[now] == b[eff - now + 1])
      res += dfs(now - 1, eff, 0, fulc && (dig[now] == i));
  }
  if (!fulc) f[now][eff][ful0] = res;
  return res;
}

char cc1[100], cc2[100];
int strc, ansm, ansn;

int get(char cc[]) {  // encapsulated processing
  strc = strlen(cc);
  for (int i = 0; i < strc; ++i) dig[strc - i] = cc[i] - '0';
  return dfs(strc, strc, 1, 1);
}

scanf("%s%s", cc1, cc2);
printf("%lld\n", get(cc2) - get(cc1) + check(cc1));

Example 5

Example 5.P3311 Count

Problem: We call a positive integer \(x\) lucky if and only if its decimal representation does not contain any string from set \(S\) as a substring. For example, when \(S = \{22, 333, 0233\}\), \(233233\) is lucky, while \(23332333\), \(2023320233\), \(32233223\) are not. Given \(n\) and \(S\), compute the number of lucky numbers not exceeding \(n\). Output the answer modulo \(10^9 + 7\).

\(1 \leq n<10^{1201}，1 \leq m \leq 100，1 \leq \sum_{i = 1}^m |s_i| \leq 1500，\min_{i = 1}^m |s_i| \geq 1\), where \(|s_i|\) denotes the length of string \(s_i\). \(n\) has no leading zeros, but \(s_i\) may have leading zeros.

Explanation

Reading the problem, if we treat numbers as strings, this requires multi-pattern matching, naturally leading to AC automaton. In standard Digit DP, we enumerate digits from high to low, then enumerate which digit to fill at each position. In this problem, we naturally transform to enumerating the number of digits already filled, then enumerating which node we are currently at on the AC automaton, and transitioning from the current node to its children on the AC automaton.

Let \(f(i,j,0/1)\) represent that we have filled \(i\) digits from high to low (i.e., traversed \(i\) edges on the AC automaton), currently at node \(j\), and whether we are tight to the upper bound.

For the "does not contain" condition, simply mark the ending nodes of each pattern string on the AC automaton, and skip these ending nodes during DP.

The transitions are straightforward; see the main function part of the code.

Implementation

Reference Code 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;
using ll = long long;
constexpr int N = 1505;
constexpr int mod = 1000000007;
int n, m;
char s[N], c[N];
int ch[N][10], fail[N], ed[N], tot, len;

void insert() {
  int now = 0;
  int L = strlen(s);
  for (int i = 0; i < L; ++i) {
    if (!ch[now][s[i] - '0']) ch[now][s[i] - '0'] = ++tot;
    now = ch[now][s[i] - '0'];
  }
  ed[now] = 1;
}

queue<int> q;

void build() {
  for (int i = 0; i < 10; ++i)
    if (ch[0][i]) q.push(ch[0][i]);
  while (!q.empty()) {
    int u = q.front();
    q.pop();
    for (int i = 0; i < 10; ++i) {
      if (ch[u][i]) {
        fail[ch[u][i]] = ch[fail[u]][i], q.push(ch[u][i]),
        ed[ch[u][i]] |= ed[fail[ch[u][i]]];
      } else
        ch[u][i] = ch[fail[u]][i];
    }
  }
  ch[0][0] = 0;
}

ll f[N][N][2], ans;

void add(ll &x, ll y) { x = (x + y) % mod; }

int main() {
  scanf("%s", c);
  n = strlen(c);
  scanf("%d", &m);
  for (int i = 1; i <= m; ++i) scanf("%s", s), insert();
  build();
  f[0][0][1] = 1;
  for (int i = 0; i < n; ++i) {
    for (int j = 0; j <= tot; ++j) {
      if (ed[j]) continue;
      for (int k = 0; k < 10; ++k) {
        if (ed[ch[j][k]]) continue;
        add(f[i + 1][ch[j][k]][0], f[i][j][0]);
        if (k < c[i] - '0') add(f[i + 1][ch[j][k]][0], f[i][j][1]);
        if (k == c[i] - '0') add(f[i + 1][ch[j][k]][1], f[i][j][1]);
      }
    }
  }
  for (int j = 0; j <= tot; ++j) {
    if (ed[j]) continue;
    add(ans, f[n][j][0]);
    add(ans, f[n][j][1]);
  }
  printf("%lld\n", ans - 1);
  return 0;
}

This problem helps in understanding the principles of Digit DP well.

Exercises

Ahoi2009 self same distribution

Luogu P3413 SAC#1 - Cute Numbers

HDU 6148 Valley Number

CF55D Beautiful numbers

CF628D Magic Numbers

本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用