October Challenge 2019 Queries on Matrix

Official Editorial : https://discuss.codechef.com/t/jiit-editorial/39300

My solution is really complicated. As far as viewing other people's solutions, more simple solution exists.

We can consider the row and the col independently, so it is enough to focus on only the row. What we should find is the number of ways such that the number of cols added odd times is odd. First, we can solve this problem by DP with dp[the number of operations][the number of odd cols] = the number of ways. The number of operations is extremely large, but we can still solve it using fast power method. Up to this point, we can obtain the first sub-score.

Next, we speed up the finding the power of a matrix using the theory of linear algebra. By Cayley-Hamilton's theorem, the following statement holds: Let $p(x)$ be the characteristic polynomial $\det(xE-A)$, then $p(A)$ always equals to $O$. If we treat $A$ as the indeterminant of polynomial, we can consider of the division of $A^Q$ and $p(A)$. When divide $A^Q$ by $p(A)$, since $p(A)=O$, $A^Q$ are reduced into $\square E + \square A + \cdots \square A^N$. If we already have $A^k \vec{v}$ for some $\vec{v}$, we can easily compute $A^{k+1} \vec{v}$ because A is sparse. So, its time complexity extremely reduced.

We haven't explained the method for finding the characteristic polynomial yet. There are two ways to find them. The first is Berlekamp-Massay algorithm, which is slightly slow than the second algorithm but the difference is quite small. The second algorithm is cofactor expansion. The matrix used in this problem is almost diagonal, so cofactor expansion works well. If we properly expand it, the second order recurrence relation will appear. By the way, such a matrix like this problem is called tridiagonal matrix.

Finally, I reduced the size of this problem into half because it isn't fast enough yet.