QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #641826 | #3089. Harsh Comments | ohwphil | TL | 981ms | 11380kb | Python3 | 995b | 2024-10-15 00:54:54 | 2024-10-15 00:54:54 |
Judging History
answer
MOD=119<<23|1
N,M=map(int,input().split())
*a_i,=map(int,input().split())
*b_i,=map(int,input().split())
sum_a=sum(a_i)
sum_b=sum(b_i)
inv_sum=pow(sum_a+sum_b,-1,MOD)
knapsack=[0]*10001
knapsack[0]=1
for a in a_i:
for i in range(10000-a,-1,-1):
if knapsack[i]:
knapsack[i+a]=(knapsack[i+a]-knapsack[i])%MOD
final_coeffs=[0]*10001
for a in a_i:
temp_knapsack=knapsack[:]
for i in range(10000-a,-1,-1):
temp_knapsack[i]=(temp_knapsack[i]+temp_knapsack[i+a])%MOD
temp_knapsack[i+a]=(MOD-temp_knapsack[i+a])%MOD
temp_knapsack=temp_knapsack[a:]
for i in range(len(temp_knapsack)):
final_coeffs[i]=(final_coeffs[i]+temp_knapsack[sum_a-a-i]*a)%MOD
ans=0
for i in range(10001):
if final_coeffs[i]:
ans=(ans+final_coeffs[i]*pow(sum_a-i,-1,MOD)*(N+M))%MOD
for b in b_i:
for i in range(10001):
if final_coeffs[i]:
ans=(ans-final_coeffs[i]*pow(sum_a-i+b,-1,MOD))%MOD
print(ans)
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 804ms
memory: 11160kb
input:
95 100 61 6 36 49 69 67 89 27 65 22 60 21 66 80 78 31 25 15 83 20 62 20 90 6 6 30 45 2 32 30 74 31 80 11 40 80 41 17 31 61 32 21 15 14 55 71 55 13 44 10 26 98 64 4 64 96 92 61 89 39 84 30 12 79 13 30 44 81 97 11 9 68 4 17 30 76 40 58 1 84 36 26 3 30 24 14 90 6 6 38 1 9 93 5 3 1426110 1643513 365571 ...
output:
241078495
result:
ok single line: '241078495'
Test #2:
score: 0
Accepted
time: 914ms
memory: 11308kb
input:
97 92 12 48 34 55 51 75 24 97 68 38 41 62 29 22 62 81 68 54 46 40 76 29 68 18 32 68 92 48 80 69 91 30 25 7 49 36 49 24 8 85 27 27 48 86 19 88 11 57 82 42 66 6 38 25 47 36 60 46 100 98 28 4 22 95 69 45 51 13 28 13 6 61 94 18 13 64 99 76 41 71 3 45 25 97 84 62 8 25 41 15 94 61 34 68 34 85 28 6737543 9...
output:
517480317
result:
ok single line: '517480317'
Test #3:
score: 0
Accepted
time: 820ms
memory: 11256kb
input:
90 100 58 63 24 4 57 21 34 30 28 28 59 50 57 59 19 89 78 62 9 89 62 55 4 22 23 89 77 12 85 50 5 51 44 39 19 79 34 32 8 40 18 75 22 72 64 41 99 63 82 63 69 40 82 27 43 14 63 37 15 49 9 3 34 85 88 73 92 46 46 96 23 88 21 81 77 33 98 13 1 14 12 2 84 73 67 18 58 98 31 5 9393346 5675925 3595318 1426237 8...
output:
699286815
result:
ok single line: '699286815'
Test #4:
score: 0
Accepted
time: 905ms
memory: 11196kb
input:
96 93 58 44 81 20 11 81 88 90 1 6 66 43 77 10 98 63 16 61 76 88 100 46 14 36 26 14 1 52 62 94 26 69 86 8 76 35 79 13 51 44 81 29 95 89 10 65 99 83 91 52 25 70 92 36 86 89 55 14 24 61 74 32 82 85 83 69 25 28 4 18 3 58 30 57 72 69 56 75 83 8 60 43 41 22 8 7 46 99 100 70 99 54 11 6 4 8 5651855 7218847 ...
output:
83316870
result:
ok single line: '83316870'
Test #5:
score: 0
Accepted
time: 942ms
memory: 11184kb
input:
96 98 75 67 12 51 74 19 73 91 69 88 11 37 91 19 26 30 47 35 51 25 38 95 31 6 76 98 47 6 38 20 3 70 69 41 47 52 88 15 1 17 54 72 61 84 16 10 16 42 56 72 99 59 3 26 62 32 75 43 20 91 15 72 83 67 10 26 28 66 92 75 59 79 32 45 14 66 38 71 85 44 65 68 73 29 68 11 24 55 68 9 97 85 10 66 55 35 176095 85776...
output:
857493246
result:
ok single line: '857493246'
Test #6:
score: 0
Accepted
time: 923ms
memory: 11208kb
input:
90 98 15 7 56 2 86 44 15 76 40 96 50 96 4 78 18 64 78 21 46 97 66 3 48 31 93 81 92 66 48 37 62 45 41 26 67 93 33 76 73 94 97 94 61 86 57 85 22 92 12 64 12 5 61 97 53 62 25 58 2 33 37 60 58 72 7 10 21 78 96 37 65 58 66 14 97 80 83 17 59 62 23 43 18 75 30 39 23 37 23 20 8536726 445360 6549586 8871047 ...
output:
518246325
result:
ok single line: '518246325'
Test #7:
score: 0
Accepted
time: 816ms
memory: 11300kb
input:
90 96 86 30 40 86 7 11 65 84 34 54 29 56 85 73 34 35 95 45 44 84 11 86 7 13 14 25 88 44 46 61 20 59 1 81 18 93 36 14 79 81 21 3 72 24 81 72 89 84 46 62 64 14 26 43 40 94 38 16 95 23 5 60 13 92 29 90 61 7 43 52 53 55 66 83 77 100 48 52 28 35 100 72 47 93 33 2 75 4 1 55 6738276 5286038 7332547 8769210...
output:
831790358
result:
ok single line: '831790358'
Test #8:
score: 0
Accepted
time: 874ms
memory: 11188kb
input:
98 99 70 65 55 55 14 3 58 55 51 97 37 4 62 14 36 30 79 46 77 24 2 10 79 47 40 41 90 1 100 99 45 86 78 45 60 18 12 68 20 41 61 5 64 77 18 41 34 75 3 72 57 43 41 38 11 76 40 32 94 72 16 80 55 1 1 68 1 93 4 94 17 59 44 20 21 54 73 31 68 57 7 99 32 56 6 95 28 95 51 30 91 62 50 36 37 38 9 7 9592645 15178...
output:
404335437
result:
ok single line: '404335437'
Test #9:
score: 0
Accepted
time: 882ms
memory: 11336kb
input:
99 90 85 55 99 43 16 33 74 52 85 63 75 99 36 30 26 3 64 56 52 62 49 31 45 61 59 24 17 42 59 43 99 75 65 36 30 2 51 90 8 8 9 37 5 83 45 31 28 90 6 91 23 43 75 45 97 40 54 95 94 8 95 60 18 28 91 30 57 50 18 96 61 4 94 92 22 77 98 55 43 54 11 28 89 69 70 95 8 15 35 44 2 8 71 16 95 29 78 78 9 9492475 83...
output:
369387451
result:
ok single line: '369387451'
Test #10:
score: 0
Accepted
time: 830ms
memory: 11312kb
input:
91 95 6 32 87 94 72 81 100 11 84 75 16 99 19 28 8 51 49 24 76 95 90 81 39 56 24 41 90 76 38 22 50 5 47 14 28 10 8 26 53 77 58 16 60 95 67 68 37 71 88 8 2 33 2 18 59 36 90 65 29 17 55 9 25 10 61 4 62 38 63 66 43 10 59 69 45 15 72 60 35 57 35 76 52 77 65 6 20 83 87 63 88 3998713 866847 4907031 9455818...
output:
967893024
result:
ok single line: '967893024'
Test #11:
score: 0
Accepted
time: 932ms
memory: 11236kb
input:
100 96 65 34 17 96 68 24 98 28 82 1 40 89 1 11 18 94 81 69 85 12 67 41 53 67 65 53 47 32 83 48 27 59 64 20 59 33 8 72 98 2 7 97 71 5 41 66 41 49 15 24 68 9 90 45 55 41 36 46 48 71 100 98 59 19 73 63 17 93 99 98 72 34 65 54 71 52 37 96 36 20 92 34 70 68 71 16 41 75 92 45 99 37 46 85 5 25 76 48 82 25 ...
output:
54155933
result:
ok single line: '54155933'
Test #12:
score: 0
Accepted
time: 858ms
memory: 11380kb
input:
91 93 86 71 92 31 73 86 76 64 88 12 41 31 34 96 11 58 40 51 69 31 50 61 96 72 65 60 78 51 75 50 68 68 35 60 5 69 47 33 74 23 66 61 94 5 50 48 24 61 69 2 70 76 55 88 42 27 93 40 85 53 50 81 80 17 15 32 81 70 2 95 99 20 90 5 46 92 23 77 83 3 35 40 40 23 62 29 89 77 22 91 60 8467997 6585759 3282041 844...
output:
185536410
result:
ok single line: '185536410'
Test #13:
score: 0
Accepted
time: 962ms
memory: 11236kb
input:
100 100 92 49 94 91 16 21 57 13 33 76 15 72 5 32 55 68 56 10 39 40 58 1 75 21 73 59 7 80 10 75 45 58 98 59 82 68 44 64 45 100 40 16 73 88 52 76 38 24 83 57 46 66 60 9 18 42 57 63 88 72 3 34 89 1 13 26 10 53 88 56 98 97 41 10 9 52 80 49 91 92 45 1 34 69 6 22 78 83 81 30 66 88 14 71 26 8 96 34 70 76 9...
output:
740279557
result:
ok single line: '740279557'
Test #14:
score: 0
Accepted
time: 877ms
memory: 11308kb
input:
94 94 15 28 64 94 82 69 52 83 69 88 35 27 44 55 56 52 58 15 17 6 1 78 91 90 61 4 54 32 26 65 39 22 22 60 21 98 12 10 58 17 6 56 22 86 75 93 8 68 99 48 92 12 9 56 5 85 32 23 61 68 18 74 58 49 94 96 28 73 31 4 79 50 4 84 61 1 38 62 44 82 13 80 62 56 6 90 68 46 50 12 14 74 88 92 6759174 1053571 4759573...
output:
595691002
result:
ok single line: '595691002'
Test #15:
score: 0
Accepted
time: 941ms
memory: 11304kb
input:
98 93 61 80 73 13 32 6 75 69 86 22 52 82 21 88 50 77 19 72 99 34 79 25 96 44 28 3 53 55 7 39 90 96 67 97 1 15 90 93 79 12 16 15 26 35 35 81 65 80 48 88 83 77 39 30 82 46 11 95 9 41 75 20 46 1 33 92 40 98 49 88 58 97 8 90 47 59 93 24 100 100 93 13 65 36 96 91 24 78 4 49 14 91 68 74 98 9 90 36 3796974...
output:
468439547
result:
ok single line: '468439547'
Test #16:
score: 0
Accepted
time: 926ms
memory: 11376kb
input:
98 98 100 83 13 6 15 17 53 88 18 69 57 3 3 24 45 79 19 74 90 91 78 100 40 63 50 27 62 41 40 67 14 31 88 11 75 22 54 91 95 94 16 97 38 50 52 5 8 34 68 22 16 75 87 51 34 24 34 1 36 37 67 67 17 25 98 39 43 97 24 12 56 76 28 31 78 29 61 43 100 49 77 4 83 77 84 78 92 48 100 94 16 83 24 92 21 29 88 38 669...
output:
293170261
result:
ok single line: '293170261'
Test #17:
score: 0
Accepted
time: 892ms
memory: 11332kb
input:
98 100 85 16 74 13 17 81 49 41 32 66 99 62 5 31 53 61 20 23 15 65 45 8 2 41 10 66 86 11 49 70 4 36 36 26 48 30 22 35 49 42 50 38 89 22 20 75 2 83 17 19 55 74 9 55 95 46 19 29 87 100 87 86 96 34 90 63 79 14 75 8 38 22 42 42 30 41 7 8 36 48 61 18 55 32 68 50 51 32 18 72 72 72 28 10 74 88 14 81 355824 ...
output:
351953473
result:
ok single line: '351953473'
Test #18:
score: 0
Accepted
time: 894ms
memory: 11236kb
input:
91 92 67 46 62 24 69 91 71 16 61 87 61 7 9 21 15 13 34 57 37 75 51 41 33 48 30 100 73 44 86 9 66 96 80 51 64 52 4 63 64 13 57 76 65 40 7 67 81 71 93 60 59 24 81 83 28 96 85 13 25 42 16 34 24 8 60 63 44 68 37 49 36 25 87 11 25 72 1 59 87 86 38 73 55 70 45 47 13 68 15 19 72 9721630 5765285 970575 9508...
output:
363920783
result:
ok single line: '363920783'
Test #19:
score: 0
Accepted
time: 981ms
memory: 11296kb
input:
100 100 47 54 15 31 48 47 11 57 39 76 76 25 87 31 100 32 95 57 10 100 61 52 44 4 53 56 48 100 90 26 15 74 40 81 15 48 91 75 89 87 21 98 8 51 38 83 65 10 33 57 42 72 81 39 87 19 46 51 7 90 77 47 30 85 81 23 76 46 80 28 73 25 73 17 93 90 100 85 63 40 94 23 13 57 25 47 63 55 11 52 40 78 29 38 78 55 12 ...
output:
335891263
result:
ok single line: '335891263'
Test #20:
score: 0
Accepted
time: 922ms
memory: 11244kb
input:
96 96 31 42 84 21 82 67 11 91 79 14 52 99 45 28 42 78 100 4 83 25 98 2 45 74 16 46 38 70 86 40 91 46 52 36 23 16 10 44 70 37 67 81 74 45 38 67 42 7 1 20 30 12 33 7 10 56 19 79 70 25 29 56 70 74 79 21 19 21 15 1 62 96 94 49 14 81 6 9 84 91 75 84 96 26 97 90 71 43 88 63 82 84 72 51 100 66 9486425 2014...
output:
211786857
result:
ok single line: '211786857'
Test #21:
score: 0
Accepted
time: 880ms
memory: 11220kb
input:
99 90 79 41 59 64 7 5 11 76 98 2 66 75 96 2 30 85 81 20 1 14 56 94 29 7 96 5 91 42 37 19 98 62 9 58 29 25 60 5 34 45 56 20 23 91 12 78 90 60 29 5 16 84 7 97 35 81 20 43 39 52 40 83 87 80 14 98 37 69 77 26 28 93 69 15 64 9 9 24 28 37 94 68 42 16 23 58 56 12 48 35 73 87 75 10 83 77 74 14 46 7838938 56...
output:
520580054
result:
ok single line: '520580054'
Test #22:
score: 0
Accepted
time: 890ms
memory: 11220kb
input:
95 94 28 21 78 39 88 84 55 25 15 90 54 26 60 68 69 8 73 34 51 55 6 65 69 82 73 87 80 12 52 9 29 31 6 58 79 8 79 61 6 11 91 85 16 13 80 65 18 96 92 5 100 5 16 14 82 28 45 13 99 91 31 29 84 47 14 88 36 93 81 92 25 2 22 63 100 84 62 77 93 98 59 56 17 25 59 89 25 18 97 34 72 66 55 74 40 9795961 9537920 ...
output:
176259918
result:
ok single line: '176259918'
Test #23:
score: 0
Accepted
time: 849ms
memory: 11236kb
input:
92 90 85 98 73 28 92 73 55 75 1 74 47 85 18 65 52 65 28 47 30 73 61 14 88 22 85 92 47 83 76 32 64 90 91 61 22 5 30 50 5 46 45 43 41 51 98 24 31 44 73 57 91 18 10 38 60 64 23 52 16 81 71 49 39 59 27 35 76 72 100 57 53 75 19 84 18 73 12 65 45 9 12 63 30 96 46 63 46 25 72 93 53 31 631810 3353531 378572...
output:
233638804
result:
ok single line: '233638804'
Test #24:
score: 0
Accepted
time: 903ms
memory: 11316kb
input:
95 93 80 56 29 58 33 33 95 98 58 37 69 72 46 83 42 69 1 49 15 2 90 2 85 27 54 32 21 41 3 64 75 6 5 91 95 25 48 100 76 80 72 7 51 46 6 52 12 49 5 58 18 65 46 55 63 28 52 58 82 65 25 38 6 78 82 44 22 32 55 8 15 41 20 38 23 78 96 30 82 89 66 53 60 46 31 84 74 77 23 59 89 40 58 7 98 8370179 4231583 2341...
output:
401168598
result:
ok single line: '401168598'
Test #25:
score: 0
Accepted
time: 917ms
memory: 11244kb
input:
96 96 59 26 8 11 50 53 69 16 47 66 95 1 90 92 1 27 58 39 48 51 95 57 18 56 36 65 79 93 28 76 38 82 73 80 70 36 51 76 57 29 58 11 45 72 71 53 94 97 49 77 71 83 84 8 56 50 55 91 85 73 85 75 43 12 48 83 86 60 57 78 85 70 51 40 29 92 30 47 67 59 53 27 58 38 23 36 97 93 8 23 22 25 77 41 87 85 9059923 399...
output:
490574780
result:
ok single line: '490574780'
Test #26:
score: -100
Time Limit Exceeded
input:
100 92 92 82 25 18 57 66 89 55 87 99 63 85 74 27 82 26 87 31 96 29 40 67 52 88 33 13 1 93 37 21 87 40 63 87 9 2 67 100 8 53 95 72 40 32 62 61 18 9 50 11 96 65 99 94 43 60 44 69 96 66 31 16 86 69 6 98 86 31 29 58 49 94 81 51 81 6 98 99 19 18 73 22 41 98 77 76 30 35 28 16 78 86 21 27 76 1 77 37 14 66 ...
output:
56160744