跳转至

數位 DP

本頁面將簡要介紹數位 DP。

引入

數位是指把一個數字按照個、十、百、千等等一位一位地拆開，關注它每一位上的數字。如果拆的是十進制數，那麼每一位數字都是 0~9，其他進制可類比十進制。

數位 DP：用來解決一類特定問題，這種問題比較好辨認，一般具有這幾個特徵：

  1. 要求統計滿足一定條件的數的數量（即，最終目的為計數）；

  2. 這些條件經過轉化後可以使用「數位」的思想去理解和判斷；

  3. 輸入會提供一個數字區間（有時也只提供上界）來作為統計的限制；

  4. 上界很大（比如 \(10^{18}\)），暴力枚舉驗證會超時。

數位 DP 的基本原理：

考慮人類計數的方式，最樸素的計數就是從小到大開始依次加一。但我們發現對於位數比較多的數，這樣的過程中有許多重複的部分。例如，從 7000 數到 7999、從 8000 數到 8999、和從 9000 數到 9999 的過程非常相似，它們都是後三位從 000 變到 999，不一樣的地方只有千位這一位，所以我們可以把這些過程歸併起來，將這些過程中產生的計數答案也都存在一個通用的數組裏。此數組根據題目具體要求設置狀態，用遞推或 DP 的方式進行狀態轉移。

數位 DP 中通常會利用常規計數問題技巧，比如把一個區間內的答案拆成兩部分相減（即 \(\mathit{ans}_{[l, r]} = \mathit{ans}_{[0, r]}-\mathit{ans}_{[0, l - 1]}\)）

那麼有了通用答案數組，接下來就是統計答案。統計答案可以選擇記憶化搜索，也可以選擇循環迭代遞推。為了不重不漏地統計所有不超過上限的答案，要從高到低枚舉每一位，再考慮每一位都可以填哪些數字，最後利用通用答案數組統計答案。

接下來我們具體看幾道題目。

例題一

例 1 Luogu P2602 數字計數

題目大意：給定兩個正整數 \(a,b\)，求在 \([a,b]\) 中的所有整數中，每個數碼（digit）各出現了多少次。

方法一

解釋

發現對於滿 \(\mathit{i}\) 位的數，所有數字出現的次數都是相同的，故設數組 \(\mathit{dp}_i\) 為滿 \(i\) 位的數中每個數字出現的次數，此時暫時不處理前導零。則有 \(\mathit{dp}_i=10 \times \mathit{dp}_{i−1}+10^{i−1}\)，這兩部分前一個是來自前 \(i-1\) 位數字的貢獻，後一個是來自第 \(i\) 位的數字的貢獻。

有了 \(\mathit{dp}\) 數組，我們來考慮如何統計答案。將上界按位分開，從高到低枚舉，不貼着上界時，後面可以隨便取值。貼着上界時，後面就只能取 \(0\) 到上界，分兩部分分別計算貢獻。最後考慮下前導零，第 \(i\) 位為前導 \(0\) 時，此時 \(1\) 到 \(\mathit{i-1}\) 位也都是 \(0\)，也就是多算了將 \(i-1\) 位填滿的答案，需要額外減去。

實現

參考代碼 
 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 <bits/stdc++.h>
using namespace std;
const int N = 15;
typedef long long ll;
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;
}

方法二

解釋

此題也可以使用記憶化搜索。\(\mathit{dp}_i\) 表示不貼上限、無前導零時，位數為 \(i\) 的答案。

詳見代碼註釋

過程

參考代碼 
 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>  //code by Alphnia
#include <cstring>
#include <iostream>
using namespace std;
#define N 50005
#define ll long long
ll a, b;
ll f[15], ksm[15], p[15], now[15];

ll dfs(int u, int x, bool f0,
       bool lim) {  // u 表示位數，f0 是否有前導零，lim 是否都貼在上限上
  if (!u) {
    if (f0) f0 = 0;
    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++) {  // 枚舉這位要填的數字
    if (f0 && i == 0)
      cnt += dfs(u - 1, x, 1, lim && i == lst);  // 處理前導零
    else if (i == x && lim && i == lst)
      cnt += now[u - 1] + 1 +
             dfs(u - 1, x, 0,
                 lim && i == lst);  // 此時枚舉的前幾位都貼在給定的上限上。
    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;  // 只有不貼着上限和沒有前導零才能記憶
  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;
}

例題二

例 2 HDU 2089 不要 62

題面大意：統計一個區間內數位上不能有 4 也不能有連續的 62 的數有多少。

解釋

沒有 4 的話在枚舉的時候判斷一下，不枚舉 4 就可以保證狀態合法了，所以這個約束沒有記憶化的必要，而對於 62 的話，涉及到兩位，當前一位是 6 或者不是 6 這兩種不同情況計數是不相同的，所以要用狀態來記錄不同的方案數。\(\mathit{dp}_{\mathit{pos},\mathit{sta}}\) 表示當前第 \(\mathit{pos}\) 位，前一位是否是 6 的狀態，這裏 \(\mathit{sta}\) 只需要取 0 和 1 兩種狀態就可以了，不是 6 的情況可視為同種，不會影響計數。

實現

參考代碼 
 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>  //code by Alphnia
#include <cstring>
#include <iostream>
using namespace std;
int x, y, dp[15][3], p[50];

int 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 = 0;
  p[cnt + 1] = 0;
  for (int i = cnt; i; i--) {  // 從高到低枚舉數位
    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 = 1;
    }
  }
  return tmp - ans;
}

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

例題三

例 3 SCOI2009 windy 數

