algorithm - Simple recurrence in C++ -

simple recurrencemax. score 0

our hero - alex has been working on research week. , has gotten recurrence relation solving part of research. has no time. it?

recurrence relation 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 given initial value of f(1), f(0), g(1), g(0).

you have output f(n) mod 10^9.

input:

in first line given 4 numbers : f(1), f(0), g(1), g(0) respectively. in next line given 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 indeed easy question. used iteration 6 variables f0, f1, f2, g0, g1, g2 solve it. in loop, first compute g2, f2, f0=f1, f1=f2, g0=g1, g1=g2. data types unsigned long long in c++.

however, time limit 1 second , 1.06 second. therefore passed 1 test case in test, others "time limit exceeded". there faster way 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; } 

given recurrence can written

with base conditions given f(1), f(o), g(1) , g(0). now, calculate f(n), have raise coefficient matrix power n - 1. fortunately, can done using log(n) matrix multiplications. famous problem of exponentiation.

since matrix size small, has o(log(n)) complexity.