AIOJ

This page briefly introduces digit DP.

Introduction

A digit refers to splitting a number apart one digit at a time—ones, tens, hundreds, thousands, and so on—and focusing on the digit at each position. If the number is decimal, each digit is 0~9; other bases are analogous to decimal.

Digit DP is used to solve a particular class of problems. They are generally recognizable by these features:

Count the number of numbers satisfying certain conditions (that is, the ultimate goal is counting);
After transformation, these conditions can be understood and checked using the idea of "digits";
The input provides a number interval (sometimes only an upper bound) as the limit for counting;
The upper bound is very large (for example, $10^{18}$ ), so brute-force enumeration and verification would time out.

The basic principle of digit DP:

Consider how humans count. The most straightforward method is to increment numbers one by one from small to large. However, for numbers with many digits, we find many repeated parts in this process. For example, counting from 7000 to 7999, from 8000 to 8999, and from 9000 to 9999 is very similar: in all three cases the last three digits change from 000 to 999, and the only difference is the thousands digit. Therefore, we can merge these processes and store the counts produced by them in a general array. This array uses states set according to the specific requirements of the problem, and performs state transitions by recurrence or DP.

Digit DP usually uses techniques from ordinary counting problems, such as splitting the answer for an interval into the difference of two parts (namely, $\mathit{ans}_{[l, r]} = \mathit{ans}_{[0, r]}-\mathit{ans}_{[0, l - 1]}$ ).

With the general answer array, we next count the answers. We can use memoized search or iterative recurrence. To count every answer not exceeding the upper bound exactly once, enumerate each digit from high to low, consider which digits can be placed at each position, and finally use the general answer array to calculate the answer.

Next, let us look at several problems in detail.

Example 1

Example 1 Luogu P2602 Digit Counting

Problem statement: Given two positive integers $a,b$ , find how many times each digit appears among all integers in $[a,b]$ .

Method 1

Explanation

For numbers with exactly $\mathit{i}$ digits, every digit appears the same number of times. Let $\mathit{dp}_i$ be the number of occurrences of each digit among all $i$ -digit numbers, temporarily ignoring leading zeros. Then $\mathit{dp}_i=10 \times \mathit{dp}_{i−1}+10^{i−1}$ : 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, split the upper bound by digits and enumerate from high to low. When no longer matching the upper bound, later positions can take arbitrary values. While matching the upper bound, later positions can only take values from $0$ to the corresponding upper-bound digit, so calculate the two contributions separately. Finally, consider leading zeros: when the $i$ -th digit is a leading $0$ , positions $1$ through $\mathit{i-1}$ are also $0$ , which overcounts the answer for filling the $i-1$ positions, so this must be subtracted.

Implementation

Reference Code

#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 they are not tight to the upper bound and have no leading zeros.

See the code comments for details.

Process

Reference Code

#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 is the number of digits, f0 indicates leading zeros, lim indicates whether all digits are tight to the 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 the digit to fill at this position
    if (f0 && i == 0)
      cnt += dfs(u - 1, x, 1, lim && i == lst);  // handle leading zeros
    else if (i == x && lim && i == lst)
      cnt += now[u - 1] + 1 +
             dfs(u - 1, x, 0,
                 lim && i == lst);  // the preceding digits are all tight to the given 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 with no leading zeros
  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 statement: Count how many numbers in an interval have neither a 4 nor a consecutive 62 in their digits.

Explanation

If there is no 4, checking during enumeration and simply not enumerating 4 guarantees a valid state, so this constraint does not need to be memoized. For 62, two digits are involved: the counts differ depending on whether the current digit is 6, so a state is needed to record the different numbers of schemes. $\mathit{dp}_{\mathit{pos},\mathit{sta}}$ represents the state at position $\mathit{pos}$ , recording whether the previous digit is 6. Here $\mathit{sta}$ only needs the two states 0 and 1; the case of not being 6 can be treated as one state and does not affect the count.

Implementation

Reference Code

#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 statement: Given an interval $[l,r]$ , find the number of numbers satisfying no leading $0$ and the difference between every pair of adjacent digits is at least $2$ .

Explanation

