ABC208 E - Digit Products (500)
桁DPで解く
$ dp[i][j][k] でi桁目まで見て元の値未満かどうか、積がkの時の場合の数とする
$ kを全パターン保持することはできないのでMapで持っておく
$ 9^{18} \lt 10^{18} \lt 2^{60}なのでlong longに収まる
後ろで0をかける可能性があるので$ k以下かどうかで条件分岐を途中で書かないように注意が必要
一番上の桁はnのその桁の数以下が1通りずつ
それ以降の桁は以下のとおり
1-9でそれぞれ未満の方に1通りずつ追加
この桁が最初の0でない数字の場合
上の桁の$ kのMapそれぞれについて以下を行う
ちょうどのMapからは今の桁の値を掛けた値のみちょうどのMapに遷移する
今の値未満の値を掛けた結果は未満のMapに遷移する
未満のMapからは0-9の全ての数を掛けた結果が未満のMapに遷移する
最後に$ dp[len-1][0][k] と$ dp[len-][1][k] のうち$ k \le Kの値を全て足したものが答え