結果
問題 | No.1073 無限すごろく |
ユーザー | Keroru |
提出日時 | 2020-06-11 21:53:02 |
言語 | Python3 (3.12.2 + numpy 1.26.4 + scipy 1.12.0) |
結果 |
AC
|
実行時間 | 22 ms / 2,000 ms |
コード長 | 5,156 bytes |
コンパイル時間 | 103 ms |
コンパイル使用メモリ | 11,500 KB |
実行使用メモリ | 8,512 KB |
最終ジャッジ日時 | 2023-09-06 08:38:06 |
合計ジャッジ時間 | 3,197 ms |
ジャッジサーバーID (参考情報) |
judge13 / judge12 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 19 ms
8,416 KB |
testcase_01 | AC | 19 ms
8,356 KB |
testcase_02 | AC | 19 ms
8,400 KB |
testcase_03 | AC | 18 ms
8,460 KB |
testcase_04 | AC | 17 ms
8,364 KB |
testcase_05 | AC | 18 ms
8,284 KB |
testcase_06 | AC | 17 ms
8,288 KB |
testcase_07 | AC | 18 ms
8,364 KB |
testcase_08 | AC | 18 ms
8,324 KB |
testcase_09 | AC | 17 ms
8,416 KB |
testcase_10 | AC | 17 ms
8,416 KB |
testcase_11 | AC | 17 ms
8,356 KB |
testcase_12 | AC | 18 ms
8,328 KB |
testcase_13 | AC | 18 ms
8,284 KB |
testcase_14 | AC | 19 ms
8,356 KB |
testcase_15 | AC | 18 ms
8,416 KB |
testcase_16 | AC | 19 ms
8,344 KB |
testcase_17 | AC | 19 ms
8,348 KB |
testcase_18 | AC | 19 ms
8,512 KB |
testcase_19 | AC | 19 ms
8,360 KB |
testcase_20 | AC | 20 ms
8,368 KB |
testcase_21 | AC | 19 ms
8,320 KB |
testcase_22 | AC | 19 ms
8,284 KB |
testcase_23 | AC | 20 ms
8,344 KB |
testcase_24 | AC | 20 ms
8,308 KB |
testcase_25 | AC | 20 ms
8,284 KB |
testcase_26 | AC | 20 ms
8,288 KB |
testcase_27 | AC | 20 ms
8,344 KB |
testcase_28 | AC | 22 ms
8,332 KB |
testcase_29 | AC | 21 ms
8,304 KB |
testcase_30 | AC | 21 ms
8,464 KB |
testcase_31 | AC | 21 ms
8,368 KB |
testcase_32 | AC | 20 ms
8,296 KB |
ソースコード
## Verified by Yukicoder 1073 ## https://yukicoder.me/problems/no/1073 ## ## Matrix Class supporting operators +, -, *, %, +=, -=, *=, %= ## *, *= allows int/float/complex ## ** or pow(self,p,mod) for the size N*N matrix is implemented by Repeated squaring. O(N^3*log(p)) ## ## Constructor: matrix(array), where array is 1D or 2D array. 1-dimensional array X is modified as 2D array of [X]. ## ## methods ## T(): returns transposed matrix ## resize((n,m),fill=0): changes the matrix instance into the new shape (n * m), missing entries are filled with "fill" (default value is zero). class matrix: class MulShapeError(Exception): "mult is not applicable between the two matrices given" pass def __init__(self,arr_input): if hasattr(arr_input[0],"__getitem__"): self.arr=arr_input else: self.arr=[arr_input] self.shape=(len(self.arr),len(self.arr[0])) def __getitem__(self,key): return self.arr[key] def __setitem__(self,key,value): self.arr[key]=value def __iter__(self): return iter(self.arr) def __add__(self,B): if type(B)!=matrix: return NotImplemented if B.shape!=self.shape: return NotImplemented rt=[[0]*self.shape[1] for i in range(self.shape[0])] for i in range(self.shape[0]): for j in range(self.shape[1]): rt[i][j]=self.arr[i][j]+B.arr[i][j] return matrix(rt) def __iadd__(self,B): return self.__add__(B) def __sub__(self,B): if type(B)!=matrix: return NotImplemented if B.shape!=self.shape: return NotImplemented rt=[[0]*self.shape[1] for i in range(self.shape[0])] for i in range(self.shape[0]): for j in range(self.shape[1]): rt[i][j]=self.arr[i][j]-B.arr[i][j] return matrix(rt) def __isub__(self,B): return self.__sub__(B) def __mul__(self,M): if type(M) in [int,float,complex]: M=matrix([[M*(i==j) for j in range(self.shape[1])] for i in range(self.shape[1])]) if type(M)!=matrix: return NotImplemented if M.shape[0]!=self.shape[1]: raise matrix.MulShapeError("mult is not applicable between the matrices of shape "+str(self.shape)+" and "+str(M.shape)) ra,ca=self.shape rb,cb=M.shape c=[[0]*cb for i in range(ra)] for i in range(ra): for j in range(cb): for k in range(ca): c[i][j]+=self.arr[i][k]*M.arr[k][j] return matrix(c) def __imul__(self,M): return self.__mul__(M) def __rmul__(self,M): if type(M) in [int,float,complex]: M=matrix([[M*(i==j) for j in range(self.shape[1])] for i in range(self.shape[1])]) if type(M)!=matrix: return NotImplemented if M.shape[0]!=self.shape[1]: raise matrix.MulShapeError("mult is not applicable between the matrix shape "+str(self.shape)+" and "+str(M.shape)) ra,ca=M.shape rb,cb=self.shape c=[[0]*cb for i in range(ra)] for i in range(ra): for j in range(cb): for k in range(ca): c[i][j]+=M.arr[i][k]*self.arr[k][j] return matrix(c) def __mod__(self,p): if type(p)!=int: return NotImplemented c=[[0]*self.shape[1] for i in range(self.shape[0])] for i in range(self.shape[0]): for j in range(self.shape[1]): c[i][j]=self.arr[i][j]%p return matrix(c) def __imod__(self,p): return self.__mod__(p) def __pow__(self,p,mod=10**9+7): if type(p)!=int or self.shape[0]!=self.shape[1]: return NotImplemented A=matrix(self.arr) R=matrix([[1*(i==j) for j in range(self.shape[0])] for i in range(self.shape[0])]) while p>0: if p&1: R*=A R%=mod A*=A A%=mod p>>=1 return R def __neg__(self): return self.__mul__(-1) def __str__(self): rt='[' for i in self.arr: rt=rt+str(i)+",\n" return rt[:-2]+']' def T(self): rt=[[0]*self.shape[0] for i in range(self.shape[1])] for i in range(self.shape[0]): for j in range(self.shape[1]): rt[j][i]=self.arr[i][j] return matrix(rt) def resize(self,new_shape,fill=0): t_arr=[] for i in self.arr: t_arr+=i t_arr.reverse() n,m=new_shape self.shape=(n,m) self.arr=[[fill]*m for i in range(n)] for i in range(self.shape[0]): for j in range(self.shape[1]): if t_arr: self.arr[i][j]=t_arr.pop() return def view(self): for i in self.arr: print(i) mo=10**9+7 n=int(input()) b=pow(6,mo-2,mo) M=matrix([b]*6) M.resize((6,6)) for i in range(5): M[i+1][i]=1 X=matrix([1]+[0]*5) X.resize((6,1)) M**=n ans=M*X print(ans[0][0])