Atcoder Typical DP Contest E. 数

Atcoder Typical DP Contest E. 数

E: 数 - Typical DP Contest | AtCoder

解法

自分の実際の思考の流れに従ってまとめておく。

まず自明に思いつくDPが、$\ dp[i][j] := \ $(上からi番目までを見て、各桁の和をDで割った余りがjであるような組み合わせの数)である。しかしこれだけでは上手く漸化式を立てることができない。

まず、$\ N = 10^k\ $のときを考えよう。このとき一番左の桁を0にすれば、各桁の数は0から9までの数を自由に取りうる（すべて0になる場合は除く）。よって、上に述べたdpの更新が容易になる。例えば、$\ i + 1\ $番目の数が7だとするとDPの定義より、dp[i + 1][j] += dp[i][[(j - 7) % D]のように更新できる。これを$\ k = 0, 1,2, ..., 9\ $ですべて計算する。

次に、もう少し一般に、$\ N = a * 10^k\ $のときを考える。このとき、まず、1番目の数を0に固定すると、上に述べたようにその総数が求められる。次に1番目の数を1から$\ a - 1\ $に固定したときを考える。このときも実はほとんど同じように考えることができる。例えばこれを3に固定したとすれば、上のDPにおいて、$\ j = -3 = d - 3\ $となっているものをとってこればよいからである。これで1番目を0から$\ a - 1\ $に固定したときの答えは求めらた。

さて、これ以降、一番左の数は、$\ a\ $に固定して考えて良い。次の桁からも同じようにその桁の数を固定して考えていくのだが、2番目の数を固定したときに使えるdp値は、dp[n - 2][j]である。これを今までと同じように利用して計算する。ただし、固定した数をどこかに保存して、常にその数を引いたmodをとらなければいけない。　

あとから気づいたが、同じ桁の値でも、それが上限値をとっているのか的な変数をもたせてやれば、もっとわかりやすく書けそう。とか思いながら他の人の解説などを見てみると、まさにそうだった。というかそれを桁DPとかなんとか言うらしい。前も桁DPの問題をそうとは知らずに解いたような...。まぁいいや。

実装

#include "bits/stdc++.h"
using namespace std;

static const long long MOD = 1000000007;

signed main() {
        string s;
        int d;
        cin >> d >> s;
        int n = s.size();
        vector<vector<long long> > dp(n, vector<long long> (d, 0));
        dp[0][0] = 1;
        for (int i = 1; i < n; i ++) {
                for (int j = 0; j < d; j ++) {
                        for (int k = 0; k <= 9; k ++) {
                                dp[i][j] = dp[i][j] + dp[i - 1][(((j - k) % d) + d) % d] % MOD;
                        }
                }
        }
        long long ans = 0;
        long long ex = 0;
        for (int i = 0; i < n; i ++) {
                if (s[i] != '0') ans = ans + dp[n - 1 - i][((( - ex) % d) + d) % d] % MOD;
                for (int k = 1; k <= s[i] - '0' - 1; k ++) {
                        ans = ans + dp[n - 1 - i][(((- k - ex) % d) + d) % d] % MDO;
                }
                ex = (ex + s[i] - '0') % d;
        }
        cout << (ans - 1) % MOD << endl;
        return 0;
}