我们必须找到这个级数的第n项http://oeis.org/A028859 http://oeis.org/A028859
n
答案应该以 1000000007 为模
我已经编写了代码,但是当 n a 是一个巨大的数字时,时间限制就超出了。
#include<iostream>
using namespace std
int main()
{
long long int n;
cin>>n;
long long int a,b,c;
a=1;
b=3;
int i;
for(i=3;i<=n;i++)
{
c=(2ll*(a+b))%1000000007;
a=b;
b=c;
}
cout<<c;
}
解决此类问题的标准技术是将其重写为矩阵乘法,然后使用通过平方求幂 http://en.wikipedia.org/wiki/Exponentiation_by_squaring有效地计算矩阵的幂。
在这种情况下:
a(n+2) = 2 a(n+1) + 2 a(n)
a(n+1) = a(n+1)
(a(n+2)) = (2 2) * ( a(n+1) )
(a(n+1)) (1 0) ( a(n) )
因此,如果我们定义矩阵 A=[2,2 ; 1,0],那么你可以计算第 n 项
[1,0] * A^(n-2) * [3;1]
所有这些操作都可以对 1000000007 进行模运算,因此不需要大数库。
它需要 O(log(n)) 2*2 矩阵乘法来计算 A^N,因此总的来说,此方法是 O(log(n)),而您的原始方法是 O(n)。
EDIT
Here http://wilanw.blogspot.co.uk/2009/12/matrix-exponentiation.html是这个方法的一个很好的解释和 C++ 实现。
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)