ABC#007 D.禁止された数字

その他

問題

整数A,Bについて、A〜Bの整数で、4または9を含む整数はいくつあるか？

A,B<=10^18

考え方

例えば123という数字以下の4,9を含む整数の数を求めたいと考える。
一桁目が0の時は00〜99まででカウントした場合の数になる。
一桁目が1の時は、00〜23まででカウントした場合の数になり、二桁目が0,1の時は0〜9、2の時は0〜3まででカウントした場合の数になっている。


したがって、dp[桁][00...00〜99...99(全部求める場合)か、00...00〜WX...YZ(途中まで求める場合)か]といういうものを考えると、
・00...00〜99...99(全部求める)までの場合
　・その桁が4か9なら10^{残りの桁}を加算
　・それ以外なら、次の桁について同様に計算したものを加算
・00...00〜WX...YZ(途中まで求める)までの場合
　・その桁が4か9で、Wでなければ、10^{残りの桁}、Wならば、整数「X..YZ」を加算
　・それ以外ならば、Wでなければ、次の桁について00..00〜99..99(全部求める)の場合と同様に求め加算、Wならば、00...00〜X...YZ(途中まで求める)の場合と同様に求めて加算
の関係になっている。

Bについて求めて、A-1について求めたものを引けば、A〜Bのものを求められる。