Nth member of the series

Question

we need to find the nth member of this series http://oeis.org/A028859

n <= 1,000,000,000

the answer should be modulo 1000000007

I wrote the code, but the time limit exceeds when na is a 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; } 

Answer 1

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

In this case:

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

So, if we define the matrix A = [2,2; 1,0], then you can calculate the nth term on

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

All these operations can be performed modulo 1000000007, so a library of large numbers is not required.

Computing A ^ N requires O (log (n)) 2 * 2 matrix multiplications, so this whole method is O (log (n)), and your original method is O (n).

EDIT

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

Answer 2

If long long not enough, you probably want to use the bignum library. For example GNU MP .