Matrix Exponentiation

Where there is recurrence , there is Matrix Expo.

We use matrix expo to calculate very large number, terms of the recurrence where even DP can’t help us to pre-calculate the result.

You are all requested to read this blog  Matrix Expo  for understanding the matrix exponentiation.

Here is a sample code for generating Fibonacci numbers.

Note: For different types of recurrence , the base matrix will change accordingly. We have to generate this base matrix carefully , else every other things are pretty much same.