結果
問題 | No.1340 おーじ君をさがせ |
ユーザー |
👑 ![]() |
提出日時 | 2021-01-15 22:16:04 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 737 ms / 2,000 ms |
コード長 | 6,774 bytes |
コンパイル時間 | 152 ms |
コンパイル使用メモリ | 82,176 KB |
実行使用メモリ | 81,280 KB |
最終ジャッジ日時 | 2024-11-27 23:11:03 |
合計ジャッジ時間 | 12,309 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 59 |
ソースコード
from copy import copy,deepcopyclass Matrix_Error(Exception):passclass Matrix():#入力def __init__(self,M=[]):self.ele=MR=len(M)if R!=0:C=len(M[0])else:C=0self.row=Rself.col=Cself.size=(R,C)#出力def __str__(self):T=""(r,c)=self.sizefor i in range(r):U="["for j in range(c):U+=str(self.ele[i][j])+" "T+=U[:-1]+"]\n"return "["+T[:-1]+"]"#+,-def __pos__(self):return selfdef __neg__(self):return self.__scale__(-1)#加法def __add__(self,other):A=selfB=otherif A.size!=B.size:raise Matrix_Error("2つの行列のサイズが異なります.({},{})".format(A.size,B.size))M=A.eleN=B.eleL=[]for i in range(A.row):E=[]for j in range(A.col):E.append(M[i][j]|N[i][j])L.append(E)return Matrix(L)#減法def __sub__(self,other):return self+(-other)#乗法def __mul__(self,other):A=selfB=otherif isinstance(B,Matrix):R=A.rowC=B.colif A.col!=B.row:raise Matrix_Error("左側の列と右側の行が一致しません.({},{})".format(A.size,B.size))G=A.colM=A.eleN=B.eleE=[]for i in range(R):F=[]for j in range(C):S=0for k in range(G):S|=M[i][k]&N[k][j]F.append(S)E.append(F)return Matrix(E)elif isinstance(B,int):return A.__scale__(B)def __rmul__(self,other):if isinstance(other,int):return self*otherdef Inverse(self):from copy import copyM=selfif M.row!=M.col:raise Matrix_Error("正方行列ではありません.")R=M.rowI=[[1*(i==j) for j in range(R)] for i in range(R)]G=M.Column_Union(Matrix(I))G=G.Row_Reduce()A,B=[],[]for i in range(R):A.append(copy(G.ele[i][:R]))B.append(copy(G.ele[i][R:]))if A==I:return Matrix(B)else:raise Matrix_Error("正則ではありません.")#スカラー倍def __scale__(self,r):M=self.eleL=[[r*M[i][j] for j in range(self.col)] for i in range(self.row)]return Matrix(L)#累乗def __pow__(self,n):A=selfif A.row!=A.col:raise Matrix_Error("正方行列ではありません.")if n<0:return (A**(-n)).Inverse()R=Matrix([[1*(i==j) for j in range(A.row)] for i in range(A.row)])D=Awhile n>0:if n%2==1:R*=DD*=Dn=n>>1return R#等号def __eq__(self,other):A=selfB=otherif A.size!=B.size:return Falsefor i in range(A.row):for j in range(A.col):if A.ele[i][j]!=B.ele[i][j]:return Falsereturn True#不等号def __neq__(self,other):return not(self==other)#転置def Transpose(self):self.col,self.row=self.row,self.colself.ele=list(map(list,zip(*self.ele)))#行基本変形def Row_Reduce(self):M=self(R,C)=M.sizeT=[]for i in range(R):U=[]for j in range(C):U.append(M.ele[i][j])T.append(U)I=0for J in range(C):if T[I][J]==0:for i in range(I+1,R):if T[i][J]!=0:T[i],T[I]=T[I],T[i]breakif T[I][J]!=0:u=T[I][J]for j in range(C):T[I][j]/=ufor i in range(R):if i!=I:v=T[i][J]for j in range(C):T[i][j]-=v*T[I][j]I+=1if I==R:breakreturn Matrix(T)#列基本変形def Column_Reduce(self):M=self(R,C)=M.sizeT=[]for i in range(R):U=[]for j in range(C):U.append(M.ele[i][j])T.append(U)J=0for I in range(R):if T[I][J]==0:for j in range(J+1,C):if T[I][j]!=0:for k in range(R):T[k][j],T[k][J]=T[k][J],T[k][j]breakif T[I][J]!=0:u=T[I][J]for i in range(R):T[i][J]/=ufor j in range(C):if j!=J:v=T[I][j]for i in range(R):T[i][j]-=v*T[i][J]J+=1if J==C:breakreturn Matrix(T)#行列の階数def Rank(self,ep=None):M=self.Row_Reduce()(R,C)=M.sizeT=M.eleS=0for i in range(R):f=Falseif ep==None:for j in range(C):if T[i][j]!=0:f=Trueelse:for j in range(C):if abs(T[i][j])>=ep:f=Trueif f:S+=1else:breakreturn S#行の結合def Row_Union(self,other):return Matrix(self.ele+other.ele)#列の結合def Column_Union(self,other):E=[]for i in range(self.row):E.append(self.ele[i]+other.ele[i])return Matrix(E)def __getitem__(self,index):assert isinstance(index,tuple) and len(index)==2return self.ele[index[0]][index[1]]def __setitem__(self,index,val):assert isinstance(index,tuple) and len(index)==2self.ele[index[0]][index[1]]=val#================================================import sysinput=sys.stdin.readlineN,M,T=map(int,input().split())X=Matrix([[0]*N for _ in range(N)])for _ in range(M):a,b=map(int,input().split())X[b,a]=1v=X**T*Matrix([[1 if i==0 else 0] for i in range(N)])K=0for i in range(N):if v[i,0]:K+=1print(K)