ABC 114 Cを桁DPでも解いてみた

「桁DPで解きたくなる誘惑に負けず全探索で解くべき問題」ABC 114 Cを、後学のために桁DPでも解いてみたメモ。
（本番では3,5,7のみで出来た9桁までの数を全列挙しました）

桁DPのアイデアと実装については桁DP入門 - pekempey's blog がとても参考になります。
で
状態はどう持てばいいか

• 何桁目まで見たか ()
• N未満か (0..1)
• 3を既に含んでいるか (0..1)
• 5を既に含んでいるか (0..1)
• 7を既に含んでいるか (0..1)
• 357以外を含んでいるか (0..1)
• 0より大きいか (0..1)

「0より大きいか」というか、leading zeroを非753数字としてカウントしないフラグが必要。。（これに気づかなくてちょっと時間かかった。本番でやったらはまってただろう）
→AC
https://beta.atcoder.jp/contests/abc114/submissions/3711407

#include <bits/stdc++.h>
using namespace std;
#define rep(var, n) for (int var = 0; var < (n); ++var)

vector<int> num_to_vec(int x, int base = 10) {
    if (x == 0) return vector<int>{0};
    vector<int> v;
    while (x) {
        int q = x / base, r = x % base;
        v.push_back(r);
        x = q;
    }
    reverse(v.begin(), v.end());
    return v;
}

int solve(int N) {
    vector<int> a = num_to_vec(N, 10);
    int K = a.size();

    int dp[K + 1][2][2][2][2][2][2];
    mset(dp, 0);

    dp[0][0][0][0][0][0][0] = 1;

    rep(i, K) rep(j, 2) rep(k, 2) rep(l, 2) rep(m, 2) rep(n, 2) rep(o, 2) {
        int lim = j ? 9 : a[i];
        rep(d, lim + 1) {
            bool non357 = n ? (d != 3 && d != 5 && d != 7)
                            : (d != 0 && d != 3 && d != 5 && d != 7);
            dp[i + 1][j || d < lim][k || d == 7][l || d == 5][m || d == 3][n || d][o || non357]
               += dp[i][j][k][l][m][n][o];
        }
    }

    int ans = 0;
    rep(j, 2) rep(k, 2) rep(l, 2) rep(m, 2) rep(n, 2) rep(o, 2) {
        if (k == 1 && l == 1 && m == 1 && o == 0) ans += dp[K][j][k][l][m][n][o];
    }
    return ans;
}

int main() {
    int N;
    cin >> N;
    cout << solve(N) << endl;
    return 0;
}