|

General

# Author Problem Lang Verdict Time Memory Sent Judged
84116963 Practice:
JKLover
55D - 22 GNU C++17 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;
{
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;
}
{
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 ans = calc(r) - calc(l - 1);
write(ans, '\n');
}
int main()
{
memset(dp, -1, sizeof dp);
while (T--)
solve();
return 0;
}


?
Time: ? ms, memory: ? KB
Verdict: ?
Input
?
Participant's output
?
?
?
?