-
Notifications
You must be signed in to change notification settings - Fork 7
/
Digit_DP_[L,R]_some_property.cpp
63 lines (53 loc) · 1.25 KB
/
Digit_DP_[L,R]_some_property.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
// Problem : https://codeforces.com/contest/1036/problem/C
#include <bits/stdc++.h>
#define int long long
#define sz(x) (int)(x.size())
using namespace std;
const int N = 20, mod = 1e9 + 7, inf = 1e18;
string A, B;
int n, dp[N][2][2][5];
int go(int pos, bool bigA, bool smallB, int cnt) {
if (cnt > 3)
return 0;
if (pos >= n)
return 1;
int &ans = dp[pos][bigA][smallB][cnt];
if (~ans)
return ans;
ans = 0;
for (int i = 0; i < 10; i++) {
if (!bigA && i < A[pos] - '0')
continue;
if (!smallB && i > B[pos] - '0')
continue;
ans += go(pos + 1, bigA || (i > A[pos] - '0'), smallB || (i < B[pos] - '0'),
cnt + (i != 0));
}
return ans;
}
int32_t main() {
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
int t;
cin >> t;
while (t--) {
memset(dp, -1, sizeof(dp));
cin >> A >> B;
reverse(A.begin(), A.end());
while (sz(A) < sz(B))
A.push_back('0');
reverse(A.begin(), A.end());
n = sz(B);
int ans = 0;
for (int i = 0; i < 10; i++) {
if (i < A[0] - '0')
continue;
if (i > B[0] - '0')
continue;
ans += go(1, i > A[0] - '0', i < B[0] - '0', i != 0);
}
cout << ans << '\n';
}
}