結果
問題 | No.891 隣接3項間の漸化式 |
ユーザー |
![]() |
提出日時 | 2020-07-05 16:50:17 |
言語 | Python3 (3.13.1 + numpy 2.2.1 + scipy 1.14.1) |
結果 |
AC
|
実行時間 | 34 ms / 2,000 ms |
コード長 | 5,802 bytes |
コンパイル時間 | 85 ms |
コンパイル使用メモリ | 13,440 KB |
実行使用メモリ | 11,520 KB |
最終ジャッジ日時 | 2024-09-22 14:21:51 |
合計ジャッジ時間 | 2,569 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 39 |
ソースコード
class SquareMatrix():def __init__(self, n, mod=1000000007):self.n = nself.mat = [[0 for j in range(n)] for i in range(n)]self.mod = mod@staticmethoddef id(n, mod=1000000007):res = SquareMatrix(n, mod)for i in range(n):res.mat[i][i] = 1return res@staticmethoddef modinv(n, mod):assert n % mod != 0c0, c1 = n, moda0, a1 = 1, 0b0, b1 = 0, 1while c1:a0, a1 = a1, a0 - c0 // c1 * a1b0, b1 = b1, b0 - c0 // c1 * b1c0, c1 = c1, c0 % c1return a0 % moddef set(self, arr):for i in range(self.n):for j in range(self.n):self.mat[i][j] = arr[i][j] % self.moddef operate(self, vec):assert len(vec) == self.nres = [0 for _ in range(self.n)]for i in range(self.n):for j in range(self.n):res[i] += self.mat[i][j] * vec[j]res[i] %= self.modreturn resdef add(self, other):assert other.n == self.nres = SquareMatrix(self.n, self.mod)for i in range(self.n):for j in range(self.n):res.mat[i][j] = self.mat[i][j] + other.mat[i][j]res.mat[i][j] %= self.modreturn resdef subtract(self, other):assert other.n == self.nres = SquareMatrix(self.n, self.mod)for i in range(self.n):for j in range(self.n):res.mat[i][j] = self.mat[i][j] - other.mat[i][j]res.mat[i][j] %= self.modreturn resdef times(self, k):res = SquareMatrix(self.n, self.mod)for i in range(self.n):for j in range(self.n):res.mat[i][j] = self.mat[i][j] * kres.mat[i][j] %= self.modreturn resdef multiply(self, other):assert self.n == other.nres = SquareMatrix(self.n, self.mod)for i in range(self.n):for j in range(self.n):for k in range(self.n):res.mat[i][j] += self.mat[i][k] * other.mat[k][j]res.mat[i][j] %= self.modreturn resdef power(self, k):tmp = SquareMatrix(self.n, self.mod)for i in range(self.n):for j in range(self.n):tmp.mat[i][j] = self.mat[i][j]res = SquareMatrix.id(self.n, self.mod)while k:if k & 1:res = res.multiply(tmp)tmp = tmp.multiply(tmp)k >>= 1return resdef trace(self):res = 0for i in range(self.n):res += self.mat[i][i]res %= self.modreturn resdef determinant(self):res = 1tmp = SquareMatrix(self.n, self.mod)for i in range(self.n):for j in range(self.n):tmp.mat[i][j] = self.mat[i][j]for j in range(self.n):if tmp.mat[j][j] == 0:for i in range(j + 1, self.n):if tmp.mat[i][j] != 0:idx = ibreakelse:return 0for k in range(self.n):tmp.mat[j][k], tmp.mat[idx][k] = tmp.mat[idx][k], tmp.mat[j][k]res *= -1inv = SquareMatrix.modinv(tmp.mat[j][j], self.mod)for i in range(j + 1, self.n):c = -inv * tmp.mat[i][j] % self.modfor k in range(self.n):tmp.mat[i][k] += c * tmp.mat[j][k]tmp.mat[i][k] %= self.modfor i in range(self.n):res *= tmp.mat[i][i]res %= self.modreturn resdef transpose(self):res = SquareMatrix(self.n, self.mod)for i in range(self.n):for j in range(self.n):res.mat[i][j] = self.mat[j][i]return resdef inverse(self): #self.determinant() != 0res = SquareMatrix.id(self.n, self.mod)tmp = SquareMatrix(self.n, self.mod)sgn = 1for i in range(self.n):for j in range(self.n):tmp.mat[i][j] = self.mat[i][j]for j in range(self.n):if tmp.mat[j][j] == 0:for i in range(j + 1, self.n):if tmp.mat[i][j] != 0:idx = ibreakelse:return 0for k in range(self.n):tmp.mat[j][k], tmp.mat[idx][k] = tmp.mat[idx][k], tmp.mat[j][k]res.mat[j][k], res.mat[idx][k] = res.mat[idx][k], res.mat[j][k]inv = SquareMatrix.modinv(tmp.mat[j][j], self.mod)for k in range(self.n):tmp.mat[j][k] *= invtmp.mat[j][k] %= self.modres.mat[j][k] *= invres.mat[j][k] %= self.modfor i in range(self.n):c = tmp.mat[i][j]for k in range(self.n):if i == j:continuetmp.mat[i][k] -= tmp.mat[j][k] * ctmp.mat[i][k] %= self.modres.mat[i][k] -= res.mat[j][k] * cres.mat[i][k] %= self.modreturn resdef linear_equations(self, vec): #self.determinant != 0return self.inverse().operate(vec)def print(self):print(*self.mat, sep='\n')A, B, N = map(int, input().split())if N == 0:print(0)elif N == 1:print(1)else:M = SquareMatrix(2)M.set([[A, B], [1, 0]])P = M.power(N - 1)print(P.operate([1, 0])[0])