結果
問題 | No.2004 Incremental Coins |
ユーザー |
|
提出日時 | 2021-11-27 16:35:10 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,091 ms / 2,000 ms |
コード長 | 3,542 bytes |
コンパイル時間 | 209 ms |
コンパイル使用メモリ | 82,572 KB |
実行使用メモリ | 197,384 KB |
最終ジャッジ日時 | 2024-07-03 01:52:52 |
合計ジャッジ時間 | 20,373 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 20 |
ソースコード
MOD = 998244353def init_ntt_cache():n = 1 << 18C = [1]rC = [1]m = 1while 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 *= 2return C, rCC, rC = init_ntt_cache()def ntt(f, n):u, v = 1, n // 2for 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 + vfjv = wj * f[k] % MODf[k] = f[j] - fjvif f[k] < 0:f[k] += MODf[j] += fjvif f[j] >= MOD:f[j] -= MODu <<= 1v >>= 1return fdef intt(f, n):u, v = n // 2, 1for 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 + vfjv = f[j] - f[k]if fjv < 0:fjv += MODf[j] += f[k]if f[j] >= MOD:f[j] -= MODf[k] = wj * fjv % MODu >>= 1v <<= 1return fdef convolve(f, g, index):n = 2m = len(f) + len(g) - 1while 2 * n < m:n *= 2n *= 2while 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 += 1A = 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] * Nfor u in range(N):for v in g[u]:d[v] = d[u] + 1for 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] -= MODdp[u], dp[g[u][0]] = dp[g[u][0]], dp[u]dp[u].append(A[u])fact = [1] * Nifact = [1] * Nfor i in range(2, N):fact[i] = fact[i - 1] * i % MODifact[-1] = pow(fact[-1], MOD - 2, MOD)for i in range(N - 1, 1, -1):ifact[i - 1] = ifact[i] * i % MODc = [0] * Nacc = 1for i in range(N):c[i] = acc * ifact[i] % MODacc = acc * (K - i) % MODfor i, d in enumerate(dp):if not d:continuedp[i] = convolve(d, c[: len(d)], len(d))ans = [0] * Nfor 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] += MODprint(*ans, sep="\n")if __name__ == "__main__":main()