結果
問題 | No.1340 おーじ君をさがせ |
ユーザー |
👑 ![]() |
提出日時 | 2021-01-15 22:10:20 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 7,137 bytes |
コンパイル時間 | 463 ms |
コンパイル使用メモリ | 82,176 KB |
実行使用メモリ | 81,736 KB |
最終ジャッジ日時 | 2024-11-26 20:25:48 |
合計ジャッジ時間 | 31,317 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 57 WA * 2 |
ソースコード
from copy import copy,deepcopyclass Modulo_Matrix_Error(Exception):passclass Modulo_Matrix():#入力def __init__(self,M,Mod):self.ele=[[x%Mod for x in X] for X in M]self.Mod=ModR=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 Modulo_Matrix_Error("2つの行列のサイズが異なります.({},{})".format(A.size,B.size))M=A.eleN=B.eleL=[0]*self.rowfor i in range(A.row):E,F=M[i],N[i]L[i]=[(E[j]+F[j])%self.Mod for j in range(self.col)]return Modulo_Matrix(L,self.Mod)#減法def __sub__(self,other):return self+(-other)#乗法def __mul__(self,other):A=selfB=otherif isinstance(B,Modulo_Matrix):R=A.rowC=B.colif A.col!=B.row:raise Modulo_Matrix_Error("左側の列と右側の行が一致しません.({},{})".format(A.size,B.size))G=A.colM=A.eleN=B.eleE=[[0]*other.col for _ in range(self.row)]for i in range(R):F=M[i]for j in range(C):for k in range(G):E[i][j]=(E[i][j]+F[k]*N[k][j])%self.Modreturn Modulo_Matrix(E,self.Mod)elif isinstance(B,int):return A.__scale__(B)def __rmul__(self,other):if isinstance(other,int):return self*otherdef Inverse(self):M=selfif M.row!=M.col:raise Modulo_Matrix_Error("正方行列ではありません.")R=M.rowI=[[1*(i==j) for j in range(R)] for i in range(R)]G=M.Column_Union(Modulo_Matrix(I,self.Mod))G=G.Row_Reduce()A,B=[None]*R,[None]*Rfor i in range(R):A[i]=G.ele[i][:R]B[i]=G.ele[i][R:]if A==I:return Modulo_Matrix(B,self.Mod)else:raise Modulo_Matrix_Error("正則ではありません.")#スカラー倍def __scale__(self,r):M=self.eleL=[[(r*M[i][j])%self.Mod for j in range(self.col)] for i in range(self.row)]return Modulo_Matrix(L,self.Mod)#累乗def __pow__(self,n):A=selfif A.row!=A.col:raise Modulo_Matrix_Error("正方行列ではありません.")if n<0:return (A**(-n)).Inverse()R=Modulo_Matrix([[1*(i==j) for j in range(A.row)] for i in range(A.row)],self.Mod)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]u_inv=pow(u,self.Mod-2,self.Mod)for j in range(C):T[I][j]*=u_invT[I][j]%=self.Modfor i in range(R):if i!=I:v=T[i][J]for j in range(C):T[i][j]-=v*T[I][j]T[i][j]%=self.ModI+=1if I==R:breakreturn Modulo_Matrix(T,self.Mod)#列基本変形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]u_inv=pow(u,self.Mod-2,self.Mod)for i in range(R):T[i][J]*=u_invT[i][J]%=self.Modfor j in range(C):if j!=J:v=T[I][j]for i in range(R):T[i][j]-=v*T[i][J]T[i][j]%=self.ModJ+=1if J==C:breakreturn Modulo_Matrix(T,self.Mod)#行列の階数def Rank(self):M=self.Row_Reduce()(R,C)=M.sizeT=M.eleS=0for i in range(R):f=Falsefor j in range(C):if T[i][j]!=0:f=Truebreakif f:S+=1else:breakreturn S#行の結合def Row_Union(self,other):return Modulo_Matrix(self.ele+other.ele,self.Mod)#列の結合def Column_Union(self,other):E=[]for i in range(self.row):E.append(self.ele[i]+other.ele[i])return Modulo_Matrix(E,self.Mod)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())Mod=10**9+7X=Modulo_Matrix([[0]*N for _ in range(N)],Mod)for _ in range(M):a,b=map(int,input().split())X[b,a]=1v=X**T*Modulo_Matrix([[1 if i==0 else 0] for i in range(N)],Mod)K=0for i in range(N):if v[i,0]:K+=1print(K)