ABC007 D - 禁止された数字

atcoder.jp
桁DPの典型的な問題

【題意】
自然数の区間[A, B]において、4または9を含む整数はいくつあるか？
【典型ポイント】
1~Nの数え上げは桁DP
区間和
【方針】
dp[i][smaller][j]:=1~Nの整数のうち、前方i桁まで見て、4または9が含まれている(j==1)か含まれていない(j==0)場合の数
smaller:未満フラグ
・遷移( dp[i+1][smaller | x

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pll = pair<long long, long long>;
constexpr char ln =  '\n';
constexpr long long MOD = 1000000007;
constexpr long long INF = 1000000000 + 100;
constexpr long long LINF = 1000000000000000000 + 100;
#define all(v) v.begin(), v.end()
#define rep(i, n) for(int i=0;i<(n);i++)
#define rept(i, j, n) for(int i=(j); i<(n); i++)
#define rrep(i, n) for(int i=(n); i>=0; i--)
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }


int main(){
    ll A; string B, C; cin >> A >> B;
    C = to_string(A-1);

    auto digit_dp = [&](string N) -> ll{
        const int n = N.size();
        ll dp[n+1][2][2]{};
        dp[0][0][0] = 1;
        for(int i=0; i<n; i++){
            for(int smaller=0; smaller<2; smaller++){
                for(int j=0; j<2; j++){
                    for(int x=0; x<=(smaller ? 9 : N[i]-'0'); x++){
                        dp[i+1][smaller | x<N[i]-'0'][j or x==4 or x==9] += dp[i][smaller][j];
                    }
                }
            }
        }
        return dp[n][0][1] + dp[n][1][1];
    };
    cout << digit_dp(B) - digit_dp(C) << ln;
}