結果
問題 | No.2966 Simple Plus Minus Problem |
ユーザー |
![]() |
提出日時 | 2024-11-16 18:04:09 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 347 ms / 2,567 ms |
コード長 | 5,280 bytes |
コンパイル時間 | 431 ms |
コンパイル使用メモリ | 82,304 KB |
実行使用メモリ | 112,260 KB |
最終ジャッジ日時 | 2024-11-16 18:04:24 |
合計ジャッジ時間 | 14,498 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 54 |
ソースコード
mod = 998244353NTT_friend = [120586241,167772161,469762049,754974721,880803841,924844033,943718401,998244353,1045430273,1051721729,1053818881]NTT_dict = {}for i in range(len(NTT_friend)):NTT_dict[NTT_friend[i]] = iNTT_info = [[20,74066978],[25,17],[26,30],[24,362],[23,211],[21,44009197],[22,663003469],[23,31],[20,363],[20,330],[20,2789]]def popcount(n):c = (n&0x5555555555555555) + ((n>>1)&0x5555555555555555)c = (c&0x3333333333333333) + ((c>>2)&0x3333333333333333)c = (c&0x0f0f0f0f0f0f0f0f) + ((c>>4)&0x0f0f0f0f0f0f0f0f)c = (c&0x00ff00ff00ff00ff) + ((c>>8)&0x00ff00ff00ff00ff)c = (c&0x0000ffff0000ffff) + ((c>>16)&0x0000ffff0000ffff)c = (c&0x00000000ffffffff) + ((c>>32)&0x00000000ffffffff)return cdef topbit(n):h = n.bit_length()h -= 1return hdef prepared_fft(mod = 998244353):rank2 = NTT_info[NTT_dict[mod]][0]root,iroot = [0] * 30,[0] * 30rate2,irate2= [0] * 30,[0] * 30rate3,irate3= [0] * 30,[0] * 30root[rank2] = NTT_info[NTT_dict[mod]][1]iroot[rank2] = pow(root[rank2],mod - 2,mod)for i in range(rank2 - 1,-1,-1):root[i] = root[i + 1] * root[i + 1] % modiroot[i] = iroot[i + 1] * iroot[i + 1] % modprod,iprod = 1,1for i in range(rank2-1):rate2[i] = root[i + 2] * prod % modirate2[i] = iroot[i + 2] * iprod % modprod = prod * iroot[i + 2] % modiprod = iprod * root[i + 2] % modprod,iprod = 1,1for i in range(rank2-2):rate3[i] = root[i + 3] * prod % modirate3[i] = iroot[i + 3] * iprod % modprod = prod * iroot[i + 3] % modiprod = iprod * root[i + 3] % modreturn root,iroot,rate2,irate2,rate3,irate3root,iroot,rate2,irate2,rate3,irate3 = prepared_fft()def ntt(a):n = len(a)h = topbit(n)assert (n == 1 << h)le = 0while le < h:if h - le == 1:p = 1 << (h - le - 1)rot = 1for s in range(1 << le):offset = s << (h - le)for i in range(p):l = a[i + offset]r = a[i + offset + p] * rot % moda[i + offset] = (l + r) % moda[i + offset + p] = (l - r) % modrot = rot * rate2[topbit(~s & -~s)] % modle += 1else:p = 1 << (h - le - 2)rot,imag = 1,root[2]for s in range(1 << le):rot2 = rot * rot % modrot3 = rot2 * rot % modoffset = s << (h - le)for i in range(p):a0 = a[i + offset]a1 = a[i + offset + p] * rota2 = a[i + offset + p * 2] * rot2a3 = a[i + offset + p * 3] * rot3a1na3imag = (a1 - a3) % mod * imaga[i + offset] = (a0 + a2 + a1 + a3) % moda[i + offset + p] = (a0 + a2 - a1 - a3) % moda[i + offset + p * 2] = (a0 - a2 + a1na3imag) % moda[i + offset + p * 3] = (a0 - a2 - a1na3imag) % modrot = rot * rate3[topbit(~s & -~s)] % modle += 2def intt(a):n = len(a)h = topbit(n)assert (n == 1 << h)coef = pow(n,mod - 2,mod)for i in range(n):a[i] = a[i] * coef % modle = hwhile le:if le == 1:p = 1 << (h - le)irot = 1for s in range(1 << (le - 1)):offset = s << (h - le + 1)for i in range(p):l = a[i + offset]r = a[i + offset + p]a[i + offset] = (l + r) % moda[i + offset + p] = (l - r) * irot % modirot = irot * irate2[topbit(~s & -~s)] % modle -= 1else:p = 1 << (h - le)irot,iimag = 1,iroot[2]for s in range(1 << (le - 2)):irot2 = irot * irot % modirot3 = irot2 * irot % modoffset = s << (h - le + 2)for i in range(p):a0 = a[i + offset]a1 = a[i + offset + p]a2 = a[i + offset + p * 2]a3 = a[i + offset + p * 3]a2na3iimag = (a2 - a3) * iimag % moda[i + offset] = (a0 + a1 + a2 + a3) % moda[i + offset + p] = (a0 - a1 + a2na3iimag) * irot % moda[i + offset + p * 2] = (a0 + a1 - a2 - a3) * irot2 % moda[i + offset + p * 3] = (a0 - a1 - a2na3iimag) * irot3 % modirot *= irate3[topbit(~s & -~s)]irot %= modle -= 2def convolute_naive(a,b):res = [0] * (len(a) + len(b) - 1)for i in range(len(a)):for j in range(len(b)):res[i + j] = (res[i + j] + a[i] * b[j] % mod) % modreturn resdef convolute(a,b):s = a[:]t = b[:]n = len(s)m = len(t)if min(n,m) <= 60:return convolute_naive(s,t)le = 1while le < n + m - 1:le *= 2s += [0] * (le - n)t += [0] * (le - m)ntt(s)ntt(t)for i in range(le):s[i] = s[i] * t[i] % modintt(s)s = s[:n + m - 1]return sdef mod_inv(a,mod = 998244353):if mod == 1:return 0a %= modb,s,t = mod,1,0while True:if a == 1:return st -= (b // a) * sb %= aif b == 1:return t + mods -= (a // b) * ta %= bN,K = map(int,input().split())A = list(map(int,input().split()))f = [0 for i in range(N)]f[0] = 1n = K // 2for i in range(2,N,2):j = i // 2f[i] = f[i - 2] * ((n + j - 1) * mod_inv(j) % mod) % modf = convolute(f,A)[:N]if K % 2:for i in range(N):if i % 2:f[i] = mod - f[i]for i in range(N - 1):f[i + 1] += f[i]f[i + 1] %= modprint(*f)