AtCoder Regular Contest 052 D - 9

公式Editorialと違う解法で解いたので記録。

計算量多めのゴリ押し解法なのでRuby・PyPyでは通りませんでした…

解法

まず桁DPを考えました。以下のように状態を考えることができます。

$dp\lbrack i \rbrack\lbrack k \rbrack\lbrack d \rbrack\lbrack l \rbrack =$ 上から $i$ 桁目までの数字まで決めて、そこまで決めた値を $K$ で割った余りが $k$ で、そこまでの桁和を $K$ で割った余りが $d$ で、上限値 $M$ より小さいことが確定している（ $l=1$ ）/いない（ $l=0$ ）ような場合の数

これで桁DPできます。状態数は

$i$ ： $M$ が最大11桁なので初期状態含めて12通り
$k$ ： $K$ で割った余りなので $K$ 通り
$d$ ：これも $K$ で割った余りなので $K$ 通り…と思いきや、 $10^{10}$ 以下の非負整数の桁和は最大90なので $\min(K, 91)$ 通り
$l$ ：2通り

です。1状態あたりの遷移は桁1つの数字の取り方で高々10通りなので、高速な言語に限れば $K \le 10^{4}$ くらいまでなら通る見込みがあります。 $(12\times 10^{4}\times 91\times 2 \times 10 = 2.184\times 10^{8})$

ただし制約は $1 \le K \le M \le 10^{10}$ であり、 $K$ が大きいときには破綻します。そこで、 $K$ が大きいときには $M \div K$ の商が小さいことを利用します。

$M \div K$ の商を $q$ 、余りを $r$ とします。さきほど見たように桁和は90以下なので、 $r$ としてもこの範囲しか調べる必要はありません。 $K \gt 10^{4}$ であれば商 $q$ としてとり得る値は高々 $10^{6}$ 通りなので、 $(q, r)$ を全探索します。こちらも速い言語でないと厳しいですが何とか通ります。