Python 3: TC O(8**m log(n)), SC O(4**m): Transition Matrix, Scaling and Squaring
Intuition\n\nWe want the total ways. A natural subproblem is to get the total ways to get n columns ending with each valid color pattern.\n\nIf we can do that, 
# Intuition\n\nWe want the total ways. A natural subproblem is to get the total ways to get `n` columns ending with each valid color pattern.\n\nIf we can do that, then for each color pattern `c`, we can\n* find all the other color patterns `c\'` we can append this column to\n* add up all ways to get `n-1` columns with patterns `c\'`\n\nThis is a classic DP problem. For each `c` we\'d iterate over the `O(numPatterns)` other patterns `c\'`, and if they\'re compatible, add the ways to make 1 fewer column with that pattern `c\'`.\n\n## Speeding Up: Transition Matrix\n\nThe above algorithm takes `O(numPatterns**2)` for each number of columns, so `O(numPatterns**2 * n)`.\n\nBut we also see above that the ways\n* only depends on the prior column\n* and the operation is linear and the same for all steps\n\nIn other words we can find a matrix `T` where `ways_n = T*ways_{n-1}`. `T[c, c\'] == 1` if you can append pattern `c` to pattern `c\'`. That way matrix multiplication is the same as the above sum of `c\'` ways for each `c`.\n\nBy induction we find that `ways_n = T * T * ways{n-2} = ... = T**(n-1)*ways_1`. We know `ways_1`: it\'s all ones, there\'s one way to make a single column with each pattern.\n\nSo if we can\n* get all of the valid single column arrangements\n* and fill in `T[c, c\']`, 1 if `c` and `c\'` are compatible and 0 otherwise\n* and compute `T**(n-1)` in log time\n* then we get a much faster algorithm for large `n`\n\n# Approach\n\n## All Column Configs: DFS + BT\n\nWe can use DFS+backtracking to get all column configurations. The first color can be anything. Each subsequent color can be anything besides the prior color in that row.\n\n## Transition Matrix: Brute Force\n\nThen for each of the `C` column configurations\n* iterate over each `c in range(C)`\n* for `c\' != c` we can check if any color are the same, if so then we can\'t attach `c` to `c\'`. Otherwise we can, and we set `T[c, c\'] = 1`. The logic is the same if we swap `c` and `c\'` so `T` is symmetric\n\n## Fast `T**(n-1)`: Scaling and Squaring\n\nWe can use the classic scale-and-square method. It works just as well*** for matrices as it does for scalars:\n* for the current bit `b` of `n`, we need\n  * `T**b`, which I call `P` for "current **P**ower of T"\n  * the accumulation of products `T**(n-1)`\n\nMatrix multiplication is all products and summation, which commute with taking residues mod `BIG`. Therefore we can aggressively reduce values mod `BIG` to avoid overflow.\n\n*** "just as well" isn\'t quite true: BE VERY VERY CAREFUL ABOUT OVERFLOW. In fact, in this problem, I had overflow problems when trying to use numpy!\n\nThe reason is entries in a matrix can obviously be up to `BIG-1`. When we take a matrix product, numpy does not do any modular arithmetic, there\'s no option for it. For `m=5` there are 48 column patterns, so we\'re summing 48 products of max size `BIG-1` squared. Yikes. That works out to be `2 ** 65.5` or so with a calculator, which is above `np.uint64`, the largest integer datatype. Floats go higher, but we\'d get roundoff problems.\n\n**So we can\'t use numpy in this problem because of overflow** Instead, I wrote my own "mult_mod" function that does matrix multiplication A*B mod `BIG`.\n\n# Complexity\n- Time complexity:\n  - DFS + BT: `O(m)` ops for each column config, of which there are `3*2**(m-1)` for a total of `O(m*2**(m-1))`\n  - filling in `T`: `O(m)` for each pair, so `O(m*2**(2*m))` operations, `2**(m-1)` squared pairs\n  - matrix multiplies: we have `2**(m-1)` rows and columns, so matrix multiplication is cubic in that for `O(8**m)` operations. This is the leading order of complexity\n  - for scaling and squaring we need to do `O(log(n))` matrix multiplications, hence the overall complexity\n\n- Space complexity: `O(4**m)`, our matrices have `O(2**m)` rows and columns, and thus `O(2**m * 2**m) = O(4**m)` entries\n\n## Further Improvements?\n\nWe could probably reduce space usage if we got rid of the scaling-and-squaring, and instead stored `T` as a sparse matrix. Then we\'d have to do `O(N)` multiplies, but `T` would take a lot less space to store.\n\nI think the trick to these problems in general is to identify the shorter axis and exploit the rows >> cols or cols >> rows to speed things up.\n\nIn this case cols >> rows so we picked an approach that scales very favorably in `n`, not so much obviously in `m`.\n\n# Code\n```\nimport numpy as np\n\nclass Solution:\n    def colorTheGrid(self, m: int, n: int) -> int:\n        # m x n grid\n        #\n        # each cell is initially white\n        #   > paint each cell r, g, b\n        #   > all must be painted\n        # Return the number of ways to color the grid with no two adj cells having the same color\n\n        # neat. combinatorics, row/col optimization probably, etc.\n\n        # wlog have to color the first row, which is special b/c there are no constraints on it\n        # other than within the same row\n\n        # 3 ways to pick the first cell\n        # then 2 diff colors exist for the next\n        # and 2 diff after that for the next, etc.\n        # for a total of 3*2**(n-1) ways\n\n        # c0  c1  c2  c3  c4  ...\n        # c1  ?                   # if we start with c1, we have two choices b/c there\'s one unique color\n        #                         # if we start with the third color, then ? has only one choice\n        # this gets complicated, probably there\'s an optimization but hard to say\n\n        ## so something a bit more brute force: notice that m <= 5 so rows are very short, cheap\n        #\n        # idea: we can form all of the 3*2**4 = 48 column configurations\n        # and the columns they can attach to\n        # then we can use a transition matrix approach\n\n        BIG = 10**9+7\n\n        if m == 1:\n            return 3 * pow(2, n-1, BIG) % BIG # 3 choices for first, each later has 2 different colors\n\n        # all configs: DFS + bt\n        configs = []\n        curr = []\n        def dfs(r: int) -> None:\n            if r == 0:\n                for c in \'rgb\':\n                    curr.append(c)\n                    dfs(1)\n                    curr.pop()\n            elif r == m:\n                configs.append(\'\'.join(curr))\n            else:\n                for c in \'rgb\':\n                    if c == curr[-1]: continue\n\n                    curr.append(c)\n                    dfs(r+1)\n                    curr.pop()\n\n        dfs(0)\n\n        # build transition matrix\n        C = len(configs)\n        T = [[0]*C for _ in range(C)]\n        for c1 in range(C):\n            for c2 in range(c1):\n                if all(a != b for a, b, in zip(configs[c1], configs[c2])):\n                    # no conflicts: we can append a column of config c1 to c2 and vice-versa\n                    T[c1][c2] = 1\n                    T[c2][c1] = 1\n\n        # TODO: use Lapack, etc. to exploit the symmetric nature of the transition matrix\n        \n        # we advance to 2, 3, etc. ways, n-1 total. If we represent ways_n, the ways to end with\n        # each column pattern after n steps as a vector of length C, then\n        #    > ways_n = T*ways_{n-1}\n        #             = T*T*ways{n-2}\n        #             = ...\n        #             = T**(n-1) * ways_1\n        #\n        # We know ways_1 is the ones vector; there is one way to have a single column in each of\n        # the single columns\n        #\n        # So we can use scaling-and-squaring mod BIG to get T**(n-1) in log time\n        \n        def mult_mod(A, B):\n            """Returns A.dot(B) mod BIG"""\n            # we need this because A.dot(B) in numpy doesn\'t have a mod argument\n            # as a result we have have up to 48 entries of size BIG-1 multiplied together\n            # and 48*(BIG-1)**2 is above the max uint64 value!!\n\n            out = [[0]*C for _ in range(C)]\n            for i in range(C):\n                for j in range(C):\n                    for k in range(C):\n                        out[i][j] = (out[i][j] + A[i][k]*B[k][j]) % BIG\n\n            return out\n\n        # repeated scaling and squaring\n        n -= 1\n        Tn = [[0]*C for _ in range(C)]\n        for i in range(C): Tn[i][i] = 1\n        P = [t[:] for t in T]\n        while n:\n            if n & 1:\n                Tn = mult_mod(Tn, P)\n\n            # move on to next bit of n\n            #     lsb will be 2*lsb, and thus P**(2*lsb) == (P**lsb) ** 2\n            P = mult_mod(P, P)\n            n >>= 1\n\n        return sum(sum(row) for row in Tn) % BIG\n```
['Python3']