I want to generate the nth term of the sequence 1,3,8,22,60 ,164 in Order(1) or order of (nlogn)

Question

This sequence satisfies a(n+2) = 2 a(n+1) + 2 a(n).

and also a(n)=[(1+sqrt(3))^(n+2)-(1-sqrt(3))^(n+2)]/(4sqrt(3)).

I am using C++ for me n can vary from 1 to 10^ 9. I need the answers modulo (10^9)+7 But speed here is very important

My code with formula1 is slow for numbers > 10^7

#include <iostream>
#define big unsigned long long int
#include<stdlib.h>
int ans[100000001]={0};

big m  =1000000007;
using namespace std;
int main()
{
    //cout << "Hello world!" << endl;
    big t,n;
    cin>>t;
    big a,b,c;
    a=1;
    b=3;
    c=8;
    ans[0]=0;
    ans[1]=1;
    ans[2]=3;
    ans[3]=8;
    for(big i=3;i<=100000000;i++)
        {
            ans[i]=(((((ans[i-2])+(ans[i-1])))%m)<<1)%m;

        }

//    while(t--)
//    {
//        int f=0;
//        cin>>n;
//        if(n==1){
//        cout<<1<<endl;f++;}
//        if(n==2){
//        cout<<3<<endl;
//        f++;
//        }
//        if(!f){
//        a=1;
//        b=3;
//        c=8;
//        for(big i=3;i<=n;i++)
//        {
//            c=(((((a)+(b
//                         )))%m)<<1)%m;
//            a=b%m ;
//            b=c%m;
//        }
//        cout<<ans[n]<<endl;
//        }
//    }
while(t--)
{
    cin>>n;
    if(n<=100000000)
    cout<<ans[n]<<endl;
    else
    cout<<rand()%m;
}
    return 0;
}

I want a faster method. How can I compute the nth term using the second formula.Is there any trick to calculate modular powers of decimals very quickly? Do you have any suggestions for faster generation of this sequence?

Please help

Answer 1

You can calculate values of sequences with a linear recurrence relation in O(log n) steps using the matrix method. In this case, the recurrence matrix is

2 2
1 0

The n-th term of the sequence is then obtained by multiplying the n-th power of that matrix with the two initial values.

The recurrence immediately translates to

|x_n    |   |2 2|   |x_(n-1)|
|x_(n-1)| = |1 0| * |x_(n-2)|

thus

|x_(n+1)|   |2 2|^n   |x_1|
|x_n    | = |1 0|   * |x_0|.

In this case the initial conditions give, x_1 = 1, x_2 = 3 lead to x_0 = 0.5, a non-integer value, hence the calculation should rather be

|x_(n+1)|   |2 2|^(n-1)   |x_2|
|x_n    | = |1 0|       * |x_1|.

To get the value modulo some number, calculate the power of the matrix modulo that number.

Answer 2

I don't want to spoil of the fun of exploring the solution of algorithmic puzzles, so I'll just give you a starting hint: What you have there is basically a Fibonacci sequence with a few confusing elements.