Simple recurrence in C++

Question

Simple RecurrenceMax. Score 0

Our hero - Alex has been working on a research for a week. And he has recently gotten a recurrence relation for solving a part of that research. But he has no time. Could you do it?

Recurrence relation is as follows : f(n) = 3 * f(n-1) + 2 * f(n-2) + 2 * g(n-1)+3 * g(n-2) , g(n) = g(n-1) + 2 * g(n-2).

You are given the initial value of f(1), f(0), g(1), g(0).

You have to output f(N) mod 10^9.

Input:

In the first line you are given 4 numbers : f(1), f(0), g(1), g(0) respectively. In the next line you are given an integer N.

Output:

Output f(N) mod 10^9.

Constraints:

1 <= f(0),f(1),g(0),g(1) <= 10 1 <= N <= 10^18

Sample Input (Plaintext Link)

1 1 1 1 4 Sample Output (Plaintext Link) 162

This is indeed a very easy question. I simply used iteration with 6 variables f0, f1, f2, g0, g1, g2 to solve it. In the loop, I first compute g2, f2, then f0=f1, f1=f2, g0=g1, g1=g2. The data types are unsigned long long in c++.

However, the time limit is 1 second and I get 1.06 second. Therefore I passed only one test case in the test, others "time limit exceeded". Is there any faster way to solve it?

my code is:

#include<iostream>
using namespace sdt;

int main()
{
    unsigned long long f0, f1, g0, g1, f2, g2;
    unsigned long long N;
    cin>>f1>>f0>>g1>>g0;
    cin>>N;
    for(unsigned long long i=2; i<N+1; i++)
    {
        f2=3*f1+2*f0+2*g1*3*g0;
        g2=g1+2*g0;
        f0=f1;
        f1=f2;
        g0=g1;
        g1=g2;
    }
    unsigned long long result=f2%1000000000;
    cout<<result;
    return 0;
}

Answer 1

1-The code is different from the recurrence relation. The code should be:

f2=3*f1+2*f0+2*g1+3*g0;

2-One possible way to optimize the code is to decrease the number of heavy calculations, which is the multiplication in this case, by doing this:

f2=3*(f1+g0)+2*(f0+g1);

However, I think the compiler's optimizer will do this automatically for you, but you can try yourself to be sure.

Answer 2

Given recurrence can be written as

with the base conditions given by f(1), f(o), g(1) and g(0). Now, to calculate f(n), we have to raise the coefficient matrix to the power n - 1. Fortunately, this can be done using log(n) matrix multiplications. This is a famous problem of exponentiation.

Since matrix size is small, this has O(log(n)) complexity.