Jump to navigation Jump to search
10229 - Modular Fibonacci
Get the F(n) Fibonacci's Number then get its modulo on .
Solving this problem requires you to calculate Fibonacci in lg(n) time. It's by dividing n into n/2 size problem at each instance.
- Use a 64 bit integer representation for the Fibonacci's number as a 32 bit will overflow.
- Use the Q-Fibonacci Matrix to get the output in O(log n) and avoid TLE.
11 7 11 6