結果
| 問題 | No.1693 Invasion |
| ユーザー |
👑  Kazun
|
| 提出日時 | 2021-09-12 20:09:15 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
AC
|
| 実行時間 | 187 ms / 2,000 ms |
| コード長 | 5,467 bytes |
| コンパイル時間 | 1,043 ms |
| コンパイル使用メモリ | 86,604 KB |
| 実行使用メモリ | 90,120 KB |
| 最終ジャッジ日時 | 2023-09-26 15:49:13 |
| 合計ジャッジ時間 | 5,534 ms |
|
ジャッジサーバーID （参考情報） |
judge14 / judge12 |
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 70 ms
71,052 KB |
| testcase_01 | AC | 69 ms
71,332 KB |
| testcase_02 | AC | 71 ms
71,360 KB |
| testcase_03 | AC | 77 ms
75,840 KB |
| testcase_04 | AC | 69 ms
71,256 KB |
| testcase_05 | AC | 77 ms
75,868 KB |
| testcase_06 | AC | 80 ms
76,064 KB |
| testcase_07 | AC | 81 ms
76,180 KB |
| testcase_08 | AC | 78 ms
76,112 KB |
| testcase_09 | AC | 155 ms
86,576 KB |
| testcase_10 | AC | 132 ms
88,576 KB |
| testcase_11 | AC | 112 ms
83,288 KB |
| testcase_12 | AC | 140 ms
88,948 KB |
| testcase_13 | AC | 113 ms
83,148 KB |
| testcase_14 | AC | 121 ms
83,960 KB |
| testcase_15 | AC | 114 ms
81,272 KB |
| testcase_16 | AC | 133 ms
83,044 KB |
| testcase_17 | AC | 70 ms
71,476 KB |
| testcase_18 | AC | 177 ms
88,596 KB |
| testcase_19 | AC | 105 ms
90,120 KB |
| testcase_20 | AC | 74 ms
75,888 KB |
| testcase_21 | AC | 179 ms
88,644 KB |
| testcase_22 | AC | 174 ms
87,420 KB |
| testcase_23 | AC | 187 ms
88,128 KB |
ソースコード
class Modulo_Error(Exception):
pass
class Modulo():
__slots__=["a","n"]
def __init__(self,a,n):
self.a=a%n
self.n=n
def __str__(self):
return "{} (mod {})".format(self.a,self.n)
def __repr__(self):
return self.__str__()
#+,-
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 __le__(self,other):
a,p=self.a,self.n
b,q=other.a,other.n
return (a-b)%q==0 and p%q==0
def __ge__(self,other):
return other<=self
def __lt__(self,other):
return (self<=other) and (self!=other)
def __gt__(self,other):
return (self>=other) and (self!=other)
def __contains__(self,val):
return val%self.n==self.a
#加法
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 __iadd__(self,other):
if isinstance(other,Modulo):
if self.n!=other.n: raise Modulo_Error("異なる法同士の演算です.")
self.a+=other.a
if self.a>=self.n: self.a-=self.n
elif isinstance(other,int):
self.a+=other
if self.a>=self.n: self.a-=self.n
return self
#減法
def __sub__(self,other):
return self+(-other)
def __rsub__(self,other):
if isinstance(other,int):
return -self+other
def __isub__(self,other):
if isinstance(other,Modulo):
if self.n!=other.n: raise Modulo_Error("異なる法同士の演算です.")
self.a-=other.a
if self.a<0: self.a+=self.n
elif isinstance(other,int):
self.a-=other
if self.a<0: self.a+=self.n
return self
#乗法
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)
def __imul__(self,other):
if isinstance(other,Modulo):
if self.n!=other.n: raise Modulo_Error("異なる法同士の演算です.")
self.a*=other.a
elif isinstance(other,int):
self.a*=other
self.a%=self.n
return self
#Modulo逆数
def inverse(self):
return self.Modulo_Inverse()
def Modulo_Inverse(self):
s,t=1,0
a,b=self.a,self.n
while b:
q,a,b=a//b,b,a%b
s,t=t,s-q*t
if a!=1:
raise Modulo_Error("{}の逆数が存在しません".format(self))
else:
return Modulo(s,self.n)
#除法
def __truediv__(self,other):
return self*(other.Modulo_Inverse())
def __rtruediv__(self,other):
return other*(self.Modulo_Inverse())
#累乗
def __pow__(self,other):
if isinstance(other,int):
u=abs(other)
r=Modulo(pow(self.a,u,self.n),self.n)
if other>=0:
return r
else:
return r.Modulo_Inverse()
else:
b,n=other.a,other.n
if pow(self.a,n,self.n)!=1:
raise Modulo_Error("矛盾なく定義できません.")
else:
return self**b
def Factor_Modulo(N,Mod,Mode=0):
"""
Mode=0: N! (mod Mod) を求める.
Mode=1: k! (mod Mod) (k=0,1,...,N) のリストも出力する.
[計算量]
O(N)
"""
if Mode==0:
X=1
for k in range(1,N+1):
X*=k; X%=Mod
return Modulo(X,Mod)
else:
L=[Modulo(1,Mod)]*(N+1)
for k in range(1,N+1):
L[k]=k*L[k-1]
return L
def Factor_Modulo_with_Inverse(N, Mod):
""" k=0,1,...,N に対する k! (mod Mod) と (k!)^(-1) (mod Mod) のリストを出力する.
[入力]
N, Mod: 整数
Mod >0
[出力]
長さ N+1 のリストのタプル (F,G): F[k]=k! (mod M), G[k]=(k!)^(-1) (mod M)
[計算量]
O(N+log Mod)
"""
assert Mod>0
F=Factor_Modulo(N,Mod,Mode=1)
G=[0]*(N+1)
G[-1]=F[-1].inverse()
for k in range(N,0,-1):
G[k-1]=k*G[k]
return F,G
#==================================================
def nCr(n,r):
return F[n]*G[r]*G[n-r]
#==================================================
N,M=map(int,input().split())
A=list(map(int,input().split()))
inf=float("inf")
DP=[inf]*(M+1); DP[0]=0
for a in A:
for x in range(a,M+1):
DP[x]=min(DP[x],DP[x-a]+1)
X=0
Mod=998244353
F,G=Factor_Modulo_with_Inverse(M+1,Mod)
for k in range(M+1):
if DP[k]<inf:
X+=nCr(M-DP[k],k-DP[k])
print(X.a)