ABC 007
Table of Contents
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;
}