中山精品网站建设资讯,做网站的教科书,佘山做网站公司,域名查询注册官网链接#xff1a;https://ac.nowcoder.com/acm/problem/15666 来源#xff1a;牛客网
时间限制#xff1a;C/C 1秒#xff0c;其他语言2秒 空间限制#xff1a;C/C 32768K#xff0c;其他语言65536K 64bit IO Format: %lld
题目描述
输入描述:
第一行是一个整数T(1 ≤…链接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]*1res[0][1]*0res[0][2]*8res[0][3]*4res[0][4]*2res[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 power1 !0:res self.multimatrix(res, base)power power1base 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))
