QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #711392 | #7954. Special Numbers | kizen# | WA | 860ms | 116276kb | C++20 | 4.3kb | 2024-11-05 10:24:31 | 2024-11-05 10:24:32 |
Judging History
answer
#include <bits/stdc++.h>
#ifndef LOCAL
#pragma GCC optimize("O3")
#pragma GCC target("avx2")
#endif
#define sz(v) ((int)v.size())
#define all(v) v.begin(), v.end()
#define pb push_back
#define pi array<int, 2>
using namespace std;
#define int long long
int dp[60][40][30][25][2][2];
int ndp[60][40][30][25][2][2];
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
int k; cin >> k;
string l, r; cin >> l >> r;
vector<int> p = {2, 3, 5, 7};
const int mod = (int)1e9 + 7;
array<int, 4> kid = {0, 0, 0, 0};
for(int j = 0; j < 4; ++j){
while(k % p[j] == 0){
++kid[j];
k /= p[j];
}
}
auto sol = [&](string s, int less){
memset(dp, 0, sizeof(dp));
dp[0][0][0][0][0][0] = 1;
int rv = 0;
array<int, 4> id;
int zcnt = 0;
for(int i = 0; i < sz(s); ++i){
int v = s[i] - '0';
(zcnt *= 10) %= mod;
(zcnt += v) %= mod;
memset(ndp, 0, sizeof(ndp));
for(id[0] = 0; id[0] < 60; ++id[0]){
for(id[1] = 0; id[1] < 40; ++id[1]){
for(id[2] = 0; id[2] < 30; ++id[2]){
for(id[3] = 0; id[3] < 25; ++id[3]){
for(int j = 0; j < 2; ++j){
for(int nz = 0; nz < 2; ++nz){
if(!dp[id[0]][id[1]][id[2]][id[3]][j][nz]) continue;
for(int now = 0; now < 10; ++now){
if(!j && now > v) break;
if(nz && !now) continue;
// cout << i << ' ' << id[0] << ' ' << id[1] << ' ' << id[2] << ' ' << id[3] << ' ' << j << ' ' << now << endl;
auto nid = id;
if(now){
for(int k = 0; k < 4; ++k){
int imsi = now;
while(imsi % p[k] == 0){
++nid[k];
imsi /= p[k];
}
}
}
(ndp[nid[0]][nid[1]][nid[2]][nid[3]][j | (now < v)][nz | !!now] += dp[id[0]][id[1]][id[2]][id[3]][j][nz]) %= mod;
}
}
}
}
}
}
}
for(id[0] = 0; id[0] < 60; ++id[0]){
for(id[1] = 0; id[1] < 40; ++id[1]){
for(id[2] = 0; id[2] < 30; ++id[2]){
for(id[3] = 0; id[3] < 25; ++id[3]){
for(int j = 0; j < 2; ++j){
for(int nz = 0; nz < 2; ++nz){
dp[id[0]][id[1]][id[2]][id[3]][j][nz] = ndp[id[0]][id[1]][id[2]][id[3]][j][nz];
}
}
}
}
}
}
}
if(less) (zcnt += mod - 1) %= mod;
// cout << zcnt << endl;
for(id[0] = 0; id[0] < 60; ++id[0]){
for(id[1] = 0; id[1] < 40; ++id[1]){
for(id[2] = 0; id[2] < 30; ++id[2]){
for(id[3] = 0; id[3] < 25; ++id[3]){
for(int j = less; j < 2; ++j){
zcnt -= dp[id[0]][id[1]][id[2]][id[3]][j][1];
if(k == 1 && id[0] >= kid[0] && id[1] >= kid[1] && id[2] >= kid[2] && id[3] >= kid[3]){
(rv += dp[id[0]][id[1]][id[2]][id[3]][j][1]) %= mod;
}
}
}
}
}
}
(rv += zcnt) %= mod;
// cout << zcnt << ' ' << rv << endl;
return rv;
};
int ans = (sol(r, 0) - sol(l, 1) + mod) % mod;
cout << ans;
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 85ms
memory: 116124kb
input:
5 1 20
output:
4
result:
ok single line: '4'
Test #2:
score: 0
Accepted
time: 114ms
memory: 116048kb
input:
5 50 100
output:
19
result:
ok single line: '19'
Test #3:
score: 0
Accepted
time: 109ms
memory: 116052kb
input:
15 11 19
output:
0
result:
ok single line: '0'
Test #4:
score: 0
Accepted
time: 209ms
memory: 116056kb
input:
1 100 100000
output:
99901
result:
ok single line: '99901'
Test #5:
score: 0
Accepted
time: 76ms
memory: 116048kb
input:
1 1 1
output:
1
result:
ok single line: '1'
Test #6:
score: 0
Accepted
time: 182ms
memory: 116112kb
input:
10 800 43021
output:
23570
result:
ok single line: '23570'
Test #7:
score: 0
Accepted
time: 482ms
memory: 116056kb
input:
1125899906842624 1 100000000000000000000
output:
555058180
result:
ok single line: '555058180'
Test #8:
score: 0
Accepted
time: 848ms
memory: 116064kb
input:
187500000 5941554024261918062 17356601866920567143
output:
679191360
result:
ok single line: '679191360'
Test #9:
score: 0
Accepted
time: 825ms
memory: 116108kb
input:
1555848 157165614890794026 49792374427566422833
output:
588832126
result:
ok single line: '588832126'
Test #10:
score: 0
Accepted
time: 859ms
memory: 116116kb
input:
53814924637488000 8378901287491856069 46225409092942057365
output:
964965504
result:
ok single line: '964965504'
Test #11:
score: 0
Accepted
time: 852ms
memory: 116052kb
input:
11814720750000000 8152927138245188051 35351923956338524619
output:
183963359
result:
ok single line: '183963359'
Test #12:
score: 0
Accepted
time: 860ms
memory: 116116kb
input:
6453888000000 4334845344448208535 35982793193772682339
output:
570114022
result:
ok single line: '570114022'
Test #13:
score: 0
Accepted
time: 843ms
memory: 116276kb
input:
90071357282285400 7893548167754114409 27099084703937108974
output:
869822186
result:
ok single line: '869822186'
Test #14:
score: -100
Wrong Answer
time: 824ms
memory: 116100kb
input:
45571065750000 177160749596350425 98884377930460959454
output:
607698666
result:
wrong answer 1st lines differ - expected: '607698665', found: '607698666'