Typical DP Contest E - 数

問題文

http://tdpc.contest.atcoder.jp/tasks/tdpc_number

解法

いわゆる桁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;
}