題目大意：給定一個區間 \([l,r]\)，求其中滿足條件 不含前導 \(0\) 且相鄰兩個數字相差至少為 \(2\) 的數字個數。

解釋

首先我們將問題轉化成更加簡單的形式。設 \(\mathit{ans}_i\) 表示在區間 \([1,i]\) 中滿足條件的數的數量，那麼所求的答案就是 \(\mathit{ans}_r-\mathit{ans}_{l-1}\)。

對於一個小於 \(n\) 的數，它從高到低肯定出現某一位，使得這一位上的數值小於 \(n\) 這一位上對應的數值。而之前的所有位都和 \(n\) 上的位相等。

有了這個性質，我們可以定義 \(f(i,st,op)\) 表示當前將要考慮的是從高到低的第 \(i\) 位，當前該前綴的狀態為 \(st\) 且前綴和當前求解的數字的大小關係是 \(op\)（\(op=1\) 表示等於，\(op=0\) 表示小於）時的數字個數。在本題中，這個前綴的狀態就是上一位的值，因為當前將要確定的位不能取哪些數只和上一位有關。在其他題目中，這個值可以是：前綴的數字和，前綴所有數字的 \(\gcd\)，該前綴取模某個數的餘數，也有兩種或多種合用的情況。

寫出 狀態轉移方程：\(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)\)

這裏的 \(k\) 就是當前枚舉的下一位的值，而 \(\mathit{maxx}\) 就是當前能取到的最高位。因為如果 \(\mathit{op}=1\)，那麼你在這一位上取的值一定不能大於求解的數字上該位的值，否則則沒有限制。

我們發現，儘管前綴所選擇的狀態不同，而 \(f\) 的三個參數相同，答案就是一樣的。為了防止這個答案被計算多次，可以使用 記憶化搜索 的方式實現。

實現

參考代碼 
 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);
}

例題四

例 4.SPOJMYQ10

題面大意：假如手寫下 \([n,m]\) 之間所有整數，會有多少數看起來和在鏡子裏看起來一模一樣？（\(n,m<10^{44}, T<10^5\)）

解釋

注：由於這裏考慮到的鏡像，只有 \(0,1,8\) 的鏡像是自己本身。所以，這裏的「一模一樣」並不是傳統意義上的迴文串，而是隻含有 \(0,1,8\) 的迴文串。

首先，在數位 DP 過程中，顯然只有 \(0,1,8\) 能被選中。

其次，由於數值超過 long long 範圍，所以 \([n,m]=[1,m]-[1,n-1]\) 不再適用（高精度比較繁瑣），而是需要對 \(n\) 是否合法進行判斷，得出：\([n,m]=[1,m]-[1,n]+\mathrm{check}(n)\)。

鏡像解決了，如何判斷迴文？

我們需要用一個小數組記錄一下之前的值。在未超過一半的長度時，只要不超上限就行；在超過一半的長度時，還需要判斷是否和與之「鏡面對稱」的位相等。

需要額外注意的是，這道題的記憶化部分，不能用 memset，否則會導致超時。

實現

參考代碼 
 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[]) {  // 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: 當前位, eff: 有效位, fulc: 是否全頂格, ful0: 是否全0
int dfs(int now, int eff, bool ful0, bool fulc) {
  if (now == 0) return 1ll;
  if (!fulc && f[now][eff][ful0] != -1)  // 記憶化
    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)  // 全前導 0
      res += dfs(now - 1, eff - 1, 1, 0);
    else if (now > eff / 2)                                  // 未過半程
      res += dfs(now - 1, eff, 0, fulc && (dig[now] == i));  // 已過半程
    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[]) {  // 處理封裝
  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));

例題五

例 5.P3311 數數

題面：我們稱一個正整數 \(x\) 是幸運數，當且僅當它的十進制表示中不包含數字串集合 \(S\) 中任意一個元素作為其子串。例如當 \(S = \{22, 333, 0233\}\) 時，\(233233\) 是幸運數，\(23332333\)、\(2023320233\)、\(32233223\) 不是幸運數。給定 \(n\) 和 \(S\)，計算不大於 \(n\) 的幸運數個數。答案對 \(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\)，其中 \(|s_i|\) 表示字符串 \(s_i\) 的長度。\(n\) 沒有前導 \(0\)，但是 \(s_i\) 可能有前導 \(0\)。

解釋

閲讀題面發現，如果將數字看成字符串，那麼這就是需要完成一個多模匹配，自然而然就想到 AC 自動機。普通數位 DP 中，先從高到低枚舉數位，再枚舉每一位都填什麼，在這道題中，我們也就自然地轉化為枚舉已經填好的位數，再枚舉此時停在 AC 自動機上的哪個節點，然後從當前節點轉移到它在 AC 自動機上的子節點。

設 \(f(i,j,0/1)\) 表示當前從高到低已經填了 \(i\) 位（即在 AC 自動機上走過了 \(i\) 條邊），此時停在標號為 \(j\) 的節點上，當前是否正好貼着上界。

至於題目中的「不包含」條件，只需在 AC 自動機上給每個模式串的結尾節點都打上標記，DP 過程中一旦遇上這些結尾節點就跳過即可。

轉移很好想，詳見代碼主函數部分。

實現

參考代碼 
 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
#include <bits/stdc++.h>  //code by Alphnia
using namespace std;
#define N 1505
#define ll long long
#define 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;
}

此題可以很好地幫助理解數位 DP 的原理。

習題

Ahoi2009 self 同類分佈

洛谷 P3413 SAC#1 - 萌數

HDU 6148 Valley Number

CF55D Beautiful numbers

CF628D Magic Numbers

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