Matrix Exponentiation

In Matrix Exponentiation , how to solve this equation,

F(n) = aF(n-1) + bF(n-2) + c*F(n-3) + G(n)

G(n) = nn(n+1)

where max value of n can be 10^18

How to make the M matrix for such equations where the ‘n’ variable is present in the equations ?

2 Likes

Study it from here:- https://www.geeksforgeeks.org/matrix-exponentiation/ :slight_smile:

1 Like

hey thanks for your reply,
but i am confused that how to handle G(n)…

I had the same confusion 6 months ago ; all boils down to basic maths and manipulating your way to create a matrix which satisfies G(n) as well. To learn how to do that, read this:-
https://www.quora.com/How-do-I-simplify-a-recursion-equation-The-equation-is-f-n-2-n-3-f-n-3-f-n-1-We-are-given-the-values-f-0-f-1-f-2-Is-it-possible-to-get-an-expression-in-terms-of-n-for-f-n/answer/David-Smith-2412

After some basic maths for g(n),I have written a code. You can check here :- https://pastebin.com/v0z6uGru

1 Like

can somebody explain how to solve www.codechef.com/problems/CKISSHUG via matrix exponentiation?

Hey!
I have gone through code. But, quite couldn’t understand why you took 12,10,8,6 and also why size to be 7?
Could you please explain or give any reference so that i can go through it and understand?

g(n) = nn(n+1),try to write g(n) = g(n-1) + something, that something will again in terms of n,let say d(n) again try doing this , u will get new equations , so total terms will 3 + 4(after expanding nn(n+1)= hence 7 terms.6,8,10,12 are base values of that equation.

1 Like

@maxwell_008 Thanks a lot. I understood it now :slight_smile:
g(n) = n2 * (n+1) becomes g(n-1)+(3n2- n)
considering d(n) = 3n2- n, it can be written as d(n-1)+(6n-4)
considering m(n) as 6n-4, it can be written as m(n) = m(n-1)+6
substituting all, we get g(n) = g(n-1) + d(n-1) + m(n-1) + 6
=> g(n) = (n3-2n2+n)+(3n2-7n+4)+(6n-10)+6

anyone?? :slightly_frowning_face:

That problem does not require matrix exponentiation at all, it has an O(1) solution, a simple formula which you have to derive, you can check the editorial in case deriving the formula gets hard :slight_smile:

1 Like

@maxwell_008 @venkatpinnaman thanks for your reply,

but how you get the base values as 6,8,10,12,

Nice blog on Matrix Exponentiation by Zobayer Hasan :-

yeah i got the formula and struggled to get an AC but, the editorial said we can solve it using Matrix Exponentiation as well. So, that’s why i wanted to ask how to do it that way

@aarls
g(n) = g(n-1)+d(n-1)+m(n-1)+6
let n = 3
g(3) = g(2)+d(2)+m(2)+6
g(3) = (22 * (2+1))+((3 * 22)-2)+((6 * 2)-4)+6
g(3) = (4*3)+(12-2)+(12-4)+6
g(3) = 12+10+8+6

This is how you get base values as 12,10,8,6

this makes initial matrix as
f(2)
f(1)
f(0)
12
10
8
6

thanks bhai :slight_smile:

So the answer in this case would be :

Product of matrix
{ a, b, c, 1, 1, 1 ,1
1, 0, 0, 0, 0, 0 ,0
0, 1, 0, 0, 0, 0 ,0
0, 0, 0, 12, 0, 0 ,0
0, 0, 0, 0, 10, 0 ,0
0, 0, 0, 0, 0, 8 ,0
0, 0, 0, 0, 0, 0 ,6 } (n-2) times multiplied by initial matrix which is

f(2)
f(1)
f(0)
12
10
8
6

@gpatel3
the Transformation matrix here would be
{ a,b,c,1,1,1,1
1,0,0,0,0,0,0
0,1,0,0,0,0,0
0,0,0,1,1,1,1
0,0,0,0,1,1,1
0,0,0,0,0,1,1
0,0,0,0,0,0,1 }

where as the initial matrix is
f(2)
f(1)
f(0)
12
10
8
6

So, the resultant becomes

f(3)
f(2)
f(1)
36
24
14
6

Because, we have expressed n2 * (n+1) as g(n), it becomes part of equation.
f(n) = a * f(n-1)+b * f(n-2)+c * f(n-3) + g(n)

Why this can’t be the transformation matrix :
{ a,b,c,1,1,1,1
1,0,0,0,0,0,0
0,1,0,0,0,0,0
0,0,0,1,0,0,0
0,0,0,0,1,0,0
0,0,0,0,0,1,0
0,0,0,0,0,0,1 }

@gpatel3 it would have been possible if the last 4 terms of initial matrix are constants. But, they are variables (dependent on value of n). That’s the reason the transformation matrix which you have mentioned can’t be used.