ツバサの備忘録

主に備忘録代わりに精進記録を載せていくつもりです。

Typical DP Contest E - 数

問題
提出コード

解法

制約をみてもわかるように桁DPです。
dp[i][j][m]とします。iは、上からi桁目を決める段階、という意味です。jは、今作成している数字の桁和をDで割った余りがjであるという意味です。mは、今作成している数字がN未満であることが確定しているかどうか、を表します(している場合は1、なければ0です)。初期状態は、dp[0][0][0] = 1です。
Nの桁数をnNの上からi桁目をN_iと表記することにします。
最終的な答えは、dp[n][0][1]+dp[n][0][0]-1です。-1は、0を表しています。今回は正整数が条件なので、0を省かなければなりません。
i-1桁目まで決めた段階での桁和をDで割った余りがjのとき、i桁目をkにすることを考えます(kはもちろん0以上9以下です)。
これは、dp[i][(j+k)\%D][1]dp[i][(j+k)\%D][0]についてを考えることになります。
ここから先は、kN_iの関係によって3つに場合分けされます。順番に見ていきます。

  •  k \lt N_iのとき
    i-1桁目を決める時点でN未満であることが確定しているかどうかにかかわらず、i+1桁目以降でどんな数字を当てはめてもN未満になります。ので、m=1になります。
    ということで、遷移は
    dp[i][(j+k)\%D][1] += dp[i-1][j][0] + dp[i-1][j][1]
    となります。

  •  k = N_iのとき
    N未満が確定しているかどうかは、i-1桁目の時点でN未満であることが確定しているかどうかに依存します。i-1桁目の状態をそのまま受け継ぎます。
    ということで、遷移は
    dp[i][(j+k)\%D][1] += dp[i][j][1]
    dp[i][(j+k)\%D][0] += dp[i][j][0]
    となります。

  •  k \gt N_iのとき
    N未満であることがi-1桁目の時点で決まっていればいいですが、そうでない場合は、i桁目でkを選ぶとNを超えてしまうので、問題の条件を満たさなくなります。ということで、m=1についてのみ考えればよく、遷移は
    dp[i][(j+k)\%D][1] += dp[i][j][1]
    のみとなります。


あとは、これを繰り返してDPを行っていけばよいです。10^{9}+7で割った余りを求めることに注意しましょう。