結果
問題 | No.891 隣接3項間の漸化式 |
ユーザー |
|
提出日時 | 2023-02-17 21:32:43 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 42 ms / 2,000 ms |
コード長 | 2,192 bytes |
コンパイル時間 | 341 ms |
コンパイル使用メモリ | 81,920 KB |
実行使用メモリ | 52,608 KB |
最終ジャッジ日時 | 2024-07-19 12:36:50 |
合計ジャッジ時間 | 2,951 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 39 |
ソースコード
def oi(): return int(input())def os(): return input()def mi(): return list(map(int, input().split()))# import sys# input = sys.stdin.readline# import sys# sys.setrecursionlimit(10**8)# import pypyjit# pypyjit.set_param('max_unroll_recursion=-1')input_count = 0input_count = 0a,b,n = mi()mod = 10**9+7def prod_func(a,b):# 累乗部分がデカすぎてメモリが死んじゃう時など# 例えば10^18回移動して到達できる場所はどこ?というときはこれで良いreturn (a*b)%moddef add_func(a,b):return a+bclass MATRIX:def __init__(self, prod_func, add_func):self.prod_func = prod_funcself.add_func = add_funcdef dot(self, A,B):if len(A[0]) != len(B):return Noneout = [[0] * len(B[0]) for _ in range(len(A))]for ay in range(len(A)):for bx in range(len(B[0])):sums = 0for ax in range(len(A[0])):sums += self.prod_func(A[ay][ax], B[ax][bx])out[ay][bx] = sumsreturn outdef sum(self, A,B):if not(len(A) == len(B) and len(A[0]) == len(B[0])):return Noneout = []for ay in range(len(A)):temp = []for ax in range(len(A[0])):temp.append(self.add_func(A[ay][ax], B[ay][ax]))out.append(temp)return outdef prod(self, A,B):if not(len(A) == len(B) and len(A[0]) == len(B[0])):return Noneout = []for ay in range(len(A)):temp = []for ax in range(len(A[0])):temp.append(self.prod_func(A[ay][ax], B[ay][ax]))out.append(temp)return out# 正方行列AをN乗する。def ruijou(self, A, N):out = [[0] * len(A) for _ in range(len(A))]for i in range(len(A)):out[i][i] = 1while N:if N%2==1:out = self.dot(out, A)A = self.dot(A,A)N//=2return outMAT = MATRIX(prod_func=prod_func, add_func=add_func)print(MAT.ruijou([[a, b],[1,0]], n)[1][0]%mod)