結果
問題 | No.1704 Many Bus Stops (easy) |
ユーザー | 👑 Kazun |
提出日時 | 2021-10-08 23:07:22 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 755 ms / 2,000 ms |
コード長 | 8,458 bytes |
コンパイル時間 | 391 ms |
コンパイル使用メモリ | 87,124 KB |
実行使用メモリ | 89,976 KB |
最終ジャッジ日時 | 2023-09-30 12:36:01 |
合計ジャッジ時間 | 26,836 ms |
ジャッジサーバーID (参考情報) |
judge13 / judge12 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 188 ms
84,656 KB |
testcase_01 | AC | 694 ms
88,804 KB |
testcase_02 | AC | 464 ms
87,932 KB |
testcase_03 | AC | 465 ms
87,920 KB |
testcase_04 | AC | 470 ms
87,908 KB |
testcase_05 | AC | 495 ms
89,048 KB |
testcase_06 | AC | 478 ms
88,140 KB |
testcase_07 | AC | 491 ms
87,980 KB |
testcase_08 | AC | 490 ms
88,184 KB |
testcase_09 | AC | 444 ms
88,112 KB |
testcase_10 | AC | 471 ms
88,480 KB |
testcase_11 | AC | 472 ms
87,996 KB |
testcase_12 | AC | 472 ms
87,980 KB |
testcase_13 | AC | 475 ms
88,584 KB |
testcase_14 | AC | 479 ms
88,476 KB |
testcase_15 | AC | 479 ms
89,300 KB |
testcase_16 | AC | 469 ms
87,876 KB |
testcase_17 | AC | 473 ms
88,700 KB |
testcase_18 | AC | 472 ms
87,872 KB |
testcase_19 | AC | 476 ms
88,184 KB |
testcase_20 | AC | 480 ms
87,944 KB |
testcase_21 | AC | 472 ms
88,008 KB |
testcase_22 | AC | 705 ms
88,616 KB |
testcase_23 | AC | 717 ms
89,228 KB |
testcase_24 | AC | 696 ms
89,332 KB |
testcase_25 | AC | 708 ms
89,400 KB |
testcase_26 | AC | 721 ms
89,976 KB |
testcase_27 | AC | 709 ms
89,244 KB |
testcase_28 | AC | 702 ms
89,416 KB |
testcase_29 | AC | 696 ms
88,776 KB |
testcase_30 | AC | 709 ms
88,880 KB |
testcase_31 | AC | 699 ms
89,156 KB |
testcase_32 | AC | 699 ms
88,956 KB |
testcase_33 | AC | 755 ms
88,032 KB |
testcase_34 | AC | 719 ms
89,536 KB |
testcase_35 | AC | 706 ms
88,596 KB |
testcase_36 | AC | 712 ms
89,400 KB |
testcase_37 | AC | 717 ms
88,864 KB |
testcase_38 | AC | 700 ms
89,264 KB |
testcase_39 | AC | 706 ms
89,140 KB |
testcase_40 | AC | 702 ms
89,640 KB |
testcase_41 | AC | 696 ms
88,980 KB |
ソースコード
from copy import copy,deepcopy from typing import Match class Modulo_Matrix_Error(Exception): pass class Modulo_Matrix(): #入力 def __init__(self,M,Mod): self.ele=[[x%Mod for x in X] for X in M] self.Mod=Mod R=len(M) if R!=0: C=len(M[0]) else: C=0 self.row=R self.col=C self.size=(R,C) #出力 def __str__(self): T="" (r,c)=self.size for i in range(r): U="[" for j in range(c): U+=str(self.ele[i][j])+" " T+=U[:-1]+"]\n" return "["+T[:-1]+"]" def __repr__(self): return str(self) #+,- def __pos__(self): return self def __neg__(self): return self.__scale__(-1) #加法 def __add__(self,other): self.__is_calculatable(other) M=self.ele; N=other.ele L=[[0]*self.col for _ in range(self.row)] for i in range(self.row): Li,Mi,Ni=L[i],M[i],N[i] for j in range(self.col): Li[j]=Mi[j]+Ni[j] return Modulo_Matrix(L,self.Mod) def __iadd__(self,other): self.__is_calculatable(other) M=self.ele; N=other.ele for i in range(self.row): Mi,Ni=M[i],N[i] for j in range(self.col): Mi[j]+=Ni[j] Mi[j]%=self.Mod return self #減法 def __sub__(self,other): self.__is_calculatable(other) M=self.ele; N=other.ele L=[[0]*self.col for _ in range(self.row)] for i in range(self.row): Li,Mi,Ni=L[i],M[i],N[i] for j in range(self.col): Li[j]=Mi[j]-Ni[j] return Modulo_Matrix(L,self.Mod) def __isub__(self,other): self.__is_calculatable(other) M=self.ele; N=other.ele for i in range(self.row): Mi,Ni=M[i],N[i] for j in range(self.col): Mi[j]-=Ni[j] Mi[j]%=self.Mod return self #乗法 def __mul__(self,other): if isinstance(other,Modulo_Matrix): if self.col!=other.row: raise Modulo_Matrix_Error("左側の列と右側の行が一致しません.({},{})".format(self.size,other.size)) M=self.ele; N=other.ele E=[[0]*other.col for _ in range(self.row)] for i in range(self.row): Ei,Mi=E[i],M[i] for k in range(self.col): m_ik,Nk=Mi[k],N[k] for j in range(other.col): Ei[j]+=m_ik*Nk[j] Ei[j]%=self.Mod return Modulo_Matrix(E,self.Mod) elif isinstance(other,int): return self.__scale__(other) def __rmul__(self,other): if isinstance(other,int): return self.__scale__(other) def Inverse(self): if self.row!=self.col: raise Modulo_Matrix_Error("正方行列ではありません.") M=self N=M.row; Mod=M.Mod R=[[int(i==j) for j in range(N)] for i in range(N)] T=deepcopy(M.ele) for j in range(N): if T[j][j]==0: for i in range(j+1,N): if T[i][j]: break else: raise Modulo_Matrix_Error("正則行列ではありません") T[j],T[i]=T[i],T[j] R[j],R[i]=R[i],R[j] Tj,Rj=T[j],R[j] inv=pow(Tj[j],Mod-2,Mod) for k in range(N): Tj[k]*=inv; Tj[k]%=Mod Rj[k]*=inv; Rj[k]%=Mod for i in range(N): if i==j: continue c=T[i][j] Ti,Ri=T[i],R[i] for k in range(N): Ti[k]-=Tj[k]*c; Ti[k]%=Mod Ri[k]-=Rj[k]*c; Ri[k]%=Mod return Modulo_Matrix(R,Mod) #スカラー倍 def __scale__(self,r): M=self.ele L=[[(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=self if 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=A while n>0: if n%2==1: R*=D D*=D n=n>>1 return R #等号 def __eq__(self,other): A=self B=other if A.size!=B.size: return False for i in range(A.row): for j in range(A.col): if A.ele[i][j]!=B.ele[i][j]: return False return True #不等号 def __neq__(self,other): return not(self==other) #転置 def Transpose(self): self.col,self.row=self.row,self.col self.ele=list(map(list,zip(*self.ele))) #行基本変形 def Row_Reduce(self): M=self (R,C)=M.size T=[] for i in range(R): U=[] for j in range(C): U.append(M.ele[i][j]) T.append(U) I=0 for 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] break if 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_inv T[I][j]%=self.Mod for 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.Mod I+=1 if I==R: break return Modulo_Matrix(T,self.Mod) #列基本変形 def Column_Reduce(self): M=self (R,C)=M.size T=[] for i in range(R): U=[] for j in range(C): U.append(M.ele[i][j]) T.append(U) J=0 for 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] break if 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_inv T[i][J]%=self.Mod for 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.Mod J+=1 if J==C: break return Modulo_Matrix(T,self.Mod) #行列の階数 def Rank(self): M=self.Row_Reduce() (R,C)=M.size T=M.ele S=0 for i in range(R): f=False for j in range(C): if T[i][j]!=0: f=True break if f: S+=1 else: break return 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)==2 return self.ele[index[0]][index[1]] def __setitem__(self,index,val): assert isinstance(index,tuple) and len(index)==2 self.ele[index[0]][index[1]]=val #================================================== Mod=10**9+7 M=3 S=pow(M,Mod-2,Mod) X=Modulo_Matrix([[0]*4 for _ in range(4)],Mod) Data=[ (0,0,S), (0,3,1-S), (1,1,S), (1,2,S), (1,3,1-2*S), (2,0,1), (3,1,1) ] for a,b,p in Data: X[a,b]=p T=int(input()) for _ in range(T): N=int(input()) print((X**N)[0,0])