QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#322692 | #7954. Special Numbers | sgweo8ys | WA | 654ms | 232328kb | C++14 | 4.7kb | 2024-02-07 15:53:35 | 2024-02-07 15:53:35 |
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;
}
}
}
}
//cout << (long long)ans << endl;
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][1] + g[c ^ 1][1][0][1]) * 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);
g[c][0][0][1] += (g[c ^ 1][0][1][1] + g[c ^ 1][1][1][1]) * 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][1] + g[c ^ 1][1][1][1];
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 << (long long)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 1 109
*/
详细
Test #1:
score: 100
Accepted
time: 51ms
memory: 232252kb
input:
5 1 20
output:
4
result:
ok single line: '4'
Test #2:
score: 0
Accepted
time: 87ms
memory: 232104kb
input:
5 50 100
output:
19
result:
ok single line: '19'
Test #3:
score: 0
Accepted
time: 72ms
memory: 232128kb
input:
15 11 19
output:
0
result:
ok single line: '0'
Test #4:
score: 0
Accepted
time: 105ms
memory: 232132kb
input:
1 100 100000
output:
99901
result:
ok single line: '99901'
Test #5:
score: 0
Accepted
time: 28ms
memory: 232328kb
input:
1 1 1
output:
1
result:
ok single line: '1'
Test #6:
score: 0
Accepted
time: 94ms
memory: 232280kb
input:
10 800 43021
output:
23570
result:
ok single line: '23570'
Test #7:
score: 0
Accepted
time: 386ms
memory: 232316kb
input:
1125899906842624 1 100000000000000000000
output:
555058180
result:
ok single line: '555058180'
Test #8:
score: 0
Accepted
time: 633ms
memory: 232128kb
input:
187500000 5941554024261918062 17356601866920567143
output:
679191360
result:
ok single line: '679191360'
Test #9:
score: 0
Accepted
time: 603ms
memory: 232280kb
input:
1555848 157165614890794026 49792374427566422833
output:
588832126
result:
ok single line: '588832126'
Test #10:
score: 0
Accepted
time: 622ms
memory: 232060kb
input:
53814924637488000 8378901287491856069 46225409092942057365
output:
964965504
result:
ok single line: '964965504'
Test #11:
score: 0
Accepted
time: 645ms
memory: 232084kb
input:
11814720750000000 8152927138245188051 35351923956338524619
output:
183963359
result:
ok single line: '183963359'
Test #12:
score: 0
Accepted
time: 635ms
memory: 232112kb
input:
6453888000000 4334845344448208535 35982793193772682339
output:
570114022
result:
ok single line: '570114022'
Test #13:
score: 0
Accepted
time: 636ms
memory: 232060kb
input:
90071357282285400 7893548167754114409 27099084703937108974
output:
869822186
result:
ok single line: '869822186'
Test #14:
score: 0
Accepted
time: 597ms
memory: 232040kb
input:
45571065750000 177160749596350425 98884377930460959454
output:
607698665
result:
ok single line: '607698665'
Test #15:
score: 0
Accepted
time: 654ms
memory: 232048kb
input:
1128443962982400 6338876482181492537 40931938533793596007
output:
881168270
result:
ok single line: '881168270'
Test #16:
score: 0
Accepted
time: 43ms
memory: 232320kb
input:
1 1 1
output:
1
result:
ok single line: '1'
Test #17:
score: 0
Accepted
time: 625ms
memory: 232096kb
input:
1412793457031250 2410155470167050095 99063185266833009818
output:
399813226
result:
ok single line: '399813226'
Test #18:
score: 0
Accepted
time: 643ms
memory: 232116kb
input:
67722117120000 8909573534349989418 73129289758235281558
output:
898227227
result:
ok single line: '898227227'
Test #19:
score: 0
Accepted
time: 634ms
memory: 232068kb
input:
472055808000 6809917603531307093 27494416416722163137
output:
379198478
result:
ok single line: '379198478'
Test #20:
score: 0
Accepted
time: 650ms
memory: 232108kb
input:
19353600000 8687492345912514346 24058039408337150852
output:
250715555
result:
ok single line: '250715555'
Test #21:
score: 0
Accepted
time: 649ms
memory: 232260kb
input:
47855420020225440 6150828649270625443 84863934988301168136
output:
665186711
result:
ok single line: '665186711'
Test #22:
score: 0
Accepted
time: 645ms
memory: 232100kb
input:
1382400000 9545797804645162278 70441077437727026904
output:
278230087
result:
ok single line: '278230087'
Test #23:
score: 0
Accepted
time: 641ms
memory: 232100kb
input:
816293376 2952089614708276156 10939708785225040670
output:
120954190
result:
ok single line: '120954190'
Test #24:
score: 0
Accepted
time: 644ms
memory: 232108kb
input:
4185097875 1348426133484952253 56617823359794500344
output:
773995224
result:
ok single line: '773995224'
Test #25:
score: 0
Accepted
time: 637ms
memory: 232064kb
input:
5828945117184 7777082394971366991 63470232991138132969
output:
678496908
result:
ok single line: '678496908'
Test #26:
score: 0
Accepted
time: 635ms
memory: 232280kb
input:
16184770560 3869053219872876321 94590086601168840932
output:
168181821
result:
ok single line: '168181821'
Test #27:
score: 0
Accepted
time: 48ms
memory: 232088kb
input:
2 1 12
output:
6
result:
ok single line: '6'
Test #28:
score: 0
Accepted
time: 596ms
memory: 232104kb
input:
30146484375 290228705524339176 51853415145287716863
output:
229436627
result:
ok single line: '229436627'
Test #29:
score: 0
Accepted
time: 624ms
memory: 232312kb
input:
2072513819443200 3726664558969607832 42501102605103061370
output:
947952932
result:
ok single line: '947952932'
Test #30:
score: 0
Accepted
time: 633ms
memory: 232104kb
input:
9920232000000000 4602219263214498291 80783137037024823899
output:
846877519
result:
ok single line: '846877519'
Test #31:
score: 0
Accepted
time: 632ms
memory: 232128kb
input:
97200000000000000 9310820760839688870 35322929083473756214
output:
936587432
result:
ok single line: '936587432'
Test #32:
score: 0
Accepted
time: 640ms
memory: 232144kb
input:
45209390625 5752361069878044328 64635325028527078951
output:
578047592
result:
ok single line: '578047592'
Test #33:
score: 0
Accepted
time: 636ms
memory: 232088kb
input:
54442233216000 2452030574225118723 90982734056131320662
output:
417646585
result:
ok single line: '417646585'
Test #34:
score: 0
Accepted
time: 611ms
memory: 232324kb
input:
1530550080000 7431421026778839808 84825282227911272129
output:
600103842
result:
ok single line: '600103842'
Test #35:
score: 0
Accepted
time: 627ms
memory: 232028kb
input:
13765147361280 4924477486471254843 10002324705150566233
output:
951883713
result:
ok single line: '951883713'
Test #36:
score: 0
Accepted
time: 627ms
memory: 232124kb
input:
59825698242187500 6303744363677706767 91410210495502213963
output:
774734375
result:
ok single line: '774734375'
Test #37:
score: 0
Accepted
time: 624ms
memory: 232108kb
input:
110658879959040 2133591391458550040 48494371567095341228
output:
103505650
result:
ok single line: '103505650'
Test #38:
score: 0
Accepted
time: 66ms
memory: 232112kb
input:
1 3 100
output:
98
result:
ok single line: '98'
Test #39:
score: 0
Accepted
time: 636ms
memory: 232264kb
input:
3160365465600 8968721517098518892 78444481529635953131
output:
364620926
result:
ok single line: '364620926'
Test #40:
score: -100
Wrong Answer
time: 0ms
memory: 3620kb
input:
54838448056132899 4242999884713464056 92948071680698209741
output:
0
result:
wrong answer 1st lines differ - expected: '922087167', found: '0'