結果
問題 | No.1706 Many Bus Stops (hard) |
ユーザー |
|
提出日時 | 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 |
ソースコード
import copyclass matrix():def __init__(self):self.mod = 10**9+7def multiplication(self,arr1,arr2):'''例arr12 3 4 56 7 8 9arr21 23 45 67 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 = 0for k in range(len(arr1[0])):val += arr1[i][k]*arr2[k][j]arr3[i][j] = valreturn arr3def 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]/dfor k in range(i,N):arr_calc[j][k] -= e*arr_calc[i][k]#arr_calc 上△行列det = 1for i in range(N):det *= arr_calc[i][i]return detdef invarr(self,arr):'''正方行列N*Nの逆行列det == 0ならreturn False計算量O(N**3)'''arr_calc = copy.deepcopy(arr)if self.determinant(arr_calc) == 0:return FalseN = len(arr_calc)for i in range(N):v = [0]*(N)v[i] = 1arr_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]/dfor 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] /= dfor 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 invdef SimultaneousE(self,arr):'''3x+2y+z = 44x+5y+6z = 37x+8y+9z = 2->3 2 1 44 5 6 37 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 Falseinva = self.invarr(arr1)return self.multiplication(inva,v)def invmod(self,a):#mod逆元if a == 0:return 0if a == 1:return 1return (-self.invmod(self.mod % a) * (self.mod // a)) % self.moddef 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 = 0for k in range(len(arr1[0])):val += arr1[i][k]*arr2[k][j]arr3[i][j] = val%self.modreturn arr3def 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.modfor k in range(i,N):arr_calc[j][k] -= e*arr_calc[i][k]arr_calc[j][k] %= self.mod#arr_calc 上△行列det = 1for i in range(N):det *= arr_calc[i][i]det %= self.modreturn detdef invarr_mod(self,arr):'''正方行列N*Nの逆行列det == 0ならreturn False計算量O(N**3)'''arr_calc = copy.deepcopy(arr)det = self.determinant_mod(arr_calc)if det == 0:return FalseN = len(arr_calc)for i in range(N):v = [0]*(N)v[i] = detarr_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.modfor 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.modinv = [[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.modreturn invdef SimultaneousE_mod(self,arr):'''3x+2y+z = 44x+5y+6z = 37x+8y+9z = 2->3 2 1 44 5 6 37 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 Falseinva = self.invarr_mod(arr1)v2 = self.multiplication_mod(inva,v)for i in range(N):v2[i][0] %= self.modreturn v2def modPow_matrix(self,arr,n):'''N*Nの正方行列arrをn乗する。'''N = len(arr)if n==0:arr1 = [[0]*(N) for i in range(N)]for i in range(N):arr1[i][i] = 1return arr1if n==1:for i in range(N):for j in range(N):arr[i][j] %= self.modreturn arrif n % 2 == 1:arr2 = self.multiplication_mod(arr,self.modPow_matrix(arr,n-1))return arr2arr3 = self.modPow_matrix(arr,n//2)return self.multiplication_mod(arr3,arr3)def Pow_matrix(self,arr,n):'''N*Nの正方行列arrをn乗する。'''N = len(arr)if n==0:arr1 = [[0]*(N) for i in range(N)]for i in range(N):arr1[i][i] = 1return arr1if n==1:return arrif n % 2 == 1:arr2 = self.multiplication(arr,self.Pow_matrix(arr,n-1))return arr2arr3 = self.Pow_matrix(arr,n//2)return self.multiplication(arr3,arr3)def modPow(a,n,mod):#繰り返し二乗法 a**n % modif n==0:return 1if n==1:return a%modif n & 1:return (a*modPow(a,n-1,mod)) % modt = modPow(a,n>>1,mod)return (t*t)%modC,N,M = map(int,input().split())mod = 10**9+7MX = 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))%modprint(ans)