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での動作

入力を受け取る。

s: "45"

$N$ 以下を数えるため、先に $1$ を足して s を "46" にする。

s: "46"

後ろの桁を自由に決めるための DP を作る。
末尾より後ろには数字がないため、最初にある状態は次の $1$ つだけである。

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

ここから $1$ 桁追加する。
例えば数字 $5$ を追加すると、使った数字は $5$ だけになり、桁和を $3$ で割った余りは $2$ になる。

free[1][0][0] -> free[0][32][2]

同様に $0$ から $9$ を追加すると、free[0] で $0$ でない状態は次のようになる。

次に、46 より小さい $2$ 桁の数を上の桁から数える。

先頭を 4 より小さくする場合、先頭には 1、2、3 のいずれかを置ける。
このとき条件を満たす数は次の $14$ 個である。

12, 13, 15, 18
21, 23, 24, 27
31, 32, 34, 35, 37, 38

ここまでで $14$ 個となる。

次に先頭を 4 に固定する。
ここまでに使った数字は $4$ だけで、桁和は $4$ である。

末尾は 6 より小さい 0 から 5 を調べる。
条件を満たすのは 42、43、45 の $3$ 個なので、合計は $17$ 個になる。

最後に、46 より桁数が短い正の整数も数える。
$1$ 桁の数では 6、9 の $2$ 個が条件を満たす。

したがって、答えは $17+2=19$ となる。

注意点

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

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

別解

特になし。