计算序列1,3,8,22,60,164,448,1224的第n项...? [英] Calculate the nth term of the sequence 1,3,8,22,60,164,448,1224...?
问题描述
可能重复:
<一href="http://stackoverflow.com/questions/11301992/i-want-to-generate-the-nth-term-of-the-sequence-1-3-8-22-60-164-in-order1-or">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.
这篇关于计算序列1,3,8,22,60,164,448,1224的第n项...?的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!