[AtCoder] ABC 007 D – 禁止された数字

問題

方針

桁DP

\( n \) 以下の数字の中で \( 4 \) または \( 9 \) を含まない数の個数を求めます。\( d_{i, 0} \) を上位 \( i \) 桁目まで調べたとき、\( 4 \) または \( 9 \) を含むか含まないかのフラグとします。含まないときは、\( d_{i, 0} = 1 \) とし、含むときは、\( d_{i, 0} = 0 \) とします。また、\( d_{i, 1} \) を \( n \) 上位 \( i \) 桁まで調べた時、\( n \) の \( i \) 桁目までの数よりも小さい数で、\( 4 \) または \( 9 \) を含まない数の個数とします。このとき、\( n \) の桁数を \( l \) とすると、\( d_{l, 0} + d_{l, 1} \) が答えになります。\( d_{l, 0} = 0 , 1 \) となることに注意します。また、初期値として、\( d_{0, 0} = 1 \) とします。

ここで、\( n \) の \( i \) 桁目の数字を \( s_i \) とします。\( d_{i, 0} \) について、上位の桁から見て \( 4 \) または \( 9 \) が出現しない限り \( d_{i, 0} = 1 \) となります。出現した場合、その桁以降は \( d_{i, 0} = 0 \) となります。次に、\( d_{i, 1} \) について、\( 0 \leq j < s[i]  \wedge j \neq 4 \) を満たす \( j \) の個数を \( k \) とすると、

\[d_{i + 1, 1} = k \times d_{i, 0} + 8 \times d_{i, 1}\]

となります。

例えば、\( n = 8341 \) とすると、\( d_{i, 0} = 1 \ (0 \leq i \leq 2)\), \( d_{i, 0} = 1 \ (3 \leq i \leq 4)\) となります。\( d_{0, 1} = 0 \) として、上から \( 1 \) 桁目の数字は \(s_{1} =  8 \) なので、\( 8000 \) 未満の数字で、\( s_{1} \) の候補は、 \( (0, 1, 2, 3, 5, 6, 7)\) となるので、\( k = 7 \) より、\( d_{1, 1} = 7 + 8 \times 0\) となります。

次に、\( d_{2, 1} \) について考えます。同様にして、\( 8300\) 未満の数字で \( 8x?? \) の \( x \) に入る数字は \( (0, 1, 2) \) なので、\( k = 3\) となります。 また、\( xy?? \) ,  \( 0 \leq x \leq 7 \) という形で、\( y \) に入る数字は任意の数字となります。 以下同様にして最後の桁まで調べます。

コード