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.

HackerEarth: Fibonacci with GCD

Problem: Fibonacci with GCD

Editorial: It's a segment tree problem with simple matrix exponentiation for generating fibonacci numbers. In this problem, we will be given some numbers. Then we will be asked to perform some queries.  Each query there will be a range, from that range we need to find GCD of all the elements fibonacci numbers. Say for 2 4 8, we need to calculate GCD ( fib[2], fib[4], fib[8] ) = GCD ( 1, 3, 21 ) = 1.
We will create a segment tree, where we will store the gcd of every elements of the array. Basically our segment tree will be made of calculating gcd for a given range. Then for the query we will calculate part by part in the range for our gcd. If left and right both child node is -1, then we will simply return 1. If left child is -1 but right child has positive value, then we will return right child. Similarly we will do for the right child being -1 also. And when both the child have positive value, we will return the gcd between them. After getting the gcd value from the elements of the range from our query, then we will find the fibonacci number of that gcd value. We will do that with matrix exponentiation.

So, basically, for this problem, we will create segment tree first with corresponding gcd, and then after the query, we will calculate the fibonacci number. Say for values : 2, 4, 8, the GCD = 1. So our answer will be fibonacci [ 1 ] and that is 1. ( Fibonacci series : 1, 2, 3, 5,....).

LightOJ: Algebraic Problem

Problem Link: loj1070
Technique: Matrix Exponentiation

Given the value of a+b and ab you will have to find the value of aⁿ+bⁿ. a and b not necessarily have to be real numbers. I solved this using matrix exponentiation technique. I will now write about how I modelled the base matrix for multiplication. There may be other approaches too. But first please read this mat expo if you don't know about how to create a matrix from a recurrance relation.
First let's observe some cases.

If n = 0, a⁰+b⁰ = 1+1 = 2
If n = 1, a¹+b¹ = a+b - 0
If n = 2, a²+b² = (a+b) (a+b) - 2ab
If n = 3, a³+b³ = (a+b) ( (a+b)² - ab ) - 2ab (a+b)
..............     ..............     .............     .................
So, basically the recurrence somehow turns like this -->
(a¹+b¹) = (a+b) + (-0)
(a²+b²) = (a+b) (a+b) + 2(-ab)
So,

base  =  | (a+b)   -ab  |
             |   1           0   |
We will multiply (a+b) with base [0][0] and 2 with base [0][1], then we will get our final output by summing these two elements.
So, when n = 0 , ans will be 2.
When n = 1, ans will be a+b
When n = 2, ans will be (base)¹  = (a+b) * (a+b) + 2 * (-ab) = (a+b)² - 2ab
When n = 3, ans will be (base)²  = (a+b) * [(a+b)² -ab)] + 2 * [-ab*(a+b)]
Let's see this : (for n = 3)

In our base matrix, after performing exponentiation, at base [0][0] we get [(a+b)² -ab)], and we will multiply it with (a+b). Similarly, at base[0][1] we get [-ab*(a+b)], so we will multuply it with 2. And by summing these two elements, we will get our final output.

NOTE : As For each test case, print the case number and (aⁿ+bⁿ) modulo 2⁶⁴, we will use unsigned long long for each variable instead of applying modulus operation. This will save our time. Infact, without this, the program will get TLE.



"Don't directly copy code. First try to understand how each step works, then do your own coding."