递归关系的一般公式？

Question

我在解一道编码题，找出如下关系求可能排列的个数：

one[1] = two[1] = three[1] = 1

one[i] = two[i-1] + three[i-1]

two[i] = one[i-1] + three[i-1]

three[i] = one[i-1] + two[i-1] + three[i-1]

我本可以很容易地使用 for 循环 来找出各个数组的值，直到 n，但是 n 的值是订单 10^9，我将无法从 1 迭代到这么大的数字。

对于n的每个值，我需要在O(1)时间内输出(one[n] + two[n] + three[n]) % 10^9+7的值。

一些结果：

对于 n = 1，结果 = 3
对于 n = 2，结果 = 7
对于 n = 3，结果 = 17
对于 n = 4，结果 = 41

我花了几个小时才找到上述 n 的通用公式。谁能帮帮我。

编辑：

n = 1, result(1) = 3
n = 2, result(2) = 7
n = 3, result(3) = result(2)*2 + result(1) = 17
n = 4, result(4) = result(3)*2 + result(2) = 41

所以，result(n) = result(n-1)*2 + result(n-2) 或者 T(n) = 2T(n-1) + T(n-2)

Answer 1

可以用矩阵来表示递归关系。（我已将 one、two、three 重命名为 a、b、c）。

(a[n+1]) = ( 0 1 1 ) (a[n])
(b[n+1])   ( 1 0 1 ) (b[n])
(c[n+1])   ( 1 1 1 ) (c[n])

使用这种表示法，可以通过矩阵求幂（对您的大数求模），使用平方求幂来计算大 n 的值。这将在 O(log n) 时间内给你结果。

(a[n]) = ( 0 1 1 )^(n-1) (1)
(b[n])   ( 1 0 1 )       (1)
(c[n])   ( 1 1 1 )       (1)

这里有一些 Python 从头开始实现的：

# compute a*b mod K where a and b are square matrices of the same size
def mmul(a, b, K):
    n = len(a)
    return [
        [sum(a[i][k] * b[k][j] for k in xrange(n)) % K for j in xrange(n)]
        for i in xrange(n)]

# compute a^n mod K where a is a square matrix
def mpow(a, n, K):
    if n == 0: return [[i == j for i in xrange(len(a))] for j in xrange(len(a))]
    if n % 2: return mmul(mpow(a, n-1, K), a, K)
    a2 = mpow(a, n//2, K)
    return mmul(a2, a2, K)

M = [[0, 1, 1], [1, 0, 1], [1, 1, 1]]

def f(n):
    K = 10**9+7
    return sum(sum(a) for a in mpow(M, n-1, K)) % K

print f(1), f(2), f(3), f(4)
print f(10 ** 9)

输出：

3 7 17 41
999999966

即使在 n=10**9 的情况下，它也能立即有效地运行。

递归关系的一般公式？

General formula for a recurrence relation?

algorithm

formula

recurrence