問題概要

問題文はこちらを参照してください。

いわゆる桁DPの問題です。桁DPはなかなか慣れることができません。。。

解法

「$n$以下の正整数で」という条件と$n$が巨大な数という時点で、桁DPを考えるべきなんだと思います。桁DPは、桁数を1つずつ増やしていって、$j$桁目を考える際に、$j-1$桁目までの状態と$j$桁目の数字としてすべての数字(0~9)を変化させた時の状態をまとめていきます。さらに、これとは別に、$n$の$j$桁目の数字まで(0~nのj桁目の数字)を変化させた場合の2つの漸化式を考えることになります。

今回は、各桁で考慮するべき条件が桁の数の和が$D$の倍数であるものということなので、$D$で割った余りの数だけ状態を考える必要があります。つまり、1つ前の桁までの各桁の数の和を$D$で割った余りの数が$i$になる組合せの数がわかれば、それにその桁の数字を足して$D$で割った余りの数になる組合せの数がわかることになります。

漸化式の定義: $$\begin{eqnarray} dp[(i+k)\mod D][j] & += & dp[i][j-1]\\ dp2[(i+k)\mod D][j] & += & \begin{cases}dp2[i][j-1] & (k=num)\\ dp[i][j-1] & (k\lt num)\\ 0 & (k\gt num)\end{cases} \end{eqnarray}$$

$dp[i][j]$:$j$桁目までの数で、各桁の数の和を$D$で割った余りが$i$となる数の個数。「$j$桁目までの数」とは0~999..99と、0から9が$j$個並んだ数までの計$10^j$個の数を意味する

$dp2[i][j]$:$n$の$j$桁目までの数で、各桁の数の和を$D$で割った余りが$i$となる数の個数。「$n$の$j$桁目までの数」とは$n$が123456789と仮定した場合、その数字の下から$j$桁目までの数値、すなわち$j=3$の場合0~789の数を意味する

$k$は0~9とし、$num$は$n$の$j$桁目の数字とする。
$(0\le i \lt D,\ 0\le j \le nの桁数)$

初期値:$dp[0][0]=1,\ dp2[0][0]=1$

求める解:$dp2[0][n]-1$ (0も$D$の倍数とカウントしているのでその分引く)

このように、各桁の数字を0~9で動かしていって、求めるたい条件がどうなるかを計算していきます。その際に上記のように2つの漸化式に分けて考えるのがポイントです。

考察

桁DPを使えばいいというのはわかるのですが、コンテスト本番でコーディングまで落とし込める自信はまだありません。。。