Here is my code for the problem link It exceeds the time limit, how do I improve the code?
There are 44 fibonacci numbers less than 10^9 + 7. So, we can store those numbers in an array, and then compute the n’th non fibonacci number easily (in O(1)).
For computing Fib(n) % MOD, use matrix exponentiation. Read about it here
It is a Russian website, so translate it to English, if needed.
This operation takes O(log n) time. After computing this value, we need to compute a^b % MOD. We know that b < MOD, and this power mod can be calculated in O(log b) time using binary exponentiation. Read about it here
Each test case takes O(log n) time effectively.
Make sure you handle the integer overflows. Use 64 bit integers, and take modulus after multiplications.
Can you explain your first statement? How do I achieve O(1) ?
First generate all the fibonacci numbers less than 10^9 + 7 and store them in an array. There are 43 such numbers. ( ar[] = {1,2,3,5,8,13,…,701408733}; )
Now, for finding the n’th non fibonacci number, you can iterate on this array and sum the differences between consecutive elements till it is less than n. It will take atmost 43 iterations.