結果
問題 | No.2013 Can we meet? |
ユーザー |
![]() |
提出日時 | 2023-04-29 05:02:57 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 592 ms / 2,500 ms |
コード長 | 16,048 bytes |
コンパイル時間 | 137 ms |
コンパイル使用メモリ | 81,832 KB |
実行使用メモリ | 123,668 KB |
最終ジャッジ日時 | 2024-11-18 03:53:40 |
合計ジャッジ時間 | 10,552 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 35 |
ソースコード
import sysreadline=sys.stdin.readlineimport mathdef Extended_Euclid(n,m):stack=[]while m:stack.append((n,m))n,m=m,n%mif n>=0:x,y=1,0else:x,y=-1,0for i in range(len(stack)-1,-1,-1):n,m=stack[i]x,y=y,x-(n//m)*yreturn x,yclass MOD:def __init__(self,p,e=None):self.p=pself.e=eif self.e==None:self.mod=self.pelse:self.mod=self.p**self.edef Pow(self,a,n):a%=self.modif n>=0:return pow(a,n,self.mod)else:assert math.gcd(a,self.mod)==1x=Extended_Euclid(a,self.mod)[0]return pow(x,-n,self.mod)def Build_Fact(self,N):assert N>=0self.factorial=[1]if self.e==None:for i in range(1,N+1):self.factorial.append(self.factorial[-1]*i%self.mod)else:self.cnt=[0]*(N+1)for i in range(1,N+1):self.cnt[i]=self.cnt[i-1]ii=iwhile ii%self.p==0:ii//=self.pself.cnt[i]+=1self.factorial.append(self.factorial[-1]*ii%self.mod)self.factorial_inve=[None]*(N+1)self.factorial_inve[-1]=self.Pow(self.factorial[-1],-1)for i in range(N-1,-1,-1):ii=i+1while ii%self.p==0:ii//=self.pself.factorial_inve[i]=(self.factorial_inve[i+1]*ii)%self.moddef Fact(self,N):if N<0:return 0retu=self.factorial[N]if self.e!=None and self.cnt[N]:retu*=pow(self.p,self.cnt[N],self.mod)%self.modretu%=self.modreturn retudef Fact_Inve(self,N):if self.e!=None and self.cnt[N]:return Nonereturn self.factorial_inve[N]def Comb(self,N,K,divisible_count=False):if K<0 or K>N:return 0retu=self.factorial[N]*self.factorial_inve[K]%self.mod*self.factorial_inve[N-K]%self.modif self.e!=None:cnt=self.cnt[N]-self.cnt[N-K]-self.cnt[K]if divisible_count:return retu,cntelse:retu*=pow(self.p,cnt,self.mod)retu%=self.modreturn retudef Tonelli_Shanks(N,p):if pow(N,p>>1,p)==p-1:retu=Noneelif p%4==3:retu=pow(N,(p+1)//4,p)else:for nonresidue in range(1,p):if pow(nonresidue,p>>1,p)==p-1:breakpp=p-1cnt=0while pp%2==0:pp//=2cnt+=1s=pow(N,pp,p)retu=pow(N,(pp+1)//2,p)for i in range(cnt-2,-1,-1):if pow(s,1<<i,p)==p-1:s*=pow(nonresidue,p>>1+i,p)s%=pretu*=pow(nonresidue,p>>2+i,p)retu%=preturn retumod = 998244353imag = 911660635iimag = 86583718rate2 = (911660635, 509520358, 369330050, 332049552, 983190778, 123842337, 238493703, 975955924, 603855026, 856644456, 131300601,842657263, 730768835, 942482514, 806263778, 151565301, 510815449, 503497456, 743006876, 741047443, 56250497, 867605899)irate2 = (86583718, 372528824, 373294451, 645684063, 112220581, 692852209, 155456985, 797128860, 90816748, 860285882, 927414960,354738543, 109331171, 293255632, 535113200, 308540755, 121186627, 608385704, 438932459, 359477183, 824071951, 103369235)rate3 = (372528824, 337190230, 454590761, 816400692, 578227951, 180142363, 83780245, 6597683, 70046822, 623238099,183021267, 402682409, 631680428, 344509872, 689220186, 365017329, 774342554, 729444058, 102986190, 128751033, 395565204)irate3 = (509520358, 929031873, 170256584, 839780419, 282974284, 395914482, 444904435, 72135471, 638914820, 66769500,771127074, 985925487, 262319669, 262341272, 625870173, 768022760, 859816005, 914661783, 430819711, 272774365, 530924681)def butterfly(a):n = len(a)h = (n - 1).bit_length()len_ = 0while len_ < h:if h - len_ == 1:p = 1 << (h - len_ - 1)rot = 1for s in range(1 << len_):offset = s << (h - len_)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) % modif s + 1 != 1 << len_:rot *= rate2[(~s & -~s).bit_length() - 1]rot %= modlen_ += 1else:p = 1 << (h - len_ - 2)rot = 1for s in range(1 << len_):rot2 = rot * rot % modrot3 = rot2 * rot % modoffset = s << (h - len_)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) % modif s + 1 != 1 << len_:rot *= rate3[(~s & -~s).bit_length() - 1]rot %= modlen_ += 2def butterfly_inv(a):n = len(a)h = (n - 1).bit_length()len_ = hwhile len_:if len_ == 1:p = 1 << (h - len_)irot = 1for s in range(1 << (len_ - 1)):offset = s << (h - len_ + 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 % modif s + 1 != (1 << (len_ - 1)):irot *= irate2[(~s & -~s).bit_length() - 1]irot %= modlen_ -= 1else:p = 1 << (h - len_)irot = 1for s in range(1 << (len_ - 2)):irot2 = irot * irot % modirot3 = irot2 * irot % modoffset = s << (h - len_ + 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 % modif s + 1 != (1 << (len_ - 2)):irot *= irate3[(~s & -~s).bit_length() - 1]irot %= modlen_ -= 2def integrate(a):a=a.copy()n = len(a)assert n > 0a.pop()a.insert(0, 0)inv = [1, 1]for i in range(2, n):inv.append(-inv[mod%i] * (mod//i) % mod)a[i] = a[i] * inv[i] % modreturn adef differentiate(a):n = len(a)assert n > 0for i in range(2, n):a[i] = a[i] * i % moda.pop(0)a.append(0)return adef convolution_naive(a, b):n = len(a)m = len(b)ans = [0] * (n + m - 1)if n < m:for j in range(m):for i in range(n):ans[i + j] = (ans[i + j] + a[i] * b[j]) % modelse:for i in range(n):for j in range(m):ans[i + j] = (ans[i + j] + a[i] * b[j]) % modreturn ansdef convolution_ntt(a, b):a = a.copy()b = b.copy()n = len(a)m = len(b)z = 1 << (n + m - 2).bit_length()a += [0] * (z - n)butterfly(a)b += [0] * (z - m)butterfly(b)for i in range(z):a[i] = a[i] * b[i] % modbutterfly_inv(a)a = a[:n + m - 1]iz = pow(z, mod - 2, mod)for i in range(n + m - 1):a[i] = a[i] * iz % modreturn adef convolution_square(a):a = a.copy()n = len(a)z = 1 << (2 * n - 2).bit_length()a += [0] * (z - n)butterfly(a)for i in range(z):a[i] = a[i] * a[i] % modbutterfly_inv(a)a = a[:2 * n - 1]iz = pow(z, mod - 2, mod)for i in range(2 * n - 1):a[i] = a[i] * iz % modreturn adef convolution(a, b):"""It calculates (+, x) convolution in mod 998244353.Given two arrays a[0], a[1], ..., a[n - 1] and b[0], b[1], ..., b[m - 1],it calculates the array c of length n + m - 1, defined by> c[i] = sum(a[j] * b[i - j] for j in range(i + 1)) % 998244353.It returns an empty list if at least one of a and b are empty.Complexity----------> O(n log n), where n = len(a) + len(b)."""n = len(a)m = len(b)if n == 0 or m == 0:return []if min(n, m) <= 60:return convolution_naive(a, b)if a is b:return convolution_square(a)return convolution_ntt(a, b)def inverse(a):n = len(a)assert n > 0 and a[0] != 0res = [pow(a[0], mod - 2, mod)]m = 1while m < n:f = a[:min(n,2*m)] + [0]*(2*m-min(n,2*m))g = res + [0]*mbutterfly(f)butterfly(g)for i in range(2*m):f[i] = f[i] * g[i] % modbutterfly_inv(f)f = f[m:] + [0]*mbutterfly(f)for i in range(2*m):f[i] = f[i] * g[i] % modbutterfly_inv(f)iz = pow(2*m, mod-2, mod)iz = (-iz*iz) % modfor i in range(m):f[i] = f[i] * iz % modres += f[:m]m <<= 1return res[:n]def log(a):a = a.copy()n = len(a)assert n > 0 and a[0] == 1a_inv = inverse(a)a=differentiate(a)a = convolution(a, a_inv)[:n]a=integrate(a)return adef exp(a):a = a.copy()n = len(a)assert n > 0 and a[0] == 0g = [1]a[0] = 1h_drv = a.copy()h_drv=differentiate(h_drv)m = 1while m < n:f_fft = a[:m] + [0] * mbutterfly(f_fft)if m > 1:_f = [f_fft[i] * g_fft[i] % mod for i in range(m)]butterfly_inv(_f)_f = _f[m // 2:] + [0] * (m // 2)butterfly(_f)for i in range(m):_f[i] = _f[i] * g_fft[i] % modbutterfly_inv(_f)_f = _f[:m//2]iz = pow(m, mod - 2, mod)iz *= -iziz %= modfor i in range(m//2):_f[i] = _f[i] * iz % modg.extend(_f)t = a[:m]t=differentiate(t)r = h_drv[:m - 1]r.append(0)butterfly(r)for i in range(m):r[i] = r[i] * f_fft[i] % modbutterfly_inv(r)im = pow(-m, mod - 2, mod)for i in range(m):r[i] = r[i] * im % modfor i in range(m):t[i] = (t[i] + r[i]) % modt = [t[-1]] + t[:-1]t += [0] * mbutterfly(t)g_fft = g + [0] * (2 * m - len(g))butterfly(g_fft)for i in range(2 * m):t[i] = t[i] * g_fft[i] % modbutterfly_inv(t)t = t[:m]i2m = pow(2 * m, mod - 2, mod)for i in range(m):t[i] = t[i] * i2m % modv = a[m:min(n, 2 * m)]v += [0] * (m - len(v))t = [0] * (m - 1) + t + [0]t=integrate(t)for i in range(m):v[i] = (v[i] - t[m + i]) % modv += [0] * mbutterfly(v)for i in range(2 * m):v[i] = v[i] * f_fft[i] % modbutterfly_inv(v)v = v[:m]i2m = pow(2 * m, mod - 2, mod)for i in range(m):v[i] = v[i] * i2m % modfor i in range(min(n - m, m)):a[m + i] = v[i]m *= 2return adef power(a,k):n = len(a)assert n>0if k==0:return [1]+[0]*(n-1)l = 0while l < len(a) and not a[l]:l += 1if l * k >= n:return [0] * nic = pow(a[l], mod - 2, mod)pc = pow(a[l], k, mod)a = log([a[i] * ic % mod for i in range(l, len(a))])for i in range(len(a)):a[i] = a[i] * k % moda = exp(a)for i in range(len(a)):a[i] = a[i] * pc % moda = [0] * (l * k) + a[:n - l * k]return adef sqrt(a):if len(a) == 0:return []if a[0] == 0:for d in range(1, len(a)):if a[d]:if d & 1:return Noneif len(a) - 1 < d // 2:breakres=sqrt(a[d:]+[0]*(d//2))if res == None:return Noneres = [0]*(d//2)+resreturn resreturn [0]*len(a)sqr = Tonelli_Shanks(a[0],mod)if sqr == None:return NoneT = [0] * (len(a))T[0] = sqrres = T.copy()T[0] = pow(sqr,mod-2,mod) #T:res^{-1}m = 1two_inv = (mod + 1) // 2F = [sqr]while m <= len(a) - 1:for i in range(m):F[i] *= F[i]F[i] %= modbutterfly_inv(F)iz = pow(m, mod-2, mod)for i in range(m):F[i] = F[i] * iz % moddelta = [0] * (2 * m)for i in range(m):delta[i + m] = F[i] - a[i] - (a[i + m] if i+m<len(a) else 0)butterfly(delta)G = [0] * (2 * m)for i in range(m):G[i] = T[i]butterfly(G)for i in range(2 * m):delta[i] *= G[i]delta[i] %= modbutterfly_inv(delta)iz = pow(2*m, mod-2, mod)for i in range(2*m):delta[i] = delta[i] * iz % modfor i in range(m, min(2 * m, len(a))):res[i] = -delta[i] * two_inv%modres[i]%=modif 2 * m > len(a) - 1:breakF = res[:2 * m]butterfly(F)eps = [F[i] * G[i] % mod for i in range(2 * m)]butterfly_inv(eps)for i in range(m):eps[i] = 0iz = pow(2*m, mod-2, mod)for i in range(m,2*m):eps[i] = eps[i] * iz % modbutterfly(eps)for i in range(2 * m):eps[i] *= G[i]eps[i] %= modbutterfly_inv(eps)for i in range(m, 2 * m):T[i] = -eps[i]*izT[i]%=modiz = iz*iz % modm <<= 1return resN=int(readline())x1,y1,x2,y2=map(int,readline().split())x=abs(x1-x2)y=abs(y1-y2)a,b=map(int,readline().split())A=list(map(int,readline().split()))mod=998244353if x%2!=y%2:ans=0else:MD=MOD(mod)MD.Build_Fact(2*N)a,b=a*MD.Pow(2*(a+b),-1)%mod,b*MD.Pow(2*(a+b),-1)%modX=[]for i in range(0,2*N+1,2):X.append(MD.Comb(i,i//2)*MD.Pow(a,i)%mod*MD.Fact_Inve(i)%mod)Y=[]for i in range(0,2*N+1,2):Y.append(MD.Comb(i,i//2)*MD.Pow(b,i)%mod*MD.Fact_Inve(i)%mod)XY_inve=convolution(X,Y)[:N+1]for i in range(0,N+1):XY_inve[i]*=MD.Fact(2*i)XY_inve[i]%=modX=[]for i in range(x%2,2*N+1,2):X.append(MD.Comb(i,(i+x)//2)*MD.Pow(a,i)%mod*MD.Fact_Inve(i)%mod)Y=[]for i in range(y%2,2*N+1,2):Y.append(MD.Comb(i,(i+y)//2)*MD.Pow(b,i)%mod*MD.Fact_Inve(i)%mod)XY=convolution(X,Y)if x%2:XY=[0]+XYXY=XY[:N+1]for i in range(len(XY)):XY[i]*=MD.Fact(2*i)XY[i]%=modpoly=convolution(XY,inverse(XY_inve))ans=0for i in range(1,N+1):ans+=poly[i]*A[i-1]%modans%=modprint(ans)