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 
1 Like
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
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.
Thank you 
I know how to solve it I think.
Will surely help you after contest gets over.
I am not blaming you for anything.
I flagged just because people will read other messages before answering that query as it’s from an ongoing contest.
Yup, I’ve solved it. I’ll surely explain you
can you explain, how to solve such cases :-
F(n) = a*F(n-1) + d ; if n is even
F(n) = b*F(n-1) + c ; if n is odd
@aarls It’s a simple equation
F(1) = aF(0)+d
F(2) = aF(1)+d
= a*(a*F(0)+d)+d
= a2F(0)+ad+d
F(3) = a(a2F(0)+ad+d)+d
= a3F(0)+a2+ad+d
=> F(n) = anF(0) + d (1+a+a2+…+an-1)
=> F(n) = anF(0) + d(sum of n-1 terms of gp)
It’s a formula which applies both for odd and even.
F(1) should be :-
F(1) = b*F(0) + c
but you have taken
F(1) = a*F(0) + d
?
My bad, i didn’t read it properly.
In such cases, we need to maintain two matrices and change the transformation matrix between them, in case of even and odd.
can you explain bit more please, or any good source for this??
For sake of simplicity, let us denote F(n) for even n as f(n) and for odd n as g(n).
Then the equations are
f(n)=a*g(n-1)+d …[Eq. 1]
g(n)=b*f(n-1)+c …[Eq.2]
Plugging value of f(n) from Eq.2 in Eq.1, we get
g(n)=ab*g(n-2)+bd+c
This equation can be readily solved by the following method:
Method:
Let the functional equation be h(n)=\lambda*h(n-2)+\mu
There exist two real numbers x and y such that x-y=\mu.
Then the above equation can be re-written as
h(n)-x=\lambda*h(n-2)-y
Now I will choose x and y such that
x=y/\lambda…(It will always be possible to choose them and it will be clear why I’m choosing this condition)
Then the functional equation can be re-written as
h(n)-x=\lambda*(h(n-2)-y/\lambda)
Due to the imposed condition on x and y, this reduces to
h(n)-x=\lambda*(h(n-2)-x)
Now if
Q(n)=h(n)-x, then
Q(n)=\lambda*Q(n-2)
This is basic Geometric Progression with nth term being found depending on the initial value.
Now by the above technique, we can find f(n) and g(n) explicitly without any matrices.
1 Like
I think here we can have the transformation matrix A as
[
[a, b, c, 1, 1, 0, 0],
[1, 0, 0, 0, 0, 0, 0],
[0, 1, 0, 0, 0, 0, 0],
[0, 0, 0, 1, 3, 3, 1],
[0, 0, 0, 0, 1, 2, 1],
[0, 0, 0, 0, 0, 1, 1],
[0, 0, 0, 0, 0, 0, 1]
]
where my X(n) is
[ f(n), f(n-1), f(n-2), (n+1)^3 , (n+1)^2, (n+1), 1 ]
and X(x-1) is similarly
[ f(n-1), f(n-2), f(n-3), (n)^3 , (n)^2, (n), 1 ]
from this, we can easily see that
X(3) = A*X(2)
so, the recurrence relation will be
X(n) = A^(n-2) * X(2)