結果
| 問題 | No.1066 #いろいろな色 / Red and Blue and more various colors (Easy) |
| ユーザー |
👑  Kazun
|
| 提出日時 | 2020-06-10 15:20:24 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
MLE
|
| 実行時間 | - |
| コード長 | 6,079 bytes |
| コンパイル時間 | 1,345 ms |
| コンパイル使用メモリ | 87,232 KB |
| 実行使用メモリ | 270,104 KB |
| 最終ジャッジ日時 | 2023-09-05 10:19:33 |
| 合計ジャッジ時間 | 6,915 ms |
|
ジャッジサーバーID （参考情報） |
judge14 / judge13 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 72 ms
71,464 KB |
| testcase_01 | AC | 73 ms
71,392 KB |
| testcase_02 | AC | 73 ms
71,496 KB |
| testcase_03 | AC | 72 ms
71,484 KB |
| testcase_04 | AC | 71 ms
71,476 KB |
| testcase_05 | AC | 73 ms
71,516 KB |
| testcase_06 | AC | 74 ms
71,352 KB |
| testcase_07 | AC | 73 ms
71,476 KB |
| testcase_08 | MLE | - |
| testcase_09 | -- | - |
| testcase_10 | -- | - |
| testcase_11 | -- | - |
| testcase_12 | -- | - |
| testcase_13 | -- | - |
| testcase_14 | -- | - |
| testcase_15 | -- | - |
| testcase_16 | -- | - |
| testcase_17 | -- | - |
| testcase_18 | -- | - |
| testcase_19 | -- | - |
| testcase_20 | -- | - |
| testcase_21 | -- | - |
| testcase_22 | -- | - |
| testcase_23 | -- | - |
| testcase_24 | -- | - |
| testcase_25 | -- | - |
| testcase_26 | -- | - |
ソースコード
class Polynominal_Error(Exception):
pass
class Polynominal():
def __init__(self,P=[],C="X"):
U=[]
for (c,k) in P:
if c!=0:
U.append((c,k))
if U==[]:
U=[(0,0)]
self.P=U
self.C=C
self.deg=max(U,key=lambda x:x[1])[1]
def __str__(self):
S=""
for (c,k) in self.P:
if k!=0 and k!=1:
S+="+{} {}^{}".format(c,self.C,k)
elif k==1:
S+="+{} {}".format(c,self.C)
else:
S+="+{}".format(c)
return S[1:]
#+,-
def __pos__(self):
return self
def __neg__(self):
return self.scale(-1)
#加法
def __add__(self,other):
if isinstance(other,Polynominal):
P=self.P
Q=other.P
D={k:c for (c,k) in Q}
for (c,k) in P:
if k in D:
D[k]+=c
else:
D[k]=c
E=[]
for k in D:
E.append((D[k],k))
return Polynominal(E,self.C)
else:
return self+Polynominal([(other,0)],self.C)
def __radd__(self,other):
return self+Polynominal([(other,0)],self.C)
#減法
def __sub__(self,other):
return self+(-other)
def __rsub__(self,other):
return -self+other
#X^mを掛ける
def mini_mul(self,m):
P=[]
for (k,c) in self.P:
P.append((k,c+m))
return Polynominal(P)
#乗法
def __mul__(self,other):
if isinstance(other,Polynominal):
P=self.P
Q=other.P
S=Polynominal()
for (c,m) in Q:
S=S+(self.mini_mul(m)).scale(c)
return S
else:
return self.scale(other)
def __rmul__(self,other):
return self.scale(other)
#累乗
def __pow__(P,n):
if n<0:
raise Polynominal_Error("nが負です.")
R=Polynominal([(1,0)])
D=P
while n>0:
if n%2==1:
R*=D
D*=D
n=n>>1
return R
#スカラー倍
def scale(self,s):
Q=[]
for (c,k) in self.P:
Q.append((c*s,k))
return Polynominal(Q,self.C)
#代入
def substitute(self,a):
P=self.P
P.sort(key=lambda x:x[1])
D={k:c for (c,k) in P}
if P[0][1]>=0:
S=0
t=1
for i in range(self.deg+1):
if i in D:
S+=D[i]*t
t*=a
return S
def Poly(*P):
Q=[]
for i in range(len(P)):
Q.append((P[i],i))
return Polynominal(Q)
def Coefficient_Dictionary(P):
K=P.P
D={}
for (c,k) in K:
D[k]=c
return D
def Coefficient(P,k):
D=Coefficient_Dictionary(P)
if k in D:
return D[k]
else:
return 0
class Modulo_Error(Exception):
pass
class Modulo():
def __init__(self,a,n):
self.a=a%n
self.n=n
def __str__(self):
return "{} (mod {})".format(self.a,self.n)
#+,-
def __pos__(self):
return self
def __neg__(self):
return Modulo(-self.a,self.n)
#等号,不等号
def __eq__(self,other):
if isinstance(other,Modulo):
return (self.a==other.a) and (self.n==other.n)
elif isinstance(other,int):
return (self-other).a==0
def __neq__(self,other):
return not(self==other)
#加法
def __add__(self,other):
if isinstance(other,Modulo):
if self.n!=other.n:
raise Modulo_Error("異なる法同士の演算です.")
return Modulo(self.a+other.a,self.n)
elif isinstance(other,int):
return Modulo(self.a+other,self.n)
def __radd__(self,other):
if isinstance(other,int):
return Modulo(self.a+other,self.n)
#減法
def __sub__(self,other):
return self+(-other)
def __rsub__(self,other):
if isinstance(other,int):
return -self+other
#乗法
def __mul__(self,other):
if isinstance(other,Modulo):
if self.n!=other.n:
raise Modulo_Error("異なる法同士の演算です.")
return Modulo(self.a*other.a,self.n)
elif isinstance(other,int):
return Modulo(self.a*other,self.n)
def __rmul__(self,other):
if isinstance(other,int):
return Modulo(self.a*other,self.n)
#Modulo逆数
def Modulo_Inverse(self):
x0, y0, x1, y1 = 1, 0, 0, 1
a,b=self.a,self.n
while b != 0:
q, a, b = a // b, b, a % b
x0, x1 = x1, x0 - q * x1
y0, y1 = y1, y0 - q * y1
if a!=1:
raise Modulo_Error("{}の逆数が存在しません".format(self))
else:
return Modulo(x0,self.n)
#除法
def __truediv__(self,other):
return self*other.Modulo_Inverse()
#累乗
def __pow__(self,m):
u=abs(m)
r=Modulo(1,self.n)
while u>0:
if u%2==1:
r*=self
self*=self
u=u>>1
if m>=0:
return r
else:
return r.Modulo_Inverse()
def Poly(*P):
Q=[]
for i in range(len(P)):
Q.append((P[i],i))
return Polynominal(Q)
def Coefficient_Dictionary(P):
K=P.P
D={}
for (c,k) in K:
D[k]=c
return D
#--------------------------------------
N,Q=map(int,input().split())
A=list(map(int,input().split()))
B=list(map(int,input().split()))
M=998244353
P=Poly(Modulo(1,M))
for a in A:
P=P*Poly(Modulo(a-1,M),1)
D=Coefficient_Dictionary(P)
for b in B:
if b in D:
print(D[b].a)
else:
print(0)