First transform the problem into a simpler form. Let $\mathit{ans}_i$ be the number of valid numbers in the interval $[1,i]$ . Then the required answer is $\mathit{ans}_r-\mathit{ans}_{l-1}$ .

For a number smaller than $n$ , when reading it from high to low, there must be a position whose digit is smaller than the corresponding digit of $n$ , while all previous digits equal the corresponding digits of $n$ .

Using this property, define $f(i,st,op)$ as the number of numbers when the position currently being considered is the $i$ -th position from high to low, the state of the current prefix is $st$ , and the relation between the prefix and the number currently being solved is $op$ ( $op=1$ means equal and $op=0$ means smaller). In this problem, the prefix state is the previous digit, because the digits forbidden at the position being determined depend only on the previous digit. In other problems, this value may be the sum of the prefix's digits, the $\gcd$ of all digits in the prefix, the remainder of the prefix modulo some number, or a combination of two or more such values.

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 currently being enumerated, and $\mathit{maxx}$ is the largest value currently available. If $\mathit{op}=1$ , the value taken at this position cannot be greater than the corresponding digit of the number being solved; otherwise, there is no restriction.

Although the selected prefix states may differ, when the three parameters of $f$ are the same, the answer is also the same. To prevent this answer from being calculated repeatedly, memoized search can be used.

Implementation

Reference Code

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 statement: If all integers between $[n,m]$ are written by hand, how many numbers look exactly the same as they do in a mirror?（ $n,m<10^{44}, T<10^5$ ）

Explanation

Note: Of the mirrored digits considered here, only $0,1,8$ are their own mirror images. Therefore, 「exactly the same」 here does not mean a palindrome in the traditional sense, but a palindrome containing only $0,1,8$ .

First, in the digit DP process, it is clear that only $0,1,8$ can be selected.

Second, because the values exceed the range of long long, $[n,m]=[1,m]-[1,n-1]$ is no longer applicable (high-precision comparison is cumbersome). Instead, we need to check whether $n$ is valid, giving $[n,m]=[1,m]-[1,n]+\mathrm{check}(n)$ .

The mirror restriction is handled; how do we check for a palindrome?

We need a small array to record previous values. Before passing half the length, it is enough not to exceed the upper bound; after passing half the length, we must also check whether the digit equals its 「mirror-symmetric」 counterpart.

It is worth noting that the memoization part of this problem cannot use memset, otherwise it will time out.

Implementation

Reference Code

int check(char cc[]) {  // special case 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 position, eff: effective positions, fulc: whether all are tight, ful0: whether all are 0
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 0
      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[]) {  // wrapper
  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 Counting

Problem statement: A positive integer $x$ is called lucky if and only if its decimal representation does not contain any element of the set of digit strings $S$ as a substring. For example, when $S = \{22, 333, 0233\}$ , $233233$ is lucky, while $23332333$ , $2023320233$ , and $32233223$ are not. Given $n$ and $S$ , calculate the number of lucky numbers not exceeding $n$ . Take 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|$ is the length of string $s_i$ . $n$ has no leading $0$ , but $s_i$ may have leading $0$ .

Explanation

Reading the statement, if we regard the number as a string, this is a multiple-pattern matching problem, so the AC automaton naturally comes to mind. In ordinary digit DP, we enumerate the digits from high to low and then enumerate what to fill at each position. Here, we naturally transform this into enumerating how many positions have already been filled, then which node of the AC automaton we are currently at, and transitioning from the current node to its child in the AC automaton.

Let $f(i,j,0/1)$ denote that $i$ positions have been filled from high to low (that is, $i$ edges have been traversed in the AC automaton), the current node is the node numbered $j$ , and whether the current state is exactly tight to the upper bound.

For the condition of not containing any forbidden string, mark the terminal node of every pattern string in the AC automaton. During DP, skip a transition as soon as one of these terminal nodes is encountered.

The transition is straightforward; see the main function in the code.

Implementation

Reference Code

#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 is a good way to understand the principles of digit DP.

Exercises

Ahoi2009 self Same Distribution

Luogu P3413 SAC#1 - Cute Numbers

HDU 6148 Valley Number

CF55D Beautiful numbers

CF628D Magic Numbers