General
 
 
# 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
→ Source
//%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;
}
?
Time: ? ms, memory: ? KB
Verdict: ?
Input
?
Participant's output
?
Jury's answer
?
Checker comment
?
Diagnostics
?
Click to see test details