非线性递归关系

如何找到此递归关系的第N个术语

F(n) = F(n-1) + F(n-2) + F(n-1)*F(n-2)

我必须找到这个递归关系模的第N个项10^9+7.

我知道如何找到线性递归关系的第N个术语,但无法继续进行此操作.

1<=N<=10^9

提供F(0)和F(1)作为输入.

有一个技巧.我们G(n) = F(n) + 1.等式

F(n) = F(n-1) + F(n-2) + F(n-1)*F(n-2)

变

G(n) - 1 = G(n-1) - 1 + G(n-2) - 1 + (G(n-1) - 1) * (G(n-2) - 1)
         = G(n-1) - 1 + G(n-2) - 1 + G(n-1)*G(n-2) - G(n-1) - G(n-2) + 1
         = G(n-1)*G(n-2) - 1,

所以1增加到双方,

G(n) = G(n-1)*G(n-2).

这是熟悉的斐波那契复发的乘法等价物.解决方案是

G(n) = G(0)^Fib(n-1) * G(1)^Fib(n),

通过类比线性递归理论(其中Fib(-1) = 1和Fib(0) = 0和Fib(1) = 1),因为

G(n-1)*G(n-2) = G(0)^Fib(n-2) * G(1)^Fib(n-1)
              * G(0)^Fib(n-3) * G(1)^Fib(n-2)
              = G(0)^Fib(n-1) * G(1)^Fib(n)
              = G(n).

因此,

F(n) = (F(0)+1)^Fib(n-1) * (F(1)+1)^Fib(n) - 1,

Fib通过p-1每个费马小定理和指数模的矩阵幂方法mod 进行计算p.