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;; } };