Contest Duration: - (local time) (100 minutes) Back to Home

Submission #17617768

Source Code Expand

Copy
```import sys
import numpy as np
import numba
from numba import njit, b1, i4, i8, f8

MOD = 998_244_353

@njit((i8[:], i8), cache=True)
def main(A, K):
S = np.zeros(K + 1, np.int64)
for a in A:
a %= MOD
p = 1
for k in range(0, K + 1):
S[k] += p
S[k] %= MOD
p = p * a % MOD
C = np.zeros((K + 1, K + 1), np.int64)
C[0, 0] = 1
pow2 = np.ones(K + 1, np.int64)
for n in range(1, K + 1):
pow2[n] = pow2[n - 1] * 2 % MOD
for n in range(1, K + 1):
C[n] += C[n - 1]
C[n, 1:] += C[n - 1, :-1]
C[n] %= MOD
for X in range(1, K + 1):
ans = 0
for i in range(X + 1):
ans += C[X, i] * S[i] % MOD * S[X - i] % MOD
ans -= pow2[X] * S[X] % MOD
if ans & 1:
ans += MOD
ans //= 2
ans %= MOD
print(ans)

main(A, K)```

#### Submission Info

Submission Time 2020-10-24 21:20:21+0900 D - Powers maspy Python (3.8.2) 600 1303 Byte AC 782 ms 110576 KB

#### Judge Result

Set Name Sample All
Score / Max Score 0 / 0 600 / 600
Status
 AC × 3
 AC × 30
Set Name Test Cases
Sample 00_sample_01, 00_sample_02, 00_sample_03
All 00_sample_01, 00_sample_02, 00_sample_03, 10_small_01, 10_small_02, 10_small_03, 10_small_04, 10_small_05, 10_small_06, 10_small_07, 10_small_08, 10_small_09, 10_small_10, 20_random_01, 20_random_02, 20_random_03, 20_random_04, 20_random_05, 20_random_06, 20_random_07, 20_random_08, 20_random_09, 20_random_10, 30_max_01, 30_max_02, 30_max_03, 30_max_04, 30_max_05, 31_max_01, 31_max_02
Case Name Status Exec Time Memory
00_sample_01 AC 496 ms 107192 KB
00_sample_02 AC 467 ms 106496 KB
00_sample_03 AC 457 ms 105956 KB
10_small_01 AC 461 ms 106476 KB
10_small_02 AC 459 ms 106996 KB
10_small_03 AC 461 ms 107556 KB
10_small_04 AC 463 ms 107036 KB
10_small_05 AC 458 ms 106364 KB
10_small_06 AC 463 ms 107328 KB
10_small_07 AC 465 ms 106392 KB
10_small_08 AC 465 ms 105952 KB
10_small_09 AC 467 ms 107184 KB
10_small_10 AC 470 ms 106640 KB
20_random_01 AC 560 ms 108236 KB
20_random_02 AC 578 ms 107992 KB
20_random_03 AC 472 ms 107968 KB
20_random_04 AC 592 ms 108296 KB
20_random_05 AC 521 ms 109128 KB
20_random_06 AC 659 ms 108932 KB
20_random_07 AC 521 ms 108272 KB
20_random_08 AC 635 ms 109256 KB
20_random_09 AC 487 ms 109644 KB
20_random_10 AC 532 ms 109624 KB
30_max_01 AC 774 ms 110576 KB
30_max_02 AC 782 ms 109768 KB
30_max_03 AC 776 ms 110088 KB
30_max_04 AC 782 ms 109776 KB
30_max_05 AC 770 ms 110424 KB
31_max_01 AC 767 ms 110192 KB
31_max_02 AC 774 ms 109884 KB