Submission #17617768


Source Code Expand

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

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

MOD = 998_244_353

def from_read(dtype=np.int64):
    return np.fromstring(read().decode(), dtype=dtype, sep=' ')


def from_readline(dtype=np.int64):
    return np.fromstring(readline().decode(), dtype=dtype, sep=' ')

@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)

N, K = map(int, readline().split())
A = from_read()

main(A, K)

Submission Info

Submission Time
Task D - Powers
User maspy
Language Python (3.8.2)
Score 600
Code Size 1303 Byte
Status AC
Exec Time 782 ms
Memory 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