- Matrix Exponentiation
There are three people (Sherlock, Watson and Mycroft) and N problems. Each problem will be solved by only one person and that can be any of the three people. But there are a few conditions that are to be met. The conditions are:
- Mycroft can solve at most 1 problem of any 3 consecutive ones.
- Watson can solve any number of questions but not 2 consecutive (Basically 1 problem of any 2 consecutive ones).
- Sherlock can solve at most 2 problems of any 4 consecutive problems.
Your task is to find the number of ways they can solve the N problems.
O(logn*64^3) for each test case
CORE IDEA BEHIND THE PROBLEM :
Finding the recurrence relation, building up the matrix and using matrix exponentiation to calculate answer for N problems.
Step 1 (Recurrence Relation):
We define a state <b><i>f(n, i, j, k)</i></b> as number of ways of solving <b><i>n</i></b> problems and <ul> <li><b><i>i</i></b> is a 2 bit number indicating whether the last two problems were solved by Mycroft or not.</li> <li><b><i>j</i></b> is a 1 bit number indicating whether the last problem was solved by Watson or not.</li> <li><b><i>k</i></b> is a 3 bit number indicating whether the last three problems were solved by Sherlock or not.</li> </ul> In each masked number <b><i>i, j and k</i></b>, if the <b>bth</b> bit from the last is set, then that means that the last bth problem was solved by him, othewise not. Example say k = (100)<sub>2</sub> : This indicates last problem was solved by Sherlock while 2nd and 3rd last were not. <b>Recurrences:</b> <ul> <li>If <b><i>j = 0</i></b> then Watson can solve the <b><i>nth</i></b> problem hence: <b><i>f(n, i, j, k) += f(n - 1, i, 1, k)</i></b></li> <li>If <b><i>i</i></b> has number of set bits < 1 then Mycroft can solve the <b><i>nth</i></b> problem hence: <b><i>f(n, i, j, k) += f(n - 1, (i << 2) + 1, j, k)</i></b></li> <li>If <b><i>k</i></b> has number of set bits < 2 then Sherlock can solve the <b><i>nth</i></b> problem hence: <b><i>f(n, i, j, k) += f(n - 1, i, j, (1 << k) + 1)</i></b></li> </ul> <b>Step 2</b> Since f(n,*) depends on f(n-1,*) the problem can be converted to matrix exponentiation problem with dimensions corresponding to parameters that are part of *. Here DP solution uses more than 1 dimension other than n , but they can be combined together into a single parameter. Let mask be 6 bit variable , Least 3 significant bits indicate sherlock's status on last 3 problems 4th least significant bits indicate watson's status on last problem. other 2 bits indicate mycroft's status on last 2 problems. s = (k>>0)&7; w = (k>>3)&1; m = (k>>4)&3; Now using conditions of recurrence described above we can create the matrix. <b>Step 3</b> In a general matrix expo problem we have equation of form <b>A <sub>n</sub> = T A<sub>n-1</sub></b> A<sub>i</sub> is column matrix with dimension of 2<sup>6</sup> (in this case) i<sup>th</sup> storing number of solutions with status flag after solving last problem be <b>i</b> if F(n,i) = ... + x * F(n,j) + ... <b>T[i][j] = x</b>