http://codeforces.com/contest/1036/problem/C
L≦x≦Rのなかでclassyな数の個数を答えよ。
※ classy:10進数表記した時に0でない数が3個以下である数
前提知識
解法
http://codeforces.com/contest/1036/submission/42623549
[L,R]が扱いづらいので、[0,R] - [0,L-1]を答えとするいつものテクを使おう。
今後は「f(x) := [0,x]でclassyな数」を構築していく。
桁DPを使おう。
dp[dgt][nz][isless] := dgt桁目まで確定していて、0でない桁がnz個あって、xとの今の所の大小関係がislessの組み合わせ数
※ isless=0:今の所同じ、isless=1:既に下回っている
一般的な桁DP。遷移も一般的。
nzは[0,3]を見るようにする。4も遷移してしまうので、場所だけは取っておこう。
あと、クエリ形式なので、初期化も忘れずに。
ll L, R; //--------------------------------------------------------------------------------------------------- string S; int N; ll dp[20][6][2]; ll f(ll x) { S = to_string(x); N = S.length(); rep(dgt, 0, N + 1) rep(nz, 0, 5) rep(isless, 0, 2) dp[dgt][nz][isless] = 0; dp[0][0][0] = 1; rep(dgt, 0, N) rep(nz, 0, 4) rep(isless, 0, 2) { int c = S[dgt] - '0'; rep(x, 0, 10) { int dgt2 = dgt + 1; int nz2 = nz; if (x != 0) nz2++; if (isless == 1) { dp[dgt2][nz2][isless] += dp[dgt][nz][isless]; } else { if (x < c) dp[dgt2][nz2][1] += dp[dgt][nz][isless]; else if (x == c) dp[dgt2][nz2][0] += dp[dgt][nz][isless]; } } } ll res = 0; rep(nz, 0, 4) rep(isless, 0, 2) res += dp[N][nz][isless]; return res; } //--------------------------------------------------------------------------------------------------- void solve() { cin >> L >> R; ll ans = f(R); ans -= f(L - 1); printf("%lld\n", ans); } //--------------------------------------------------------------------------------------------------- void _main() { int T; cin >> T; rep(t, 0, T) solve(); }