QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#380541 | #8565. Basic Blooms | ucup-team1766# | TL | 1988ms | 49728kb | Python3 | 660b | 2024-04-07 05:39:22 | 2024-04-07 05:39:23 |
Judging History
answer
from heapq import *
MOD = 998244353
def sqrt(n):
return n // 10000000000
flowers = [0] * 1000001
heap = []
for b in range(2,17):
for d in range(1,b):
heappush(heap, [d, b, d, d])
i = 1
while i < len(flowers):
v,b,d,m = heappop(heap)
if m != flowers[i-1]:
flowers[i] = m
i+=1
heappush(heap, [v*b+d, b, d, (m*b+d)%MOD])
if i % 100000 == 0:
for j in range(len(heap)):
heap[j][0] //= sqrt(heap[0][0])
for i in range(1,len(flowers)):
flowers[i] = (flowers[i] + flowers[i-1]) % MOD
t = int(input())
for _ in range(t):
a, b = map(int,input().split())
print(flowers[b]-flowers[a-1])
詳細信息
Test #1:
score: 100
Accepted
time: 1746ms
memory: 49600kb
input:
3 1 2 1 10 15 2000
output:
3 55 736374621
result:
ok 3 number(s): "3 55 736374621"
Test #2:
score: 0
Accepted
time: 1988ms
memory: 49728kb
input:
100000 26 99975 57 99944 28 99973 62 99939 71 99930 25 99976 53 99948 60 99941 73 99928 72 99929 30 99971 7 99994 3 99998 35 99966 73 99928 68 99933 83 99918 37 99964 63 99938 17 99984 34 99967 74 99927 6 99995 3 99998 23 99978 91 99910 39 99962 85 99916 82 99919 17 99984 61 99940 31 99970 44 99957 ...
output:
957904590 358359691 31524403 519690359 208321031 477204717 835715447 186583689 847423322 760952087 25753603 241428916 832623523 232679133 847423322 11425904 640652773 663756612 767901835 356898792 503593019 495288401 265039242 832623523 793754988 389398856 758928836 349243444 158978749 356898792 873...
result:
ok 100000 numbers
Test #3:
score: -100
Time Limit Exceeded
input:
1000000 561662 731870 560627 798415 497930 613164 210084 556894 479283 902738 271881 288854 467622 971733 55854 157477 310152 415183 146385 874852 140599 526659 438420 629148 733746 924626 84146 436790 275793 457537 466464 541539 661070 696519 534866 688272 190259 412401 206392 354525 2344 217676 51...
output:
414317936 622795512 206107194 -507956049 88321319 -116946573 172383030 555135166 -336133390 -805680780 911861587 46830640 701425185 696305318 -238528063 -79263419 -9082314 505443660 -223159909 -907770439 -107842928 147106216 221715003 -32279724 55816243 241034850 -255774163 40939160 -490952554 -1157...