具有两个相互依赖变量的关系的递归关系解

Question

我在一次在线挑战中遇到了以下问题。

考虑以下向量：

x = [3, 4, ...]
y = [2, 3, ...]

这样对于 i>= 2：

x[i] = x[i-1] + 3 * y[i-2]
y[i] = 2 * y[i-1] + 2 * x[i-2]

什么是 x[10^15] ？

虽然问题有一个非常简单的解决方案，但问题是 10^15 的值无法在短时间内计算出来。我唯一能想到的是，我们必须从递归关系中推导出一个多项式 - 然而，这并不容易做到。 我错过了什么吗？

Answer 1

问题语句可以表示为矩阵乘法，如下所示：

A= [
[1, 0, 0, 3],
[1, 0, 0, 0],
[0, 2, 2, 0],
[0, 0, 1, 0]
]
[xn+1, xn, yn+1, yn] = A*[xn, xn-1, yn, yn-1]
=>  [xn+1, xn, yn+1, yn] = A^(n-1) * [x1, x0, y1, y0]
[x1, x0, y1, y0] = [4, 3, 3, 2]

虽然问题中没有提到，但由于矩阵乘法超过整数限制，因此解决方案需要表示为某个素数的余数。让质数1000000007。但是我们怎么能在乘法时不超过整数限制呢？请考虑以下事项：

(X * Y) mod p = ((X mod p) * (Y mod p)) mod p
Now, X = A^n
Let, A^n mod p = B
Now, B = B mod p
So,
(X * Y) mod p = 
((X mod p) * (Y mod p)) mod p
=>  ((A^n mod p) * (Y mod p)) mod p
=>  ( B * (Y mod p)) mod p
=>  ((B mod p) * (Y mod p)) mod p
=> (B * Y) mod p

所以一个简单的python实现将是：

import numpy as np
p = 1000000007
A= np.array([
[1, 0, 0, 3],
[1, 0, 0, 0],
[0, 2, 2, 0],
[0, 0, 1, 0]
])
Y = np.array([4, 3, 3, 2])
# We will use binary exponentiation for fast matrix multiplication
# See: https://cp-algorithms.com/algebra/binary-exp.html
# The `power` list is the array of A's powers needed for that
powers = []
powers.append(A % p)
for i in range(1, 50): # Till 50 since 10^15 ~= 2^50
Ap = powers[i - 1]
powers.append(Ap.dot(Ap) % p)
def solve(n):
pow_of_a = n - 3
index = 0
prod = np.identity(4)
while (pow_of_a > 0):
if (pow_of_a & 1) == 1:
prod = prod.dot(powers[index])
pow_of_a >>= 1  
index += 1
B = prod % p
print(B.dot(Y) % p)