1931. 用三种不同颜色为网格涂色

mod_value = 10**9 + 7
class Solution:def colorTheGrid(self, m: int, n: int) -> int:# 1、预处理所有合法的单行涂色方案# 存储 3^i，用于快速计算颜色编码的每一位（类似位运算）#  [3^0, 3^1, 3^2, ..., 3^(m-1)]pow3 = [3**i for i in range(m)]# 存储所有合法的单行涂色方案（即同一行内相邻格子颜色不同）valid = []for color in range(3**m):for i in range(1, m):# color // pow3[i] % 3表示颜色编码 color 的第 i 位（从右往左数，最低位是 i=0）if color // pow3[i] % 3 == color //pow3[i-1] % 3:break # 相邻颜色相同，非法else:valid.append(color)