ABC 007 D - 禁止された数字

• 問題
• AC

桁DPはこれで4問目なのだが、今回も盛大にバグらせてしまった。漸化式を立てる際に境界を間違えてしまうのはさしあたり仕方ないとして、デバッグの時間はもっと短くできるはず。使っているメモ化マクロにトレース機能をつけるのが良さそう。

$g(x)$を$\{0, 1, ..., x\}$中の禁止された数の総数とすると、求める数は$g(B)-g(A-1)$である。$f_x(p, d, limit)$を桁数$p$で最上桁の数字が$d$であるような数（$d=0$のとき、000003のような表現を許す）のうちの、禁止された数字の総数とする。ただし、$limit=0$なら数は自由に選べ、$1$なら$x$を超えないようなものに限定して数えるとする。このとき、$g(x) = f_x(20, 0, 1)$であり、DPすれば求まる。

わかりにくい式でDPしてしまったように思える。4か9が既に現れたかどうかだけ見ればよいらしいので、あとで解き直すかも。