結果
問題 | No.1875 Flip Cards |
ユーザー |
![]() |
提出日時 | 2024-11-12 08:48:39 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 4,126 ms / 10,000 ms |
コード長 | 9,532 bytes |
コンパイル時間 | 753 ms |
コンパイル使用メモリ | 82,472 KB |
実行使用メモリ | 259,580 KB |
最終ジャッジ日時 | 2024-11-12 08:49:03 |
合計ジャッジ時間 | 21,672 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 7 |
ソースコード
mod = 998244353fact = [1 for i in range(10 ** 6 + 1)]fact_inv = [1 for i in range(10 ** 6 + 1)]for i in range(1,10 ** 6 + 1):fact[i] = fact[i - 1] * i % modfact_inv[-1] = pow(fact[-1],mod - 2,mod)for i in range(10 ** 6,0,-1):fact_inv[i - 1] = fact_inv[i] * i % modNTT_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 fps_inv(f,deg = -1):assert (f[0] != 0)if deg == -1:deg = len(f)res = [0] * degres[0] = pow(f[0],mod-2,mod)d = 1while d < deg:a = [0] * (d << 1)tmp = min(len(f),d << 1)a[:tmp] = f[:tmp]b = [0] * (d << 1)b[:d] = res[:d]ntt(a)ntt(b)for i in range(d << 1):a[i] = a[i] * b[i] % modintt(a)a[:d] = [0] * dntt(a)for i in range(d << 1):a[i] = a[i] * b[i] % modintt(a)for j in range(d,min(d << 1,deg)):if a[j]:res[j] = mod - a[j]else:res[j] = 0d <<= 1return resdef fps_div(f,g):n,m = len(f),len(g)if n < m:return [0],frev_f = f[:]rev_f = rev_f[::-1]rev_g = g[:]rev_g = rev_g[::-1]rev_q = convolute(rev_f,fps_inv(rev_g,n-m+1))[:n-m+1]q = rev_q[:]q = q[::-1]p = convolute(g,q)r = f[:]for i in range(min(len(p),len(r))):r[i] -= p[i]r[i] %= modwhile len(r):if r[-1] != 0:breakr.pop()if len(r) == 0:r.append(0)return q,rdef fps_add(f,g):n = max(len(f),len(g))res = [0] * nfor i in range(len(f)):res[i] = f[i]for i in range(len(g)):res[i] = (res[i] + g[i]) % modreturn resdef fps_diff(f):if len(f) <= 1:return [0]res = []for i in range(1,len(f)):res.append(i * f[i] % mod)return resdef fps_integrate(f):n = len(f)res = [0] * (n + 1)for i in range(n):res[i+1] = pow(i + 1,mod-2,mod) * f[i] % modreturn resdef fps_log(f,deg = -1):assert (f[0] == 1)if deg == -1:deg = len(f)res = convolute(fps_diff(f),fps_inv(f,deg))res = fps_integrate(res)return res[:deg]def fps_exp(f,deg = -1):assert (f[0] == 0)if deg == -1:deg = len(f)res = [1,0]if len(f) > 1:res[1] = f[1]g = [1]p = []q = [1,1]m = 2while m < deg:y = res + [0]*mntt(y)p = q[:]z = [y[i] * p[i] for i in range(len(p))]intt(z)z[:m >> 1] = [0] * (m >> 1)ntt(z)for i in range(len(p)):z[i] = z[i] * (-p[i]) % modintt(z)g[m >> 1:] = z[m >> 1:]q = g + [0] * mntt(q)tmp = min(len(f),m)x = f[:tmp] + [0] * (m - tmp)x = fps_diff(x)x.append(0)ntt(x)for i in range(len(x)):x[i] = x[i] * y[i] % modintt(x)for i in range(len(res)):if i == 0:continuex[i-1] -= res[i] * i % modx += [0] * mfor i in range(m-1):x[m+i],x[i] = x[i],0ntt(x)for i in range(len(q)):x[i] = x[i] * q[i] % modintt(x)x.pop()x = fps_integrate(x)x[:m] = [0] * mfor i in range(m,min(len(f),m << 1)):x[i] += f[i]ntt(x)for i in range(len(y)):x[i] = x[i] * y[i] % modintt(x)res[m:] = x[m:]m <<= 1return res[:deg]def fps_pow(f,k,deg = -1):if deg == -1:deg = len(f)if k == 0:return [1] + [0] * (deg - 1)while len(f) < deg:f.append(0)p = 0while p < deg:if f[p]:breakp += 1if p * k >= deg:return [0] * dega = f[p]g = [0 for _ in range(deg - p)]a_inv = pow(a,mod-2,mod)for i in range(deg - p):g[i] = f[i + p] * a_inv % modg = fps_log(g)for i in range(deg-p):g[i] = g[i] * k % modg = fps_exp(g)a = pow(a,k,mod)res = [0] * degfor i in range(deg):j = i + p * kif j >= deg:breakres[j] = g[i] * a % modreturn resdef Taylor_Shift(f,c):n = len(f) - 1P = [f[i] * fact[i] % mod for i in range(n + 1)]Q = [0] * (n + 1)for i in range(n+1):Q[n-i] = pow(c,i,mod) * fact_inv[i] % modg = convolute(P,Q)[n:]for i in range(n+1):g[i] *= fact_inv[i]g[i] %= modreturn gN,M = map(int,input().split())res = 1from collections import *F = deque()for i in range(N):A,B,C = map(int,input().split())res = res * pow(A,C,mod) % modB = B * pow(A,mod - 2,mod) % modB = (mod - B) % modF.append(([C],[1,-B]))for i in range(N - 1):a,b = F.popleft()c,d = F.popleft()f = fps_add(convolute(a,d),convolute(b,c))g = convolute(b,d)F.append((f,g))f,g = F.pop()f = convolute(f,fps_inv(g,M + 1))[:M + 1]f[0] = 0for i in range(1,M + 1):f[i] = f[i] * pow(i,mod - 2,mod) % modf[i] = (mod - f[i]) % modf = fps_exp(f)f = Taylor_Shift(f,-1)F = deque()for i in range(M + 1):a,b = [f[i]],[1,-i]F.append((a,b))for i in range(M):a,b = F.popleft()c,d = F.popleft()f = fps_add(convolute(a,d),convolute(b,c))g = convolute(b,d)F.append((f,g))f,g = F.pop()f = convolute(f,fps_inv(g))for i in range(1,M + 1):print(f[i] * res % mod)