QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #322689 | #7954. Special Numbers | sgweo8ys | WA | 103ms | 232116kb | C++14 | 4.4kb | 2024-02-07 15:47:33 | 2024-02-07 15:47:33 |
Judging History
answer
#include <bits/stdc++.h>
#define int __int128
using namespace std;
typedef __int128 LL;
const int p = 1000000007;
int add(int x, int y) { return x + y < p ? x + y : x + y - p; }
LL k, k2, k3, k5, k7, pw9[30];
LL f[2][2][2][65][45][25][25], v[25], n;
LL g[2][2][2][2];
int val[10][4] = {
{0, 0, 0, 0},
{0, 0, 0, 0},
{1, 0, 0, 0},
{0, 1, 0, 0},
{2, 0, 0, 0},
{0, 0, 1, 0},
{1, 1, 0, 0},
{0, 0, 0, 1},
{3, 0, 0, 0},
{0, 2, 0, 0},
};
long long solve(LL mx)
{
memset(f, 0, sizeof(f));
LL c = 0, ans = 0;
n = 0;
while(mx) v[++n] = mx % 10, mx /= 10;
//cout << (n == 21) << endl;
reverse(v + 1, v + n + 1);
f[1][1][1][0][0][0][0] = 1;
for(int i = 1; i <= n; i++){
memset(f[c], 0, sizeof(f[c]));
f[c][0][1][0][0][0][0] = 1;
for(int i2 = 0; i2 <= 3 * n; i2++){
for(int i3 = 0; i3 <= 2 * n; i3++){
for(int i5 = 0; i5 <= n; i5++){
for(int i7 = 0; i7 <= n; i7++){
LL sum = f[c ^ 1][0][0][i2][i3][i5][i7] + f[c ^ 1][0][1][i2][i3][i5][i7] + f[c ^ 1][1][0][i2][i3][i5][i7] + f[c ^ 1][1][1][i2][i3][i5][i7];
if(sum == 0) continue;
for(int x = 1; x <= 9; x++){
int n2 = i2 + val[x][0];
int n3 = i3 + val[x][1];
int n5 = i5 + val[x][2];
int n7 = i7 + val[x][3];
f[c][0][0][n2][n3][n5][n7] = add(f[c][0][0][n2][n3][n5][n7], add(f[c ^ 1][0][0][i2][i3][i5][i7], f[c ^ 1][0][1][i2][i3][i5][i7]));
if(x < v[i]){
f[c][0][0][n2][n3][n5][n7] = add(f[c][0][0][n2][n3][n5][n7], add(f[c ^ 1][1][0][i2][i3][i5][i7], f[c ^ 1][1][1][i2][i3][i5][i7]));
}
if(x == v[i]){
f[c][1][0][n2][n3][n5][n7] = add(f[c][1][0][n2][n3][n5][n7], add(f[c ^ 1][1][0][i2][i3][i5][i7], f[c ^ 1][1][1][i2][i3][i5][i7]));
}
}
}
}
}
}
c ^= 1;
}
for(int i2 = k2; i2 <= 3 * n; i2++){
for(int i3 = k3; i3 <= 2 * n; i3++){
for(int i5 = k5; i5 <= n; i5++){
for(int i7 = k7; i7 <= n; i7++){
ans += f[c ^ 1][0][0][i2][i3][i5][i7];
ans += f[c ^ 1][0][1][i2][i3][i5][i7];
ans += f[c ^ 1][1][0][i2][i3][i5][i7];
ans += f[c ^ 1][1][1][i2][i3][i5][i7];
ans %= p;
}
}
}
}
memset(g, 0, sizeof(g));
c = 1;
g[0][1][1][0] = 1;
for(int i = 1; i <= n; i++){
memset(g[c], 0, sizeof(g[c]));
g[c][1][0][0] = 1;
g[c][0][0][0] += (g[c ^ 1][0][0][0] + g[c ^ 1][1][0][0]) * 9;
g[c][0][0][1] += g[c ^ 1][0][0][0] + g[c ^ 1][0][0][1];
g[c][0][0][0] %= p, g[c][0][0][1] %= p;
g[c][0][0][0] += (g[c ^ 1][0][1][0] + g[c ^ 1][1][1][0]) * max(v[i] - 1, (__int128)0ll);
if(v[i] > 0) g[c][0][0][1] += g[c ^ 1][0][1][0] + g[c ^ 1][0][1][1];
g[c][0][0][0] %= p, g[c][0][0][1] %= p;
if(v[i] > 0) g[c][0][1][0] += g[c ^ 1][0][1][0] + g[c ^ 1][1][1][0];
if(v[i] == 0) g[c][0][1][1] += g[c ^ 1][0][1][0] + g[c ^ 1][0][1][1];
g[c][0][1][0] %= p, g[c][0][1][1] %= p;
c ^= 1;
}
ans += g[c ^ 1][0][0][1] + g[c ^ 1][0][1][1] + g[c ^ 1][1][0][1] + g[c ^ 1][1][1][1];
ans %= p;
//cout << ans << endl << endl;
return ans;
}
inline LL read()
{
LL x = 0, f = 1;
char c = getchar();
while(c < '0' || c > '9') { if(c == '-') f = -1; c = getchar(); }
while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
return x * f;
}
signed main()
{
ios :: sync_with_stdio(false);
LL l, r;
k = read(), l = read(), r = read();
while(k % 2 == 0) k2++, k /= 2;
while(k % 3 == 0) k3++, k /= 3;
while(k % 5 == 0) k5++, k /= 5;
while(k % 7 == 0) k7++, k /= 7;
if(k > 1) return cout << "0\n", 0;
pw9[0] = 1;
for(int i = 1; i <= 20; i++) pw9[i] = pw9[i - 1] * 9 % p;
cout << (long long)(((solve(r) - solve(l - 1)) % p + p) % p) << endl;
return 0;
}
/*
1 100000000000000000000 100000000000000000000
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 47ms
memory: 232112kb
input:
5 1 20
output:
4
result:
ok single line: '4'
Test #2:
score: 0
Accepted
time: 79ms
memory: 232048kb
input:
5 50 100
output:
19
result:
ok single line: '19'
Test #3:
score: 0
Accepted
time: 58ms
memory: 232100kb
input:
15 11 19
output:
0
result:
ok single line: '0'
Test #4:
score: -100
Wrong Answer
time: 103ms
memory: 232116kb
input:
1 100 100000
output:
74629
result:
wrong answer 1st lines differ - expected: '99901', found: '74629'