結果

問題 No.2004 Incremental Coins
ユーザー to-omerto-omer
提出日時 2021-11-27 16:35:10
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,157 ms / 2,000 ms
コード長 3,542 bytes
コンパイル時間 341 ms
コンパイル使用メモリ 87,016 KB
実行使用メモリ 188,716 KB
最終ジャッジ日時 2023-09-16 00:46:20
合計ジャッジ時間 19,624 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge15
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 109 ms
111,224 KB
testcase_01 AC 106 ms
111,156 KB
testcase_02 AC 112 ms
111,192 KB
testcase_03 AC 112 ms
111,096 KB
testcase_04 AC 160 ms
112,500 KB
testcase_05 AC 134 ms
112,188 KB
testcase_06 AC 246 ms
113,108 KB
testcase_07 AC 228 ms
113,536 KB
testcase_08 AC 1,036 ms
161,076 KB
testcase_09 AC 1,138 ms
156,676 KB
testcase_10 AC 928 ms
188,716 KB
testcase_11 AC 827 ms
154,580 KB
testcase_12 AC 1,010 ms
156,528 KB
testcase_13 AC 1,072 ms
160,524 KB
testcase_14 AC 1,139 ms
159,104 KB
testcase_15 AC 1,017 ms
162,664 KB
testcase_16 AC 1,148 ms
161,540 KB
testcase_17 AC 997 ms
161,136 KB
testcase_18 AC 1,065 ms
159,200 KB
testcase_19 AC 1,157 ms
155,060 KB
testcase_20 AC 1,077 ms
153,516 KB
testcase_21 AC 1,100 ms
151,360 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

MOD = 998244353


def init_ntt_cache():
    n = 1 << 18
    C = [1]
    rC = [1]
    m = 1
    while m < n:
        p = pow(3, (MOD - 1) // (m * 4), MOD)
        ip = pow(p, MOD - 2, MOD)
        for i in range(m):
            C.append(C[i] * p % MOD)
            rC.append(rC[i] * ip % MOD)
        m *= 2
    return C, rC


C, rC = init_ntt_cache()


def ntt(f, n):
    u, v = 1, n // 2
    for i in range(len(bin(n)) - 3, 0, -1):
        for jh in range(u):
            wj = C[jh]
            for j in range(jh << i, (jh << i) + v):
                k = j + v
                fjv = wj * f[k] % MOD
                f[k] = f[j] - fjv
                if f[k] < 0:
                    f[k] += MOD
                f[j] += fjv
                if f[j] >= MOD:
                    f[j] -= MOD
        u <<= 1
        v >>= 1
    return f


def intt(f, n):
    u, v = n // 2, 1
    for i in range(1, len(bin(n)) - 2):
        for jh in range(u):
            wj = rC[jh]
            for j in range(jh << i, (jh << i) + v):
                k = j + v
                fjv = f[j] - f[k]
                if fjv < 0:
                    fjv += MOD
                f[j] += f[k]
                if f[j] >= MOD:
                    f[j] -= MOD
                f[k] = wj * fjv % MOD
        u >>= 1
        v <<= 1
    return f


def convolve(f, g, index):
    n = 2
    m = len(f) + len(g) - 1
    while 2 * n < m:
        n *= 2
    n *= 2
    while len(f) < n:
        f.append(0)
    while len(g) < n:
        g.append(0)
    Ff = ntt(f, n)
    Fg = ntt(g, n)
    Fh = [x * y % MOD for x, y in zip(Ff, Fg)]
    h = intt(Fh, n)[:index]
    ninv = pow(n, MOD - 2, MOD)
    return [x * ninv % MOD for x in h]


def main():
    N, K = map(int, input().split())
    N += 1
    A = list(map(int, input().split()))
    B = list(map(int, input().split()))

    g = [[] for _ in range(N)]
    for i, b in enumerate(B):
        g[b].append(i + 1)
    d = [0] * N
    for u in range(N):
        for v in g[u]:
            d[v] = d[u] + 1
    for u in range(N - 1, -1, -1):
        for v in g[u]:
            d[u] = max(d[u], d[v])
    for u in range(N):
        for i in range(1, len(g[u])):
            if d[g[u][0]] < d[g[u][i]]:
                g[u][0], g[u][i] = g[u][i], g[u][0]

    dp = [[] for _ in range(N)]
    for u in range(N - 1, -1, -1):
        if g[u]:
            dpl = dp[g[u][0]]
            for v in g[u][1:]:
                for i in range(-len(dp[v]), 0):
                    dpl[i] += dp[v][i]
                    if dpl[i] >= MOD:
                        dpl[i] -= MOD
            dp[u], dp[g[u][0]] = dp[g[u][0]], dp[u]
        dp[u].append(A[u])

    fact = [1] * N
    ifact = [1] * N
    for i in range(2, N):
        fact[i] = fact[i - 1] * i % MOD
    ifact[-1] = pow(fact[-1], MOD - 2, MOD)
    for i in range(N - 1, 1, -1):
        ifact[i - 1] = ifact[i] * i % MOD
    c = [0] * N
    acc = 1
    for i in range(N):
        c[i] = acc * ifact[i] % MOD
        acc = acc * (K - i) % MOD

    for i, d in enumerate(dp):
        if not d:
            continue
        dp[i] = convolve(d, c[: len(d)], len(d))

    ans = [0] * N
    for u in range(N):
        ans[u] = dp[u].pop()
        if g[u]:
            dp[u], dp[g[u][0]] = dp[g[u][0]], dp[u]
            dpl = dp[g[u][0]]
            for v in g[u][1:]:
                for i in range(-len(dp[v]), 0):
                    dpl[i] -= dp[v][i]
                    if dpl[i] < 0:
                        dpl[i] += MOD

    print(*ans, sep="\n")


if __name__ == "__main__":
    main()
0