[AtCoder] ABC 135 D – Digits Parade

問題

方針

動的計画法

\( d(i, j) \) を \( i \) 桁目までの調べた時、余りが \( j \) となるものの個数とします。初期値として、\( d(0, 0) = 1 \) とします。

  • \( S_i = ?\) のとき

\( ? \) には、\( 0 \) から \( 9 \) までの数字が入るので、

\[ d(i + 1, (10^i \times k + j )\bmod 13) \mathrel{+}=  d[i][j] \ ( 0 \leq k \leq 9 \wedge 0 \leq j \leq 12)\]

となります。

  • \( S_i = a \ ( 0 \leq a \leq 9)\) のとき

\[ d(i + 1, (10^i \times a + j )\bmod 13) \mathrel{+}=  d[i][j] \ ( 0 \leq j \leq 12)\]

コード