結果
問題 | No.1706 Many Bus Stops (hard) |
ユーザー |
👑 ![]() |
提出日時 | 2021-10-08 22:54:42 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 8,448 bytes |
コンパイル時間 | 361 ms |
コンパイル使用メモリ | 82,048 KB |
実行使用メモリ | 73,600 KB |
最終ジャッジ日時 | 2024-07-23 06:06:24 |
合計ジャッジ時間 | 5,337 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 1 WA * 40 |
ソースコード
from copy import copy,deepcopyfrom typing import Matchclass 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 __repr__(self):return str(self)#+,-def __pos__(self):return selfdef __neg__(self):return self.__scale__(-1)#加法def __add__(self,other):self.__is_calculatable(other)M=self.ele; N=other.eleL=[[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.elefor i in range(self.row):Mi,Ni=M[i],N[i]for j in range(self.col):Mi[j]+=Ni[j]Mi[j]%=self.Modreturn self#減法def __sub__(self,other):self.__is_calculatable(other)M=self.ele; N=other.eleL=[[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.elefor i in range(self.row):Mi,Ni=M[i],N[i]for j in range(self.col):Mi[j]-=Ni[j]Mi[j]%=self.Modreturn 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.eleE=[[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.Modreturn 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=selfN=M.row; Mod=M.ModR=[[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]:breakelse: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]%=ModRj[k]*=inv; Rj[k]%=Modfor i in range(N):if i==j: continuec=T[i][j]Ti,Ri=T[i],R[i]for k in range(N):Ti[k]-=Tj[k]*c; Ti[k]%=ModRi[k]-=Rj[k]*c; Ri[k]%=Modreturn Modulo_Matrix(R,Mod)#スカラー倍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#==================================================C,N,M=map(int,input().split())Mod=10**9+7S=pow(C,Mod-2,Mod)X=Modulo_Matrix([[0]*4 for _ in range(4)],Mod)Data=[(0,0,S), (0,3,1-S),(1,1,1-S), (1,2,S),(2,0,1), (3,1,1)]for a,b,p in Data:X[a,b]=pProb=(X**N)[0,0]print((1-pow(1-Prob,M,Mod))%Mod)