整数をvector に入れて桁DP.
部分問題として,区間 ] に対する答え を求める.
これが出来れば,元の問題に対する答えは .
今回の桁DPは上の桁から調べていく.下の桁から決めるケースもあるが,多くの場合は上から決めれば良い.
桁目まで見たときに,すでに より真に小さくなっているかを記録しながらDP.
遷移するとき,今決める桁を rep(c,10) で回す.
注意:まだ真に小さくなっていないにも関わらず,今決めようとしている桁c が与えられた数字の桁 v[i]より大きくなってしまう場合は除く.
ソースコードの continue の部分.
ll dp[25][2][2];
vll itov(ll a){
if(a == 0) return vll(1, 0);
vll v;
while(a){
v.push_back(a % 10);
a /= 10;
}
reverse(all(v));
return v;
}
int main() {
ll a,b; cin >> a >> b;
a--;
vll va, vb;
va = itov(a);
auto f = [&](const vll& v) -> ll {
rep(i,25) rep(j,2) rep(k,2) dp[i][j][k] = 0;
ll n = v.size();
dp[0][0][0] = 1;
rep(i,n) {
rep(le,2){
rep(k,2){
rep(c, 10){
ll le2 = le || (c < v[i]);
ll k2 = k || (c == 4 || c == 9);
if(c > v[i] && le == 0) continue;
dp[i+1][le2][k2] += dp[i][le][k];
}
}
}
}
return dp[n][0][1] + dp[n][1][1];
};
cout << ans << endl;
return 0;
}