Typical DP Contest E - 数
解法
いわゆる桁DPというやつ.
dp[i][j][lt] := 上から i 桁目まで見た時,各桁の総和の余りが j であり,かつ N 未満かどうかが lt (less than) のときの場合の数
この dp だと 0 が常に条件を満たすので,最後に 1 を引く.
ソースコード
#include <bits/stdc++.h> using namespace std; using ll = long long; constexpr int mod = 1e9 + 7; int main() { int d; cin >> d; string n; cin >> n; vector<vector<ll>> dp(d, vector<ll>(2)); dp[0][0] = 1; for(int i = 0; i < (int)n.size(); ++i) { vector<vector<ll>> nxt(d, vector<ll>(2)); const int cur = n[i] - '0'; for(int s = 0; s < d; ++s) { for(int lt = 0; lt < 2; ++lt) { const int lim = lt ? 9 : cur; for(int v = 0; v <= lim; ++v) { const int ns = (s + v) % d; const int nlt = lt | (v < cur); (nxt[ns][nlt] += dp[s][lt]) %= mod; } } } dp = move(nxt); } cout << (dp[0][0] + dp[0][1] + mod - 1) % mod << endl; }