公式解説の桁DPとは異なる方針です。

\(f(x) = \)（\(0\)以上\(x\)以下の、禁止された数字の個数）として、求めるものは\(f(b) - f(a - 1)\) です。したがって、\(f(x)\) を計算できればこの問題を解くことができます。

\(g(x, i) = \)（ある整数 \(y\) であって以下の条件を満たすものの個数）とします。

• 任意の\(j < i\) について\(x\) の 先頭から\(j\) 桁目と \(y\) の先頭から \(j\) 桁目は一致する。
• \(y\) の先頭から \(i\) 桁目は \(x\) の 先頭から\(i\) 桁目よりも真に小さい。
• \(y\) は禁止された数字ではない（すなわち、どの桁にも \(4, 9\) を含まない）

このとき、\(g(x, i)\) の値は、\(x\) の先頭から\(i-1\) 桁目までに \(4, 9\) が含まれる場合は \(0\)、そうでない場合は （\(x\) の \(i\) 桁目の数字よりも真に小さい \(4, 9\) 以外の数字の個数）\(\times\) （\(8^{（xの桁 数 - i）}\)）として計算できます。\(i = 1, 2, \ldots , \)（\(x\) の桁数）について \(g (x, i)\) の値を計算して、\(x+1\) から引き、\(x\) がどの桁にも \(4, 9\) を含まない場合は更に \(1\) を引いたものが\(f(x)\) となります。

実装例（C++）