公式Editorialと違う解法で解いたので記録。
計算量多めのゴリ押し解法なのでRuby・PyPyでは通りませんでした…
解法
まず桁DPを考えました。以下のように状態を考えることができます。
上から
桁目までの数字まで決めて、そこまで決めた値を
で割った余りが
で、そこまでの桁和を
で割った余りが
で、上限値
より小さいことが確定している(
)/いない(
)ような場合の数
これで桁DPできます。状態数は
:
が最大11桁なので初期状態含めて12通り
:
で割った余りなので
通り
:これも
で割った余りなので
通り…と思いきや、
以下の非負整数の桁和は最大90なので
通り
:2通り
です。1状態あたりの遷移は桁1つの数字の取り方で高々10通りなので、高速な言語に限れば くらいまでなら通る見込みがあります。
ただし制約は であり、
が大きいときには破綻します。そこで、
が大きいときには
の商が小さいことを利用します。
の商を
、余りを
とします。さきほど見たように桁和は90以下なので、
としてもこの範囲しか調べる必要はありません。
であれば商
としてとり得る値は高々
通りなので、
を全探索します。こちらも速い言語でないと厳しいですが何とか通ります。