QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#302272 | #7954. Special Numbers | mshcherba# | WA | 347ms | 13664kb | C++20 | 2.1kb | 2024-01-10 18:19:56 | 2024-01-10 18:19:56 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define RFOR(i, a, b) for(int i = (a) - 1; i >= (b); i--)
#define SZ(a) int(a.size())
#define ALL(a) a.begin(), a.end()
#define PB push_back
#define MP make_pair
#define F first
#define S second
typedef long long LL;
typedef vector<int> VI;
typedef pair<int, int> PII;
typedef double db;
const int mod = 1'000'000'007;
const int p[4] = {2, 3, 5, 7};
void updAdd(int& a, int b)
{
a += b;
if (a >= mod)
a -= mod;
}
void updSub(int& a, int b)
{
a -= b;
if (a < 0)
a += mod;
}
int alpha[4];
array<int, 4> bet[10];
int f(LL n)
{
VI digits;
while (n > 0)
{
digits.PB(n % 10);
n /= 10;
}
reverse(ALL(digits));
map<array<int, 4>, int> dp[2][2];
FOR(d, 1, digits[0] + 1)
{
dp[d == digits[0]][0][bet[d]] = 1;
}
FOR(i, 1, SZ(digits))
{
map<array<int, 4>, int> ndp[2][2];
FOR(d, 1, 10)
{
ndp[0][0][bet[d]] = 1;
}
FOR(v, 0, 2)
{
FOR(wz, 0, 2)
{
for (const auto& [be, cnt] : dp[v][wz])
{
FOR(d, 0, 10)
{
if (v && d > digits[i])
break;
array<int, 4> nbe = be;
FOR(j, 0, 4)
nbe[j] += bet[d][j];
updAdd(ndp[v && d == digits[i]][wz || d == 0][nbe], cnt);
}
}
}
}
FOR(v, 0, 2)
FOR(wz, 0, 2)
dp[v][wz] = ndp[v][wz];
}
int res = 0;
FOR(v, 0, 2)
{
FOR(wz, 0, 2)
{
for (const auto& [be, cnt] : dp[v][wz])
{
bool ok = true;
FOR(j, 0, 4)
ok &= be[j] >= alpha[j];
if (wz || ok)
{
updAdd(res, cnt);
}
}
}
}
return res;
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout << fixed << setprecision(15);
LL k, l, r;
cin >> k >> l >> r;
FOR(i, 0, 4)
{
while (k % p[i] == 0)
{
k /= p[i];
alpha[i]++;
}
}
FOR(d, 1, 10)
{
int cur = d;
FOR(i, 0, 4)
{
while (cur % p[i] == 0)
{
cur /= p[i];
bet[d][i]++;
}
}
}
int ans = f(r);
if (l > 1)
updSub(ans, f(l - 1));
cout << ans << "\n";
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3756kb
input:
5 1 20
output:
4
result:
ok single line: '4'
Test #2:
score: 0
Accepted
time: 0ms
memory: 3604kb
input:
5 50 100
output:
19
result:
ok single line: '19'
Test #3:
score: 0
Accepted
time: 0ms
memory: 3760kb
input:
15 11 19
output:
0
result:
ok single line: '0'
Test #4:
score: 0
Accepted
time: 1ms
memory: 3868kb
input:
1 100 100000
output:
99901
result:
ok single line: '99901'
Test #5:
score: 0
Accepted
time: 0ms
memory: 3820kb
input:
1 1 1
output:
1
result:
ok single line: '1'
Test #6:
score: 0
Accepted
time: 1ms
memory: 3676kb
input:
10 800 43021
output:
23570
result:
ok single line: '23570'
Test #7:
score: -100
Wrong Answer
time: 347ms
memory: 13664kb
input:
1125899906842624 1 100000000000000000000
output:
566570801
result:
wrong answer 1st lines differ - expected: '555058180', found: '566570801'