Typical DP Contest - E 数

E: 数 - Typical DP Contest | AtCoder

static const ll MOD = (int)1e9+7;
class e_number {
public:
    void solve(void) {
            string N; // 10^10000 は大きすぎるので string で取る
            int D;
            cin>>D>>N;

            int n = N.length();
            //
            // * 単純な DP をかんがえると S が大きすぎるので計算できない。-> 桁数で DP する
            // * 「D の倍数かどうか」 -> 「mod D で 0 になるかどうか」 と考えればよい。
            //   そうすると sum mod D -> 0 <= sum < D(<=100) の範囲だけ考えた DP にできる。
            // * 境界判定をしたいので、与えられた数より真に小さいか一致しているかを DP させる
            //
            // dp[i][j][k] := 左から i 番目までみたときの各桁の和 j (mod D)
            //                で与えられた数字の i 番目までに対して真に小さい(or 一致する)ものの個数
            //
            vector<vector<vector<ll>>> dp(n+1, vector<vector<ll>>(D,
                                               vector<ll>(2, 0)));
            // 初回は一致するケースと対応する
            dp[0][0][1] = 1;
            // O(n*D*10) <= 10000*100*10 = 10^7
            REP(i, n)
            {
                int a = N[i]-'0';
                REP(j, D)
                REP(k, 2)
                {
                    // 更新がなされないループは飛ばす
                    if (dp[i][j][k] == 0)
                        continue;
                    REP(x, 10)      // 0...9 全てで試す
                    {
                        if (k == 0) // 真に小さい
                        {
                            // given 02334...
                            // X     02332x  <- x はどれでも大丈夫
                            (dp[i+1][(j+x)%D][0] += dp[i][j][0]) %= MOD;
                        }
                        else    // 一致する
                        {
                            // given 02334a...
                            // X     02334x... <- (x <= a)
                            if (x == a)
                                (dp[i+1][(j+x)%D][1] += dp[i][j][1]) %= MOD;
                            else if (x < a)
                                (dp[i+1][(j+x)%D][0] += dp[i][j][1]) %= MOD;
                        }
                    }
                }
            }
            // 正整数なので 000...000 のケースだけ引く
            cout<<(dp[n][0][0]+dp[n][0][1]-1)%MOD<<endl;;
    }
};