今日解いた競プロの問題。

ABC208-E: N以下のある条件を満たす整数を数える、Nがクソでかい、となったら桁DP。

各桁の数字の積がK以下のものという条件だが、Kも$10^9$とまあまあでかい。$O(K\log N)$ではTLEしてしまう。

ところで各桁の数字の積というのは0~9までの数字の掛け算である以上、2,3,5,7のみを素因数に持つ数もしくは0にしかなりえない。ということで実際のところK以下であり得る数値の数を考えてみると、

• $2^{30}>10^9$
• $3^{20}>10^9$
• $5^{15}>10^9$
• $7^{12}>10^9$

ということで高々$31\times 21\times 16\times 13\approx 14000$程度でしかないことが分かる。これを念頭に状態を限定して桁DPをやっていくと間に合う。なお、どこかの桁に0を含む数は面倒なので、別途別の桁DPで数える。

ちなみに自分の実装ではDPテーブルの添え字として、既に決めた桁数とNより小さいことが確定したかどうかに加え、0以外の数字が既に現れたかどうかと2,3,5,7の指数を持つ7次元配列を用いたのだが、解説だとあり得る各桁の数字の積をmapのキーにしてやっていく実装だった。確かに状態圧縮として考えればそっちの方が妥当か。