結果
問題 | No.1307 Rotate and Accumulate |
ユーザー |
![]() |
提出日時 | 2021-08-13 14:11:19 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 260 ms / 5,000 ms |
コード長 | 3,119 bytes |
コンパイル時間 | 260 ms |
コンパイル使用メモリ | 82,596 KB |
実行使用メモリ | 118,128 KB |
最終ジャッジ日時 | 2024-10-03 04:32:46 |
合計ジャッジ時間 | 5,211 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 19 |
ソースコード
mod = 998244353W = (1, 998244352, 911660635, 372528824, 929031873, 452798380, 922799308, 781712469, 476477967, 166035806, 258648936,584193783, 63912897, 350007156, 666702199, 968855178, 629671588, 24514907, 996173970, 363395222, 565042129,733596141, 267099868, 15311432)IW = (1, 998244352, 86583718, 509520358, 337190230, 87557064, 609441965, 135236158, 304459705, 685443576, 381598368,335559352, 129292727, 358024708, 814576206, 708402881, 283043518, 3707709, 121392023, 704923114, 950391366,428961804, 382752275, 469870224)def main():import sysinput = sys.stdin.readline# A: 係数を並べたベクトル,len(A) = 2^ndef fft(A):N = len(A)n = N.bit_length() - 1N2 = N // 2A_new = [0] * Nfor lv in range(n):L = 1 << (n - lv - 1)w = W[lv + 1]ww = 1for j in range(1 << lv):for i in range(L):f0_val = A[i + j * L * 2]f1_val = A[i + j * L * 2 + L]tmp = (ww * f1_val) % modA_new[i + j * L] = (f0_val + tmp) % modA_new[i + j * L + N2] = (f0_val - tmp) % modww = (ww * w) % modA, A_new = A_new, Areturn A# A: 係数を並べたベクトル,len(A) = 2^ndef ifft(A):N = len(A)n = N.bit_length() - 1N2 = N // 2A_new = [0] * Nfor lv in range(n):L = 1 << (n - lv - 1)w = IW[lv + 1]ww = 1for j in range(1 << lv):for i in range(L):f0_val = A[i + j * L * 2]f1_val = A[i + j * L * 2 + L]tmp = (ww * f1_val) % modA_new[i + j * L] = (f0_val + tmp) % modA_new[i + j * L + N2] = (f0_val - tmp) % modww = (ww * w) % modA, A_new = A_new, Areturn Adef convolution(A0, B0, limit):if len(A0) <= 60 or len(B0) <= 60:return convolution_naive(A0, B0, limit)N = len(A0) + len(B0) - 1N0 = 1 << ((N - 1).bit_length())A = A0 + [0] * (N0 - len(A0))B = B0 + [0] * (N0 - len(B0))AA = fft(A)BB = fft(B)CC = [(aa * bb) % mod for aa, bb in zip(AA, BB)]C = ifft(CC)invN0 = pow(N0, mod - 2, mod)C = [(c * invN0) % mod for c in C]return C[:limit]def convolution_naive(A0, B0, limit):NA = len(A0)NB = len(B0)C = [0] * (NA + NB - 1)for i in range(NA):for j in range(NB):C[i + j] = (C[i + j] + (A0[i] * B0[j]) % mod) % modreturn C[:limit]N, Q = map(int, input().split())A = list(map(int, input().split()))R = list(map(int, input().split()))B = [0] * (N+1)for r in R:B[N-r] += 1C = convolution(A, B, N*2)ans = [0] * Nfor i in range(N):ans[i] = (C[i] + C[i+N])%modprint(*ans)if __name__ == '__main__':main()