QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #302101 | #7954. Special Numbers | mariowong# | WA | 2ms | 40516kb | C++17 | 4.0kb | 2024-01-10 16:16:54 | 2024-01-10 16:16:54 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int MOD = 1e9 + 7;
int primes[] = {2, 3, 5, 7};
// no of ptimes for 1 to 9, starts from 1
int dip[9][4] = {{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}};
int cnt[4], digit[25];
ll f[2][2][57][41][21][25];
ll calc(ll n) {
if (!n) return 0;
ll kt = n;
int m = 0;
stack <int> tt;
while (kt) {
tt.push(kt % 10);
kt /= 10, m++;
}
for (int i = 0; i < m; i++) {
digit[i] = tt.top();
tt.pop();
}
for (int w = 0; w <= cnt[0]; w++) {
for (int x = 0; x <= cnt[1]; x++) {
for (int y = 0; y <= cnt[2]; y++) {
for (int z = 0; z <= cnt[3]; z++) {
f[0][0][w][x][y][z] = f[0][1][w][x][y][z] = 0;
}
}
}
}
f[0][1][0][0][0][0] = 1;
for (int i = 0; i < m; i++) {
int cur = i & 1, nxt = cur ^ 1;
for (int w = 0; w <= cnt[0]; w++) {
for (int x = 0; x <= cnt[1]; x++) {
for (int y = 0; y <= cnt[2]; y++) {
for (int z = 0; z <= cnt[3]; z++) {
f[nxt][0][w][x][y][z] = f[nxt][1][w][x][y][z] = 0;
}
}
}
}
for (int w = 0; w <= cnt[0]; w++) {
for (int x = 0; x <= cnt[1]; x++) {
for (int y = 0; y <= cnt[2]; y++) {
for (int z = 0; z <= cnt[3]; z++) {
//transition for not cur max
for (int tt = 0; tt < 9; tt++) {
int tw = min(w + dip[tt][0], cnt[0]);
int tx = min(x + dip[tt][1], cnt[1]);
int ty = min(y + dip[tt][2], cnt[2]);
int tz = min(z + dip[tt][3], cnt[3]);
f[nxt][0][tw][tx][ty][tz] = (f[nxt][0][tw][tx][ty][tz] + f[cur][0][w][x][y][z]) % MOD;
}
if (i) f[nxt][0][cnt[0]][cnt[1]][cnt[2]][cnt[3]] = (f[nxt][0][cnt[0]][cnt[1]][cnt[2]][cnt[3]] + f[cur][0][w][x][y][z]) % MOD;
//transition for current is max
for (int tt = 0; tt < digit[i] - 1; tt++) {
int tw = min(w + dip[tt][0], cnt[0]);
int tx = min(x + dip[tt][1], cnt[1]);
int ty = min(y + dip[tt][2], cnt[2]);
int tz = min(z + dip[tt][3], cnt[3]);
f[nxt][0][tw][tx][ty][tz] = (f[nxt][0][tw][tx][ty][tz] + f[cur][1][w][x][y][z]) % MOD;
}
if (digit[i] > 0) {
if (i) f[nxt][0][cnt[0]][cnt[1]][cnt[2]][cnt[3]] = (f[nxt][0][cnt[0]][cnt[1]][cnt[2]][cnt[3]] + f[cur][1][w][x][y][z]) % MOD;
int tw = min(w + dip[digit[i] - 1][0], cnt[0]);
int tx = min(x + dip[digit[i] - 1][1], cnt[1]);
int ty = min(y + dip[digit[i] - 1][2], cnt[2]);
int tz = min(z + dip[digit[i] - 1][3], cnt[3]);
f[nxt][1][tw][tx][ty][tz] = (f[nxt][1][tw][tx][ty][tz] + f[cur][1][w][x][y][z]) % MOD;
}
else
f[nxt][1][cnt[0]][cnt[1]][cnt[2]][cnt[3]] = (f[nxt][1][cnt[0]][cnt[1]][cnt[2]][cnt[3]] + f[cur][1][w][x][y][z]) % MOD;
}
}
}
}
// include number that start at this pos
if (i) {
for (int tt = 0; tt < 9; tt++) {
int tw = min(dip[tt][0], cnt[0]);
int tx = min(dip[tt][1], cnt[1]);
int ty = min(dip[tt][2], cnt[2]);
int tz = min(dip[tt][3], cnt[3]);
f[nxt][0][tw][tx][ty][tz] = (f[nxt][0][tw][tx][ty][tz] + 1) % MOD;
}
}
// cout << digit[i] << endl;
// for (int w = 0; w <= cnt[0]; w++) {
// for (int x = 0; x <= cnt[1]; x++) {
// for (int y = 0; y <= cnt[2]; y++) {
// for (int z = 0; z <= cnt[3]; z++) {
// cout << i << ' ' << w << ' ' << x << ' ' << y << ' ' << z << ' ' << f[nxt][0][w][x][y][z] << ' ' << f[nxt][1][w][x][y][z] << endl;
// }
// }
// }
// }
}
return (f[m & 1][0][cnt[0]][cnt[1]][cnt[2]][cnt[3]] + f[m & 1][1][cnt[0]][cnt[1]][cnt[2]][cnt[3]]) % MOD;
}
ll f2[25][10][2];
int main(){
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
ll k, l, r; cin >> k >> l >> r;
ll tk = k;
for (int i = 0; i < 4; i++) {
cnt[i] = 0;
while (tk % primes[i] == 0) {
tk /= primes[i];
cnt[i]++;
}
}
if (tk != 1) {
cnt[3] = 24;
}
ll tans = (calc(r) - calc(l - 1) + MOD) % MOD;
cout << tans << endl;
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 9696kb
input:
5 1 20
output:
4
result:
ok single line: '4'
Test #2:
score: 0
Accepted
time: 0ms
memory: 9708kb
input:
5 50 100
output:
19
result:
ok single line: '19'
Test #3:
score: 0
Accepted
time: 2ms
memory: 9700kb
input:
15 11 19
output:
0
result:
ok single line: '0'
Test #4:
score: 0
Accepted
time: 0ms
memory: 9768kb
input:
1 100 100000
output:
99901
result:
ok single line: '99901'
Test #5:
score: 0
Accepted
time: 1ms
memory: 9704kb
input:
1 1 1
output:
1
result:
ok single line: '1'
Test #6:
score: 0
Accepted
time: 1ms
memory: 9660kb
input:
10 800 43021
output:
23570
result:
ok single line: '23570'
Test #7:
score: -100
Wrong Answer
time: 0ms
memory: 40516kb
input:
1125899906842624 1 100000000000000000000
output:
566570801
result:
wrong answer 1st lines differ - expected: '555058180', found: '566570801'