結果
問題 | No.2966 Simple Plus Minus Problem |
ユーザー |
![]() |
提出日時 | 2024-11-16 17:59:42 |
言語 | PyPy3 (7.3.15) |
結果 |
RE
|
実行時間 | - |
コード長 | 5,601 bytes |
コンパイル時間 | 600 ms |
コンパイル使用メモリ | 82,268 KB |
実行使用メモリ | 129,812 KB |
最終ジャッジ日時 | 2024-11-16 17:59:55 |
合計ジャッジ時間 | 10,887 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 32 RE * 22 |
ソースコード
mod = 998244353n = 300000inv = [1 for j in range(n + 1)]for a in range(2,n + 1):# ax + py = 1 <=> rx + p(-x-qy) = -q => x = -(inv[r]) * (p//a) (r = p % a)res = (mod - inv[mod % a]) * (mod // a)inv[a] = res % modfact = [1 for i in range(n + 1)]for i in range(1,n + 1):fact[i] = fact[i - 1] * i % modfact_inv = [1 for i in range(n + 1)]fact_inv[-1] = pow(fact[-1],mod - 2,mod)for i in range(n,0,-1):fact_inv[i - 1] = fact_inv[i] * i % moddef binom(n,r):if n < r or n < 0 or r < 0:return 0res = fact_inv[n - r] * fact_inv[r] % modres *= fact[n]res %= modreturn resNTT_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 sN,K = map(int,input().split())A = list(map(int,input().split()))f = [0 for i in range(N)]f[0] = 1for i in range(2,N,2):j = i // 2f[i] = binom(j + K // 2 - 1,j)f = 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)