読者です 読者をやめる 読者になる 読者になる

yukicoder No.372 It's automatic

解法

DP

コード

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

const int64_t MOD = 1e9 + 7;
int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);

  string inS;
  cin >> inS;
  int N = inS.size();
  vector<int> S(N);
  for (int i = 0; i < N; ++i) S[i] = inS[i] - '0';
  int M;
  cin >> M;
  vector<vector<int>> remainer(M, vector<int>(10, 0));
  for (int i = 0; i < M; ++i)
    for (int j = 0; j < 10; ++j) remainer[i][j] = (i * 10 + j) % M;

  vector<int64_t> dp(M, 0);
  dp[0] = 1;
  int64_t zeros = 0;
  for (int i = 0; i < N; ++i) {
    vector<int64_t> next(M, 0);
    for (int m = 0; m < M; ++m) {
      next[m] += dp[m];
      next[m] %= MOD;

      int r = remainer[m][S[i]];
      next[r] += dp[m];
      if (m == 0 && S[i] == 0) {
        zeros++;
        next[r] = (next[r] - 1 + MOD) % MOD;
      } else {
        next[r] %= MOD;
      }
    }
    dp.swap(next);
  }
  cout << ((dp[0] + zeros - 1 + MOD) % MOD) << endl;
}