結果
問題 | No.1307 Rotate and Accumulate |
ユーザー |
![]() |
提出日時 | 2020-12-04 00:07:18 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 259 ms / 5,000 ms |
コード長 | 2,712 bytes |
コンパイル時間 | 256 ms |
コンパイル使用メモリ | 82,408 KB |
実行使用メモリ | 114,672 KB |
最終ジャッジ日時 | 2024-09-14 09:35:26 |
合計ジャッジ時間 | 4,849 ms |
ジャッジサーバーID (参考情報) |
judge6 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 19 |
ソースコード
_fft_mod = 998244353_fft_sum_e = [911660635, 509520358, 369330050, 332049552, 983190778, 123842337, 238493703, 975955924, 603855026, 856644456, 131300601,842657263, 730768835, 942482514, 806263778, 151565301, 510815449, 503497456, 743006876, 741047443, 56250497, 0, 0, 0, 0, 0, 0, 0, 0, 0]_fft_sum_ie = [86583718, 372528824, 373294451, 645684063, 112220581, 692852209, 155456985, 797128860, 90816748, 860285882, 927414960,354738543, 109331171, 293255632, 535113200, 308540755, 121186627, 608385704, 438932459, 359477183, 824071951, 0, 0, 0, 0, 0, 0, 0, 0,0]def butterfly_998244353(a):n = len(a)h = (n - 1).bit_length()for ph in range(1, h + 1):w = 1 << (ph - 1)p = 1 << (h - ph)now = 1for s in range(w):offset = s << (h - ph + 1)for i in range(p):l = a[i + offset]r = a[i + offset + p] * now % _fft_moda[i + offset] = (l + r) % _fft_moda[i + offset + p] = (l - r) % _fft_modnow = now * _fft_sum_e[(~s & -~s).bit_length() - 1] % _fft_moddef butterfly_inv_998244353(a):n = len(a)h = (n - 1).bit_length()for ph in range(h, 0, -1):w = 1 << (ph - 1)p = 1 << (h - ph)inow = 1for s in range(w):offset = s << (h - ph + 1)for i in range(p):l = a[i + offset]r = a[i + offset + p]a[i + offset] = (l + r) % _fft_moda[i + offset + p] = (l - r) * inow % _fft_modinow = inow * _fft_sum_ie[(~s & -~s).bit_length() - 1] % _fft_moddef convolution_998244353(a, b):a = a.copy()b = b.copy()n = len(a)m = len(b)if n == 0 or m == 0:return []if min(n, m) <= 60:if n < m:n, m = m, na, b = b, aans = [0] * (n + m - 1)for i in range(n):for j in range(m):ans[i + j] = (ans[i + j] + a[i] * b[j] % _fft_mod) % _fft_modreturn ansz = 1 << (n + m - 2).bit_length()a += [0] * (z - n)b += [0] * (z - m)butterfly_998244353(a)butterfly_998244353(b)for i in range(z):a[i] = a[i] * b[i] % _fft_modbutterfly_inv_998244353(a)a = a[:n + m - 1]iz = pow(z, _fft_mod - 2, _fft_mod)for i in range(n + m - 1):a[i] = a[i] * iz % _fft_modreturn aN,Q=map(int,input().split())A=list(map(int,input().split()))R=list(map(int,input().split()))B=[0]*Nfor i in range(Q):B[-R[i]]+=1X=convolution_998244353(A,B)for i in range(N):X.append(0)print(*[X[i]+X[N+i] for i in range(N)])