My solution giving TLE on Spoj

#1

code:

Question:

#2

@spagire4
Will get back to you asap.

#3

@spagire4
The time complexity is k^3* log(n) for a single n. The entire time complexity is O(T* k^3* log(n)). This can be reduced to O(T) using pre-computation. Declare an array of size N = 5e5 + 5. Calculate the fib values for each i from i = 1 to i = N using the very basic formula fib[i] = fib[i - 1] + fib[i - 2]. Then simply for each test case, access the already computed values.

If my solution was able to answer your query, please mark the doubt as resolved.

#4

@LP18Aug0068 Actually I wanted to use matrix exponentation for problem
prb:https://www.codechef.com/LRNDSA06/problems/FIBNK
code: https://ide.codingblocks.com/s/323331
but here also my matrix expo gives TLE

#5

@spagire4
Will get back to you after trying the question.

#6

@spagire4
I apologize for the late reply. Your code is perfectly fine. The problem lies in the fact that we are sending by value, reinitialization of vectors time and again which were slowing the code down.

There is a formula S(n) = F(n + 2) - 1.
This equation helps in keeping that extra sum term while doing matrix exponentiation. Here we just need to find the (n + 2)th fib number. You can find the derivation on GFG.

Also, this code for matrix exponentiation helps in reducing the time taken by a significant amount. Please refer to this code:

void multiply(int F[2][2], int M[2][2]){
int x = ((F[0][0] * M[0][0]) % MOD + (F[0][1] * M[1][0]) % MOD) % MOD;
int y = ((F[0][0] * M[0][1]) % MOD + (F[0][1] * M[1][1]) % MOD) % MOD;
int z = ((F[1][0] * M[0][0]) % MOD + (F[1][1] * M[1][0]) % MOD) % MOD;
int w = ((F[1][0] * M[0][1]) % MOD + (F[1][1] * M[1][1]) % MOD) % MOD;

F[0][0] = x; 
F[0][1] = y; 
F[1][0] = z; 
F[1][1] = w;

}

void power(int F[2][2], int n){
if(n == 0 || n == 1)
return;
int M[2][2] = {{1, 1}, {1, 0}};

power(F, n / 2); 
multiply(F, F); 
  
if (n % 2 != 0) 
    multiply(F, M);

}

int fib(int n){
int F[2][2] = {{1, 1}, {1, 0}};
if (n == 0)
return 0;
power(F, n - 1);

return F[0][0] % MOD;

}

If you face any difficulty, please revert.
If my solution was able to answer your query, please mark the doubt as resolved.

#7

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.