結果

問題 No.1704 Many Bus Stops (easy)
ユーザー kohei2019
提出日時 2023-06-04 20:04:02
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 556 ms / 2,000 ms
コード長 7,560 bytes
コンパイル時間 405 ms
コンパイル使用メモリ 82,048 KB
実行使用メモリ 80,128 KB
最終ジャッジ日時 2024-12-29 03:45:54
合計ジャッジ時間 17,736 ms
ジャッジサーバーID
(参考情報)
judge3 / judge4
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 1
other AC * 41
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

import copy
class matrix():
def __init__(self):
self.mod = 10**9+7
def multiplication(self,arr1,arr2):
'''
arr1
2 3 4 5
6 7 8 9
arr2
1 2
3 4
5 6
7 8
'''
H = len(arr1)
W = len(arr2[0])
arr3 = [[0]*W for i in range(H)]
for i in range(H):
for j in range(W):
val = 0
for k in range(len(arr1[0])):
val += arr1[i][k]*arr2[k][j]
arr3[i][j] = val
return arr3
def determinant(self,arr):
'''
N*N
O(N**3)
'''
arr_calc = copy.deepcopy(arr)
N = len(arr_calc)
for i in range(N-1):
d = arr_calc[i][i]
for j in range(i+1,N):
e = arr_calc[j][i]/d
for k in range(i,N):
arr_calc[j][k] -= e*arr_calc[i][k]
#arr_calc
det = 1
for i in range(N):
det *= arr_calc[i][i]
return det
def invarr(self,arr):
'''
N*N
det == 0return False
O(N**3)
'''
arr_calc = copy.deepcopy(arr)
if self.determinant(arr_calc) == 0:
return False
N = len(arr_calc)
for i in range(N):
v = [0]*(N)
v[i] = 1
arr_calc[i].extend(v)
for i in range(N-1):
d = arr_calc[i][i]
for j in range(i+1,N):
e = arr_calc[j][i]/d
for k in range(i,2*N):
arr_calc[j][k] -= e*arr_calc[i][k]
for i in range(N-1,-1,-1):
d = arr_calc[i][i]
for k in range(i,2*N):
arr_calc[i][k] /= d
for j in range(i-1,-1,-1):
c = arr_calc[j][i]
for k in range(i,2*N):
arr_calc[j][k] -= c*arr_calc[i][k]
inv = [[0]*(N) for i in range(N)]
for i in range(N):
for j in range(N):
inv[i][j] = arr_calc[i][j+N]
return inv
def SimultaneousE(self,arr):
'''
3x+2y+z = 4
4x+5y+6z = 3
7x+8y+9z = 2
->
3 2 1 4
4 5 6 3
7 8 9 2
'''
N = len(arr)
arr1 = [[0]*(N) for i in range(N)]
for i in range(N):
for j in range(N):
arr1[i][j] = arr[i][j]
v = [[0] for i in range(N)]
for i in range(N):
v[i][0] = arr[i][-1]
if self.determinant(arr1) == 0:
return False
inva = self.invarr(arr1)
return self.multiplication(inva,v)
def invmod(self,a):#mod
if a == 0:
return 0
if a == 1:
return 1
return (-self.invmod(self.mod % a) * (self.mod // a)) % self.mod
def multiplication_mod(self,arr1,arr2):
H = len(arr1)
W = len(arr2[0])
arr3 = [[0]*W for i in range(H)]
for i in range(H):
for j in range(W):
val = 0
for k in range(len(arr1[0])):
val += arr1[i][k]*arr2[k][j]
arr3[i][j] = val%self.mod
return arr3
def determinant_mod(self,arr):
'''
N*N
O(N**3)
'''
arr_calc = copy.deepcopy(arr)
N = len(arr_calc)
for i in range(N-1):
d = arr_calc[i][i]
for j in range(i+1,N):
e = arr_calc[j][i]*self.invmod(d)
e %= self.mod
for k in range(i,N):
arr_calc[j][k] -= e*arr_calc[i][k]
arr_calc[j][k] %= self.mod
#arr_calc
det = 1
for i in range(N):
det *= arr_calc[i][i]
det %= self.mod
return det
def invarr_mod(self,arr):
'''
N*N
det == 0return False
O(N**3)
'''
arr_calc = copy.deepcopy(arr)
det = self.determinant_mod(arr_calc)
if det == 0:
return False
N = len(arr_calc)
for i in range(N):
v = [0]*(N)
v[i] = det
arr_calc[i].extend(v)
for i in range(N-1):
d = arr_calc[i][i]
for j in range(i+1,N):
e = arr_calc[j][i]*self.invmod(d)
for k in range(i,2*N):
arr_calc[j][k] -= e*arr_calc[i][k]
arr_calc[j][k] %= self.mod
for i in range(N-1,-1,-1):
d = arr_calc[i][i]
for k in range(i,2*N):
arr_calc[i][k] *= self.invmod(d)
for j in range(i-1,-1,-1):
c = arr_calc[j][i]
for k in range(i,2*N):
arr_calc[j][k] -= c*arr_calc[i][k]
arr_calc[j][k] %= self.mod
inv = [[0]*(N) for i in range(N)]
for i in range(N):
for j in range(N):
inv[i][j] = arr_calc[i][j+N]*self.invmod(det)%self.mod
return inv
def SimultaneousE_mod(self,arr):
'''
3x+2y+z = 4
4x+5y+6z = 3
7x+8y+9z = 2
->
3 2 1 4
4 5 6 3
7 8 9 2
'''
N = len(arr)
arr1 = [[0]*(N) for i in range(N)]
for i in range(N):
for j in range(N):
arr1[i][j] = arr[i][j]
v = [[0] for i in range(N)]
for i in range(N):
v[i][0] = arr[i][-1]
det = self.determinant_mod(arr1)
if det == 0:
return False
inva = self.invarr_mod(arr1)
v2 = self.multiplication_mod(inva,v)
for i in range(N):
v2[i][0] %= self.mod
return v2
def modPow_matrix(self,arr,n):
'''
N*Narrn
'''
N = len(arr)
if n==0:
arr1 = [[0]*(N) for i in range(N)]
for i in range(N):
arr1[i][i] = 1
return arr1
if n==1:
for i in range(N):
for j in range(N):
arr[i][j] %= self.mod
return arr
if n % 2 == 1:
arr2 = self.multiplication_mod(arr,self.modPow_matrix(arr,n-1))
return arr2
arr3 = self.modPow_matrix(arr,n//2)
return self.multiplication_mod(arr3,arr3)
def Pow_matrix(self,arr,n):
'''
N*Narrn
'''
N = len(arr)
if n==0:
arr1 = [[0]*(N) for i in range(N)]
for i in range(N):
arr1[i][i] = 1
return arr1
if n==1:
return arr
if n % 2 == 1:
arr2 = self.multiplication(arr,self.Pow_matrix(arr,n-1))
return arr2
arr3 = self.Pow_matrix(arr,n//2)
return self.multiplication(arr3,arr3)
T = int(input())
mod = 10**9+7
MX = matrix()
one_3 = MX.invmod(3)
two_3 = (2*MX.invmod(3))%mod
one_2 = MX.invmod(2)
arr = [[one_3,0,0,two_3,0,0],[0,one_3,0,0,two_3,0],[0,0,one_3,0,0,two_3],[0,one_2,one_2,0,0,0],[one_2,0,one_2,0,0,0],[one_2,one_2,0,0,0,0]]
ansls = []
for i in range(T):
N = int(input())
m = MX.modPow_matrix(arr, N)
ans = MX.multiplication_mod(m,[[1],[0],[0],[0],[0],[0]])
ansls.append(ans[0][0])
print(*ansls,sep='\n')
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0