第n个系列

Question

我们必须找到这个系列的第n个术语http://oeis.org/A028859

N <= 10亿

答案应该是模数1000000007

我写了代码,但是当na是巨大的数字时,时间限制超过了.

#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;
}

Answer 1

解决此类问题的标准技术是将其重写为矩阵乘法,然后通过平方使用取幂来有效地计算矩阵的幂.

在这种情况下:

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).

编辑

这是一个很好的解释和这个方法的C++实现.