鏈接：https://ac.nowcoder.com/acm/problem/15666
來源：牛客網

時間限制：C/C++ 1秒，其他語言2秒
空間限制：C/C++ 32768K，其他語言65536K
64bit IO Format: %lld

題目描述

輸入描述:

第一行是一個整數T(1 ≤ T ≤ 1000)，表示樣例的個數。
以后每個樣例一行，是一個整數n(1 ≤ n ≤ 1018)。

輸出描述:

每個樣例輸出一行，一個整數，表示F(n) mod 1000000007。

列出等式，

可以求出矩陣A為：
[
[1,1,1,1,1,1],
[1,0,0,0,0,0],
[0,0,1,3,3,1],
[0,0,0,1,2,1],
[0,0,0,0,1,1],
[0,0,0,0,0,1],
]

GLOBAL_MOD = 1000000007 T = int(input()) class Solution:def f(self, n: int) -> int:if n == 0 or n == 1:return nres = self.matrixpower(n-1)res = res[0][0]*1+res[0][1]*0+res[0][2]*8+res[0][3]*4+res[0][4]*2+res[0][5]res = res % GLOBAL_MODreturn resdef matrixpower(self, power):# res初始值為單位矩陣res = [[1, 0, 0, 0, 0, 0],[0, 1, 0, 0, 0, 0],[0, 0, 1, 0, 0, 0],[0, 0, 0, 1, 0, 0],[0, 0, 0, 0, 1, 0],[0, 0, 0, 0, 0, 1]] base = [[1, 1, 1, 1, 1, 1],[1, 0, 0, 0, 0, 0],[0, 0, 1, 3, 3, 1],[0, 0, 0, 1, 2, 1],[0, 0, 0, 0, 1, 1],[0, 0, 0, 0, 0, 1]] # 這個是我們根據斐波那契數列的特點構造的矩陣 while power !=0:if power&1 !=0:res = self.multimatrix(res, base)power = power>>1base = self.multimatrix(base, base)return resdef multimatrix(self, m1, m2):n = len(m1)res = [[0]*n for i in range(n)]for i in range(n):for j in range(n):for k in range(n):res[i][j] = (res[i][j]+m1[i][k] * m2[k][j])%GLOBAL_MODreturn resfor i in range(T):n = int(input())ans = Solution()print(ans.f(n))

總結

以上是生活随笔為你收集整理的牛客15666 又见斐波那契（矩阵快速幂）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。