hello codeforces , I am a beginner coder , you can imagine very beginner , I am trying to code matrix exponential for nth fibonacci number , but , I find a bug.
the fibonacci series is : 0,1,1,2,3,5,8,13,21.... my code generates : 0,1,1,2,5,21,144,1597,28657.....
please help me finding the bug , I oblige :( :( my code : https://paste.ubuntu.com/26187218/
main_mat[0][0] = 1; main_mat[0][1] = 1; main_mat[1][0] = 1; main_mat[1][1] = 0;
Firstly, add this lines at the top of your while loop that is inside your int main function. Then you'll get the correct answer. If you do not include this line, then every time you input the value of n the values of element in main_mat 2D array is not initialized to its default value. You can check by yourself.
Secondly, your program is too slow. I'm not sure whether you used the fast exponentiation technique. You can find the nth fibonacci number in O(2^3*logn) = O(8*logn) time. But you are doing it in O(n*2^3) = O(8*n) time which is too slow. You need to learn fast exponentiation technique. :)
****
Thank a lot vaiya :) ami bug paisilm na
I know that i should use bigmod instead of the loop , then , the power will be calculated in O(log n) , but i am a beginner , so I started from easy approach