可能重复：   I要生成序列1,3,8,22,60，164的订单（1）第n项或命令（nlogn）

我现在要做的是：

t1 = 1, t2 = 0,MOD = 1000000007;

for i = 1:n 

    t1_new = (2*(t1+t2)) % MOD;
    t2_new = t1;
    a[i] = (t1_new + t2_new) % MOD;   // where a[i] is the ith term mod p
    t1 = t1_new;
    t2 = t2_new;

return a[n]; // the required ans

但它是一个O（n）的解决方案。

But it is an O(n) solution.

请给我唯一的线索（无解请），这样我就可以降低解决方案的复杂性。

Please give me only hints(no solution please) so that I can reduce the complexity of the solution.

推荐答案

您可以使用如下因素的事实。如果考虑矩阵

You can use the folowing fact. If you consider the matrix

    (0 1)
A = (2 2)

您可以使用一个事实，即 N = A N-2 *（1，3）[1]（这里是（1,3）是一个向量）和[1]装置第二坐标的载体的构建。在这里，您可以使用二进制幂的矩阵。考虑案件对于n＆LT; = 2分别

You can use the fact that an = An-2 * (1, 3)[1] (here (1,3) is a vector) and [1] means second coordinate of the vector. Here you can use binary exponentiation for the matrix. Consider the cases for n<=2 separately.