# |
Author |
Problem |
Lang |
Verdict |
Time |
Memory |
Sent |
Judged |
|
84116963 |
Practice:
JKLover |
55D
- 22
|
C++17 (GCC 7-32)
|
Accepted
|
748 ms
|
19432 KB
|
2020-06-18 03:19:42 |
2020-06-18 03:19:42 |
|
//%std
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline ll read()
{
ll out = 0, fh = 1;
char jp = getchar();
while ((jp > '9' || jp < '0') && jp != '-')
jp = getchar();
if (jp == '-')
fh = -1, jp = getchar();
while (jp >= '0' && jp <= '9')
out = out * 10 + jp - '0', jp = getchar();
return out * fh;
}
void print(ll x)
{
if (x >= 10)
print(x / 10);
putchar('0' + x % 10);
}
void write(ll x, char c)
{
if (x < 0)
putchar('-'), x = -x;
print(x);
putchar(c);
}
bool in(int S, int x)
{
return S >> (x - 2) & 1;
}
int add(int S, int x)
{
if (x > 1)
return S | 1 << (x - 2);
return S;
}
ll dp[19][1 << 8][7][8][9];
int dight[19];
int check(int S, int a, int b, int c)
{
if (!S)
return 1;
if (in(S, 2) && b % 2)
return 0;
if (in(S, 3) && c % 3)
return 0;
if (in(S, 4) && b % 4)
return 0;
if (in(S, 6) && (b % 2 || c % 3))
return 0;
if (in(S, 7) && a)
return 0;
if (in(S, 8) && b)
return 0;
if (in(S, 9) && c)
return 0;
return 1;
}
ll dfs(int k, int S, int a, int b, int c, int lim)
{
if (k < 0)
return check(S, a, b, c);
if (!lim && dp[k][S][a][b][c] != -1)
return dp[k][S][a][b][c];
ll res = 0;
int mx = lim ? dight[k] : 9;
for (int i = 0; i <= mx; ++i)
{
if (k == 0 && in(S, 5) && i != 5 && i != 0)
continue;
res += dfs(k - 1, add(S, i), (a * 10 + i) % 7, (b * 10 + i) % 8, (c * 10 + i) % 9, lim && (i == mx));
}
if (!lim)
dp[k][S][a][b][c] = res;
return res;
}
ll calc(ll x)
{
for (int i = 0; i <= 18; ++i)
{
dight[i] = x % 10;
x /= 10;
}
return dfs(18, 0, 0, 0, 0, 1);
}
void solve()
{
ll l = read(), r = read();
ll ans = calc(r) - calc(l - 1);
write(ans, '\n');
}
int main()
{
memset(dp, -1, sizeof dp);
int T = read();
while (T--)
solve();
return 0;
}
Click to see test details