公開日 :
更新日 :

桁DP

「\(N\) 以下の整数のうち、条件を満たすものの個数」を、上の桁から \(1\) 桁ずつ数字を決めながら数えるDP。
\(N\) が \(10^{500}\) のように巨大でも、計算量は「桁数 × 状態数 × \(10\)」 で済む。

使える問題の目印

  • \(N\) が大きすぎて \(1 \sim N\) を全部調べられない(\(10^{18}\) 以上、文字列で与えられる など)。
  • 条件が各桁の数字で決まる(桁和、特定の数字を含むか、使う数字の種類、隣の桁との関係など)
  • 「L 以上 R 以下」なら、\(f(R)-f(L\,-\,1)\) で「\(N\) 以下」の形に直す。

大切な考え方 : tight(N をなぞっているか)

上の桁から数字を決めていくとき、作っている数は2種類に分かれる。

意味次の桁に置ける数字
tight(t=1)ここまで N とまったく同じ数字を並べている\(0 \sim N\) のその桁まで
確定済み(t = 0)どこかで N より小さい数字を置いた\(0 \sim 9\) 何でもいい
  • tight で N の桁と同じ数字を置く → tight のまま
  • tight で N の桁より小さい数字を置く → 確定済みになる
  • 確定済みが tight に戻ることはない

例 : \(N=1013\) で \(10\) まで来た(tight)。次の桁に置けるのは \(0\) か \(1\)。

  • \(0\) を置く → \(100\) は \(101\) より小さいので確定済み
  • \(1\) を置く → \(101\) で tight のまま

コードを書く前に決めること

決めること例
1. 最後に判定するために何を覚えていくか(状態)桁和 mod 3、使った数字の集合(ビットマスク)
2. 数字 c を置いたとき、状態がどう変わるかr → (r + c) % 3、 m → m | 1<<c
3. 最後に、どの状態を答えに数えるか3 つの条件のうち満たす数がちょうど 1

1.の状態はできるだけ小さくする。
「数そのもの」は覚えられない(大きすぎる)ので、判定に必要な情報だけに絞る。

例

条件覚えるもの大きさ
D の倍数 / 桁和が D の倍数数 mod D / 桁和 mod DD
数字 3 を含む含んだかどうか2
使う数字の種類使った数字の集合(ビットマップ)1024
0 でない数字の個数が K 個個数(K を超えたらまとめる)K + 2
隣の桁と違う直前の数字10

型(dp[tight][状態])

string N; cin >> N;
// dp[t][s] : t = tight か、s = 状態
vector dp(2, vector<mint>(S));
dp[1][初期状態] = 1;                      // 何も置いていない数は N をなぞっている
rep(i, (int)N.size()) {
    int d = N[i] - '0';                   // ← '-' であって '=' ではない!
    vector ndp(2, vector<mint>(S));
    rep(t, 2) rep(s, S) {
        if (dp[t][s] == 0) continue;
        int lim = t ? d : 9;              // tight なら N の桁まで
        for (int c = 0; c <= lim; c++) {
            int nt = (t && c == lim);     // N の桁と同じ数字なら tight のまま
            ndp[nt][次の状態(s, c)] += dp[t][s];
        }
    }
    swap(dp, ndp);
}
// 答え = dp[0][OK な状態] + dp[1][OK な状態]   (dp[1] は N 自身)
  • 最後に t = 0 と t = 1 の両方と足す。 t = 1 は N 自身のこと。
  • この型は 0 も数えてしまう(全部 0 を置いた「000…0」)。
    1 以上を数えるなら、0 が条件を満たす場合に 1 を引く。

先頭ゼロの扱い

N = 1013 のとき、「45」は「0045」として数えられている。
桁和や「mod D」なら先頭の 0 は影響しないので、気にしなくてよい。

気にする必要があるのは、0 という数字そのものが条件に関わるとき:

  • 「使う数字の種類」
  • 「0 を含む」「隣の桁と違う」など

このときは状態に started(もう 0 でない数字を置いたか)を加える。

int ns = (s || c != 0);                  // 0 でない数字を置いたら始まる
int nm = ns ? (m | 1 << c) : 0;          // 始まる前の 0 は集合に入れない

最後は started = 1 の状態だけを数える(ついでに 0 も除かれる)。

例1 : 桁和が D の倍数

K 以下の正整数で、桁和が D の倍数のものの個数 \((mod 10^{9}+7)\)。

string K; int D; cin >> K >> D;
vector dp(2, vector<mint>(D));           // dp[tight][桁和 mod D]
dp[1][0] = 1;
rep(i, (int)K.size()) {
    int d = K[i] - '0';
    vector ndp(2, vector<mint>(D));
    rep(t, 2) rep(r, D) {
        if (dp[t][r] == 0) continue;
        int lim = t ? d : 9;
        for (int c = 0; c <= lim; c++) {
            int nt = (t && c == lim);
            ndp[nt][(r + c) % D] += dp[t][r];
        }
    }
    swap(dp, ndp);
}
mint ans = dp[0][0] + dp[1][0] - 1;      // 0(桁和 0)を除く
cout << ans.val() << endl;

例2 : 3 つの条件のちょうど1つ

\(1 \sim N\) で「3 の倍数」「数字 3 を含む」「数字がちょうど 3 種類」のちょうど 1 つを満たす数の個数。
\(N < 10^{500}\)。

  • 状態 : 使った数字の集合 \(m\)(1024通り) × 桁和 mod 3(3 通り)
  • ビットマスクを持てば「3 を含むか」と「何種類か」の両方がわかる(m >> 3 & 1, popcount(m))
  • 種類数だけで足りない。次の数字が新しい数字かどうか分からないから
  • 数字の種類を数えるので、先頭ゼロ(started)が必要
// dp[tight][started][mask][r]
vector dp(2, vector(2, vector(1024, vector<mint>(3))));
dp[1][0][0][0] = 1;
rep(i, (int)N.size()) {
    int d = N[i] - '0';
    vector ndp(2, vector(2, vector(1024, vector<mint>(3))));
    rep(t, 2) rep(s, 2) rep(m, 1024) rep(r, 3) {
        mint v = dp[t][s][m][r];
        if (v == 0) continue;
        int lim = t ? d : 9;
        for (int c = 0; c <= lim; c++) {
            int nt = (t && c == lim);
            int ns = (s || c != 0);
            int nm = ns ? (m | 1 << c) : 0;
            ndp[nt][ns][nm][(r + c) % 3] += v;
        }
    }
    swap(dp, ndp);
}
mint ans = 0;
rep(t, 2) rep(m, 1024) rep(r, 3) {
    int cnt = (r == 0) + ((m >> 3) & 1) + (__builtin_popcount(m) == 3);
    if (cnt == 1) ans += dp[t][1][m][r];  // started = 1 だけ
}

計算量 : 500 桁 × 状態 2 × 2 × 1024 × 3 × 10 ≒ 6 × 10^7。

別の書き方 : tightを変数で持つ

tight な数は「N の先頭 i 桁」の1通りしかないので、配列にせず変数で持つ書き方もある。

  • dp[m][r] : 確定済み(N より小さい)だけ
  • tmask, tr : N の先頭 i 桁の状態(tight の 1 個)
  • 各桁で (1.確定済み → 0〜9 (2.tight → N の桁未満(先頭桁は1から) (3.この桁から始まる短い数(1 〜 9)を足す。
  • 最後に ok(tmask, tr) なら N 自身として +1

練習問題