Well explained dude !!
Hi,
I was not able to understand how we have (m-1) choices when the last two elements are different[f(i,1)=(M−1)∗(f(i−1,1)+f(i−1,2))]?. I can see why it is (m-1) choices for f(i-1,2) but If the last two elements are different then the current element can be any of the ‘m’ choices?.
I am using the exact same recurrence, but I am getting both WA and TLE.
This is my submission.
Could someone tell me why this is wrong?
https://www.codechef.com/viewsolution/34698788
please help please i am getting tle after applying matrix exponentiation
please some one please help @taran_1407 @teja349
I thought it was a pnc question 
You should implement matrix exponentiation approache without recursion.
An awesome problems with an awesome editorial !!
I used a vector implementation and it took more than 1s (1.34s to be exact) to run whereas it took just 0.21 s in the global 2D array implementation.
If the time limit was 1sec instead of 2 sec, my first AC code would have given TLE.
One of the advantages of vectors is that they can be passed very easily (in comparison to 2D arrays).
So I am looking for some optimization with which I can get that fast runtime with vectors (not by defining them globally) ?