系列的第n项 [英] nth term of series

问题描述

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

we have to find the nth term of this series http://oeis.org/A028859

N'LT; = 10亿

n<=1000000000

答案应该是模1000000007

answer should be modulo 1000000007

我已经写了code，但期限超过当娜是巨大的数字。

i have written the code but time limit exceeds when n a is huge number.

#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相对=nofollow>幂。

The standard technique for solving this type of problem is to rewrite it as a matrix multiplication and then use exponentiation by squaring to efficiently compute powers of the matrix.

在这种情况下：

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]，那么你可以通过

So if we define the matrix A=[2,2 ; 1,0], then you can compute the n th term by

[1,0] * A^(n-2) * [3;1]

所有这些操作都可以进行模数1000000007所以没有大的数字图书馆是必需的。

All of these operations can be done modulo 1000000007 so no big number library is required.

这需要O（日志（n））的2×2矩阵乘法计算A ^ N，所以总体来说，这一方法是O（日志（N）），而你原来的方法是为O（n）。

It requires O(log(n)) 2*2 matrix multiplications to compute A^N, so overall this method is O(log(n)), while your original method was O(n).

修改

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

Here is a good explanation and a C++ implementation of this method.

这篇关于系列的第n项的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！