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