結果
| 問題 |
No.793 うし数列 2
|
| コンテスト | |
| ユーザー |
 kohei2019
|
| 提出日時 | 2022-04-11 09:36:06 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
AC
|
| 実行時間 | 43 ms / 2,000 ms |
| コード長 | 6,746 bytes |
| コンパイル時間 | 142 ms |
| コンパイル使用メモリ | 82,360 KB |
| 実行使用メモリ | 56,864 KB |
| 最終ジャッジ日時 | 2024-12-15 05:25:06 |
| 合計ジャッジ時間 | 2,046 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge3 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 2 |
| other | AC * 21 |
ソースコード
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 == 0ならreturn 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 == 0ならreturn 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*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] = 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)
N = int(input())
arr = [[10,1],[0,1]]
v = [[1],[3]]
mt = matrix()
arr2 = mt.modPow_matrix(arr, N)
ans = mt.multiplication_mod(arr2, v)
print(ans[0][0])