Python | Blazing fast O(log n) solution using modular matrix exponentiation
Intuition\nThis solution is an extension to the solution for the same problem where $m = 3$ which can be found here. \n\nFor simplicity, we use $0,1,2$ to denot
# Intuition\nThis solution is an extension to the solution for the same problem where $m = 3$ which can be found [here](https://leetcode.com/problems/number-of-ways-to-paint-n-3-grid/solutions/5222661/python-simple-dp-and-fast-matrix-multiplication-with-full-explanation/). \n\nFor simplicity, we use $0,1,2$ to denote the colors red, green and blue (or permutations of these colors).\n\nTo solve this problem, a key component we need to understand is the answer to the question: given a column of tiles colored properly, which are the properly colored columns that can immediately follow it?\n\nAn important and helpful observation is that we can consider patterns of columns instead of specific columns. We say to columns share the same pattern if the columns are equivalent up to some permutation of the colors. For example, in the case where $m=4$, the columns $0102$ and $2021$ are clearly not equivalent but they share the same pattern (using the permutation that switches $0\\to 2, 1\\to 0, 2\\to 1$).\n\n# Approach\nGiven a value of $m$, let $p_1, p_2, \\ldots, p_k$ be the distinct patters of properly colored columns of height $m$ (for example, it\'s easy to verify that for $m=3$ there are 2 patterns and for $m=4$ there are 4 - where two are mirror symmetries of one another). Note that since $m$ is small, we can compute once, by brute force the incidence mapping that computes for each $1 \\leq i, j \\leq k$ the number of possible column coloring of pattern $p_i$ that can follow a column coloring of pattern $p_j$. This will come in handy in just a minute.\n\nLet $v$ be the $k$-length vector whose $i$-th entry is the number of properly colored columns of patter $p_i$. For example, with $m=3$ the patterns are $p_1 = 012, p_2 = 010$ and $v = \\begin{bmatrix}6\\\\6\\end{bmatrix}$. Next, let $M$ be the $k\\times k$ matrix where $M_{i,j}$ denotes the incidence described above (i.e., the number of possible column colorings of pattern $p_i$ that can follow a column coloring of pattern $p_j$). For example, in the case of $m=3$, this is the matrix  $M = \\begin{bmatrix}2&2\\\\2&3\\end{bmatrix}$.\n\nWith this notation, we can see that $(Mv)_i = \\sum_{j} M_{i,j}\\cdot v_j$ is the number of possible coloring for the second column of pattern $p_i$ (and so $\\sum_i (Mv)_i$ is the total possible coloring of the second row or the answer for the query `colorTheGrid(m, 2)`). We can compute the answer for the next column by computing $M^2 \\cdot v$ and summing the values, and in general, the sum of entries in $M^k \\cdot v$ is precisely `colorTheGrid(m, k+1)` (where we remember to take modulo of the results).\n\nWith $M,v$ computed manually (and since they have dimensions at most $8 \\times 8$ for $m \\leq 5$), this already gives rise to an $O(n)$ algorithm: compute $M^{n-1}\\cdot v$ and sum the entries in the resulting vector, but we can do better. We compute $M^{n-1}$ using modular matrix exponentiation which requires only $O(\\log n)$ iterations, each one in $O(1)$ time (the matrix entries remain $O(1)$ size since we take modulo at each step of the process and so they are always bounded by $10^9+7$). See [here](https://leetcode.com/problems/number-of-ways-to-paint-n-3-grid/solutions/5222661/python-simple-dp-and-fast-matrix-multiplication-with-full-explanation/) for a thorough explanation on the algorithm and a step-by-step construction of $M,v$ for the case where $m=3$.\n\nOne final touch is to notice that when $m=1,2$, the results can be computed directly. In the solution below we have manually computed the values of $M,v$ for $m=3,4,5$ and used `numpy` for algebraic operations.\n\n# Complexity\n- Time complexity:\nAs stated above, the algorithm requires $O(\\log n)$ iterations, each one in time $O(1)$, for a total of $O(\\log n)$ running time. \n\n- Space complexity:\nAs all entries of the intermediate matrices and vectors are bounded by $10^9+7$, we require $O(1)$ space.\n\nIt is worth noting that due to the small values of $n$ tested, this code performs in practice roughly as well as the simple DP approach whose runtime is around $O(2^m \\cdot n)$. However, this solution can compute values of $n$ for which the DP solution will not halt in reasonable time.\n\n\n# Code\n```\ndef colorTheGrid(self, m: int, n: int) -> int:\n    M = 10**9+7\n    if m == 1: return (pow(2, n-1, M)*3) % M\n    if m == 2: return (pow(3, n-1, M)*6) % M\n    v1 = self.choose_vec(m)\n    A = self.choose_mat(m)\n    A = self.modexp(A, n-1, M)\n    return sum(np.matmul(A, v1)) % M\n\ndef choose_vec(self, m):\n    if m == 3: return np.array([6, 6], dtype=int)\n    if m == 4: return np.array([6, 12, 6], dtype=int)\n    if m == 5: return np.array([6, 6, 6, 6, 6, 6, 6, 6], dtype=int)\n\ndef choose_mat(self, m):\n    if m == 3: return np.array([[2, 2], [2, 3]], dtype=int)\n    if m == 4: return np.array([[3, 2, 1], [4, 4, 2], [1, 1, 2]], dtype=int)\n    if m == 5: return np.array([[3, 2, 2, 1, 0, 1, 2, 2],\n                                [2, 2, 2, 1, 1, 1, 1, 1],\n                                [2, 2, 2, 1, 0, 1, 2, 2],\n                                [1, 1, 1, 2, 1, 1, 1, 1],\n                                [0, 1, 0, 1, 2, 1, 0, 1],\n                                [1, 1, 1, 1, 1, 2, 1, 1],\n                                [2, 1, 2, 1, 0, 1, 2, 1],\n                                [2, 1, 2, 1, 1, 1, 1, 2]\n                                ], dtype=int)\n\ndef modexp(self, A, k, M):\n    n = A.shape[0]\n    res = np.identity(n, dtype=int)\n    while k:\n        if k % 2 == 1:\n            res = np.matmul(res, A) % M\n        A = np.matmul(A, A) % M\n        k //= 2\n    return res     \n```
['Math', 'Matrix', 'Combinatorics', 'Python3']