网易8.20笔试算法卷t4 类斐波那契数列
题目为给定数列前两个数a和b，数列有递推公式f[i]=(f[i-1]*f[i-2])^2，求数列第n个数
思路：矩阵快速幂求a和b在第n个数时候的幂，然后用快速幂求当前值
最后只能过60，呜呜呜希望各位大佬帮忙看看哪里实现有问题，看了一晚上了
a, b, n = list(map(int, input().split())) mod = 10**9+7 c1, c2 = 4, 6 if n == 1: print(a%mod) elif n == 2: print(b%mod) elif n == 3: print(pow(a, 2, mod)*pow(b, 2, mod)%mod) else: def mymulti(a, b): res = [[0, 0], [0, 0]] for i in range(2): for j in range(2): res[i][j] = (a[i][0]*b[0][j]+a[i][1]*b[1][j]) % mod return res def matrix_pow(n): res = [[2, 2], [1, 0]] bak = [[1, 0], [0, 1]] while n > 0: if n & 1: bak = mymulti(bak, res) n >>= 1 res = mymulti(res, res) return bak res = matrix_pow(n-4) c1 = 4*res[0][0]+2*res[0][1] c2 = 6*res[0][0]+2*res[0][1] print(pow(a, c1, mod)*pow(b, c2, mod)%mod)
