Typical DP Contest E - 数

解法

いわゆる桁DPというやつ.
dp[i][j][leq] := 下から i 桁目まで見た時,各桁の総和の余りが j であり,かつ N 以下である可能性がある (less equal) 場合の数
としておいて,遷移をする.
この時,最上位に 0 を許容する (leading zero) ことに注意.これは例えば N = 100 にたいして 099 == 99 をカウントすることを意味するためである.

最後に,1 以上 N 以下だから 0 を省く必要がある.

ソースコード

#include <bits/stdc++.h>
using namespace std;
 
using ll = long long;
 
constexpr ll MOD = 1e9+7;
 
int main() {
    int D;
    string N;
    cin >> D >> N;
    reverse(N.begin(), N.end());
    vector<vector<vector<ll>>> dp(N.size()+1, vector<vector<ll>>(D, vector<ll>(2)));
    dp[0][0][1] = 1;
    for(int i=0; i<N.size(); ++i) {
        for(int j=0; j<D; ++j) {
            for(int k=0; k<2; ++k) {
                for(int d = 0; d<=9; ++d) {
                    bool leq = d < (N[i] - '0') || k == 1 && d == (N[i] - '0');
                    (dp[i+1][(j + d) % D][leq] += dp[i][j][k]) %= MOD;
                }
            }
        }
    }
    cout << (dp[N.size()][0][1] - 1 + MOD) % MOD << endl;
}