ABC465 E - Digit Circus

考え方

超巨大な数以下の整数のうち条件を満たす数の個数を考える問題。
しかも、条件が各桁の数でどうのこうのというものとなれば、いわゆる桁DPの出番。

一般にはよく全部を並列処理するようなコードが紹介されるが、ここでは理解しやすい方法で解く。

まず、ある桁より下で $0$ から $9$ までなんでも使っていい場合に、どんなデータが何個あるか数えておく。
この問題であれば、「どの数字を使っているかの $10$ ビットの数」「$3$ で割った余り」で分けて数える。
最初は後ろから $1$ 桁目より下を求める。
これは、使っている数字なしで余り $0$ が $1$ つあるだけ。
次に、後ろから $2$ 桁目より下を求める。
これは、後ろから $1$ 桁目より下の各データから、前に $0$ から $9$ をつけてみて配る DP をする。
以下、同じように繰り返して $0$ 桁目より下の情報まで作っておく。
$N$ が最大 $500$ 桁なので、$500 \times 2^{10} \times 3 = 1536000$ 個のデータになる。
それぞれから $10$ 回配るので、$15360000$ 回の処理で終わり、計算量は問題ない。

これを事前処理としてやっておけば、$N$ 未満だけを数える作業がスムーズに済む。

先頭の桁から、以下の条件全てに該当するものの個数を結果に加える。
これで、細かい一部の点を除き、答えになる。

• そこより前は全ての桁が $N$ と同じ
• そこの桁は $N$ の同じ桁より小さい
• そこより下は事前処理の結果の任意のもの
• 問題の $3$ 条件のうち $1$ つだけを満たす

あとは、微調整。
まず、この問題では先頭の $0$ が許されていない。
そこを $0$ 埋めしても影響がない問題ならいいが、今回はそうではない。
したがって、以下の $2$ つの補正が必要となる。

• $0$ 桁目だけ、$0$ に決めることを許さない
• 桁数が短いものは同様の方法で改めて別計上する

また、以上の解法は、$N$ 未満のものしか計算できない。
問題は $N$ 以下を求めるように言っているので、これでは $N$ そのものが調査から漏れる。
よって、最初に $N$ に $1$ を加えておき、$N+1$ 未満で数えるとよい。
$999$ のような、$1$ 足すことで桁数が変わる入力に注意すること。
調査対象が $501$ 桁になるので上で述べた計算量に若干修正が必要だが、それでも十分間に合う。

入力例1での動作

入力を受け取る。
文字列として受け取った $N$ の値は、ここでは $s$ としている。

s: "45"

s に $1$ を足す。
桁数も取得しておく。

s: "46"
n: 2

free[i][b][r] を用意する。
free[i] には、i 桁目より後ろを自由に決めるときの情報が入る。
b は使った数字の種類をビットで表現し、r は桁和を $3$ で割った余りを表す。
free[i][b][r] は $s$ との大小に関係なく、そういう条件のものがいくつあるかが入る。

まず、free[1] は、後ろの桁に自由に決められる余地がない。
よって、以下のもの以外は全て $0$。

free[1][0][0]: 1

次に free[0] を作る。
今回、$N+1$ は $2$ 桁なので、free[0] には $1$ 桁分を自由に決める場合の個数が入る。
以下の $10$ 箇所が $1$ で、残りは $0$。

free[0][1][0]: 1
free[0][2][1]: 1
free[0][4][2]: 1
free[0][8][0]: 1
free[0][16][1]: 1
free[0][32][2]: 1
free[0][64][0]: 1
free[0][128][1]: 1
free[0][256][2]: 1
free[0][512][0]: 1

上の桁から順に見る。
まず、まだ何も見ていないので、桁和と数字の種類は次の通りである。

sum_d: 0
bit_d: 0

$0$ 桁目を見る。
s[0] は $4$ なので、先頭桁を $1$、$2$、$3$ のどれかにする。
$0$ にするのは先頭桁になってしまうので、一旦スキップ。

先頭桁が $1$ のものは、free[0] のうち以下の $4$ つが該当。
（実際の処理的にはもっと該当しているものがあるが、中身が $0$ のものは説明上省略している）

free[0][4][2]: 1    ← 12
free[0][8][0]: 1    ← 13
free[0][32][2]: 1   ← 15
free[0][256][2]: 1  ← 18

先頭桁が $2$ のものは、free[0] （中身が $0$ でないもの）のうち以下の $4$ つが該当。
（実際の処理的にはもっと該当しているものがあるが、中身が $0$ のものは説明上省略している）

free[0][2][1]: 1    ← 21
free[0][8][0]: 1    ← 23
free[0][16][1]: 1   ← 24
free[0][128][1]: 1  ← 27

先頭桁が $3$ のものは、free[0] （中身が $0$ でないもの）のうち以下の $6$ つが該当。
（実際の処理的にはもっと該当しているものがあるが、中身が $0$ のものは説明上省略している）

free[0][2][1]: 1    ← 31
free[0][4][2]: 1    ← 32
free[0][16][1]: 1   ← 34
free[0][32][2]: 1   ← 35
free[0][128][1]: 1  ← 37
free[0][256][2]: 1  ← 38

よって、先頭桁が $1$、$2$、$3$ であるものを数えると、$14$ 個である。

result: 14

次の桁へ進むため、ここまでの桁和と数字の種類を更新する。

sum_d: 4
bit_d: 16 (二進法で0000010000)

$1$ 桁目を見る。
s[1] は $6$ なので、$0$ 桁目を $4$ で固定したまま、$1$ 桁目を $0$ から $5$ のどれかにする。
このうち条件を満たすものは、$42$、$43$、$45$ の $3$ 個である。

result: 17

そして、桁数が $s$ より少ないもの、つまり $1$ 桁の数を数える。
$1$ 桁の数のうち、条件を満たすものは $6$、$9$ の $2$ 個である。

result: 19

注意点

答えは $998244353$ で割った余りを要求されているので、剰余類環の考えに従って処理する。
何か足し算をするたびに結果を % 998244353 する。

$N$ は int 型や long long 型からはみ出る。
文字列として扱うこと。

別解

特になし。