Typical DP Contest E - 数

問題
提出コード

解法

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

• のとき
  桁目を決める時点で未満であることが確定しているかどうかにかかわらず、桁目以降でどんな数字を当てはめても未満になります。ので、になります。
  ということで、遷移は
  
  となります。

• のとき
  未満が確定しているかどうかは、桁目の時点で未満であることが確定しているかどうかに依存します。桁目の状態をそのまま受け継ぎます。
  ということで、遷移は
  
  
  となります。

• のとき
  未満であることが桁目の時点で決まっていればいいですが、そうでない場合は、桁目でを選ぶとを超えてしまうので、問題の条件を満たさなくなります。ということで、についてのみ考えればよく、遷移は
  
  のみとなります。

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