結果

問題 No.1706 Many Bus Stops (hard)
ユーザー kohei2019
提出日時 2023-06-04 20:26:33
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 57 ms / 2,000 ms
コード長 7,686 bytes
コンパイル時間 359 ms
コンパイル使用メモリ 82,372 KB
実行使用メモリ 64,256 KB
最終ジャッジ日時 2024-12-29 03:48:04
合計ジャッジ時間 3,995 ms
ジャッジサーバーID
(参考情報)
judge2 / judge1
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 2
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)
def modPow(a,n,mod):# a**n % mod
if n==0:
return 1
if n==1:
return a%mod
if n & 1:
return (a*modPow(a,n-1,mod)) % mod
t = modPow(a,n>>1,mod)
return (t*t)%mod
C,N,M = map(int,input().split())
mod = 10**9+7
MX = matrix()
one_c = MX.invmod(C)
one_c1 = MX.invmod(C-1)
arr = [[one_c,0,((C-1)*one_c)%mod,0],[0,one_c,0,((C-1)*one_c)%mod],[0,1,0,0],[one_c1,((C-2)*one_c1)%mod,0,0]]
m = MX.modPow_matrix(arr, N)
ans0 = MX.multiplication_mod(m,[[1],[0],[0],[0]])[0][0]
ans = (1-modPow((1-ans0)%mod,M,mod))%mod
print(ans)
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0