ABC 007

https://atcoder.jp/contests/abc007

A. 植木算

https://atcoder.jp/contests/abc007/tasks/abc007_1

B. 辞書式順序

https://atcoder.jp/contests/abc007/tasks/abc007_2

D. 禁止された数字

https://atcoder.jp/contests/abc007/tasks/abc007_4

桁 DP であるこということをわかった上で自力 AC

void solve() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    string A, B;
    cin >> A >> B;

    auto cal = [](string S) -> ll {
        int N = S.size();
        vector dp(N + 1, vector(2, vector(2, vll(2))));
        dp[0][0][0][0] = 1;

        rep2(i, 1, N + 1) {
            int t = S[i - 1] - '0';
            rep(d, 10) {
                bool has_four = d == 4;
                bool has_nine = d == 9;
                if (d < t) {
                    rep(fr, 2) rep(ni, 2) {
                        dp[i][1][has_four || fr][has_nine || ni] += dp[i - 1][0][fr][ni];
                    }
                }
                if (t == d) {
                    rep(fr, 2) rep(ni, 2) {
                        dp[i][0][has_four || fr][has_nine || ni] += dp[i - 1][0][fr][ni];
                    }
                }
                rep(fr, 2) rep(ni, 2) {
                    dp[i][1][has_four || fr][has_nine || ni] += dp[i - 1][1][fr][ni];
                }
            }
        }

        ll ret = 0;
        rep(fr, 2) rep(ni, 2) {
            if (fr == 0 && ni == 0) continue;
            ret += dp[N][1][fr][ni] + dp[N][0][fr][ni];
        }

        return ret;
    };
    // cout << cal(B) << endl;
    // cout << cal(A) << endl;

    cout << cal(B) - cal(to_string(stoll(A) - 1)) << endl;
}