nth term of series
algorithm, c++, series
Solution
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.
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 compute the n th term by
[1,0] * A^(n-2) * [3;1]
All of these operations can be done modulo 1000000007 so no big number library is required.
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).
EDIT
Here is a good explanation and a C++ implementation of this method.
Problem
we have to find the nth term of this series http://oeis.org/A028859 n<=1000000000 answer should be modulo 1000000007 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; } ```