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

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)

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

Recurrence relation solution for relations with two interdependent variables

recurrence