[AtCoder] ABC 029 D – 1

問題

方針

桁 DP を用いて考えます。\( d(i, j, k) \) を \( i \) 桁目まで調べた時、\( 1 \) の数が \( j \) であり、未満フラグが \( k \) であるものの数とします。\( k = 0 \) であるとき、\( N \) の \( i \) 桁目まで一致している状態で、\( k = 1 \) は \( N \) より小さいことが確定している状態を表します。

コード

参考