結果
問題 | No.1340 おーじ君をさがせ |
ユーザー |
|
提出日時 | 2021-01-15 21:49:38 |
言語 | PyPy3 (7.3.15) |
結果 |
TLE
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 3,423 bytes |
コンパイル時間 | 342 ms |
コンパイル使用メモリ | 82,376 KB |
実行使用メモリ | 81,208 KB |
最終ジャッジ日時 | 2024-11-26 19:36:23 |
合計ジャッジ時間 | 14,230 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 58 TLE * 1 |
ソースコード
class Matrix():mod=10**9+7def set_mod(m):Matrix.mod=mdef __init__(self,L):self.row=len(L)self.column=len(L[0])self._matrix=Lfor i in range(self.row):for j in range(self.column):self._matrix[i][j]%=Matrix.moddef __getitem__(self,item):if type(item)==int:raise IndexError("you must specific row and column")elif len(item)!=2:raise IndexError("you must specific row and column")i,j=itemreturn self._matrix[i][j]def __setitem__(self,item,val):if type(item)==int:raise IndexError("you must specific row and column")elif len(item)!=2:raise IndexError("you must specific row and column")i,j=itemself._matrix[i][j]=valdef __add__(self,other):if (self.row,self.column)!=(other.row,other.column):raise SizeError("sizes of matrixes are different")res=[[0 for j in range(self.column)] for i in range(self.row)]for i in range(self.row):for j in range(self.column):res[i][j]=self._matrix[i][j]+other._matrix[i][j]res[i][j]%=Matrix.modreturn Matrix(res)def __sub__(self,other):if (self.row,self.column)!=(other.row,other.column):raise SizeError("sizes of matrixes are different")res=[[0 for j in range(self.column)] for i in range(self.row)]for i in range(self.row):for j in range(self.column):res[i][j]=self._matrix[i][j]-other._matrix[i][j]res[i][j]%=Matrix.modreturn Matrix(res)def __mul__(self,other):if type(other)!=int:if self.column!=other.row:raise SizeError("sizes of matrixes are different")res=[[0 for j in range(other.column)] for i in range(self.row)]for i in range(self.row):for j in range(other.column):temp=0for k in range(self.column):if self._matrix[i][k] and other._matrix[k][j]:temp = 1res[i][j]=tempreturn Matrix(res)else:n=otherres=[[(n*self._matrix[i][j])%Matrix.mod for j in range(self.column)] for i in range(self.row)]return Matrix(res)def __pow__(self,m):if self.column!=self.row:raise MatrixPowError("the size of row must be the same as that of column")n=self.rowres=Matrix([[int(i==j) for i in range(n)] for j in range(n)])while m:if m%2==1:res=res*selfself=self*selfm//=2return resdef __str__(self):res=[]for i in range(self.row):for j in range(self.column):res.append(str(self._matrix[i][j]))res.append(" ")res.append("\n")res=res[:len(res)-1]return "".join(res)N,M,T = map(int,input().split())A = [[0 for j in range(N)] for i in range(N)]for i in range(M):a,b = map(int,input().split())if not A[b][a]:A[b][a] = 1A = Matrix(A)A = A**TB = [[1]] + [[0]] * (N-1)B = Matrix(B)A = A*Bres = 0for i in range(N):if A[i,0]:res += 1print(res)