我们必须找到这个系列的第 n 项 http://oeis.org/A028859
n<=1000000000
答案应该是模 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;
}
最佳答案
解决此类问题的标准技术是将其重写为矩阵乘法,然后使用 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)。
编辑
Here是一个很好的解释和此方法的 C++ 实现。
关于c++ - 系列的第n项,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/11285558/