给你两个整数 m 和 n 。构造一个 m x n 的网格，其中每个单元格最开始是白色。请你用 红、绿、蓝 三种颜色为每个单元格涂色。所有单元格都需要被涂色。

涂色方案需要满足：不存在相邻两个单元格颜色相同的情况 。返回网格涂色的方法数。因为答案可能非常大， 返回 对 109 + 7 取余 的结果。

 

示例 1：

输入：m = 1, n = 1
输出：3
解释：如上图所示，存在三种可能的涂色方案。

示例 2：

输入：m = 1, n = 2
输出：6
解释：如上图所示，存在六种可能的涂色方案。

示例 3：

输入：m = 5, n = 5
输出：580986

 

提示：

• 1 <= m <= 5
• 1 <= n <= 1000

方法一：状态压缩动态规划

提示 $1$

要使得任意两个相邻的格子的颜色均不相同，我们需要保证：

• 同一行内任意两个相邻格子的颜色互不相同；

• 相邻的两行之间，同一列上的两个格子的颜色互不相同。

因此，我们可以考虑：

• 首先通过枚举的方法，找出所有对一行进行涂色的方案数；

• 然后通过动态规划的方法，计算出对整个 $m \times n$ 的方格进行涂色的方案数。

在本题中，$m$ 和 $n$ 的最大值分别是 $5$ 和 $1000$，我们需要将较小的 $m$ 看成行的长度，较大的 $n$ 看成列的长度，这样才可以对一行进行枚举。

思路与算法

我们首先枚举对一行进行涂色的方案数。

对于我们可以选择红绿蓝三种颜色，我们可以将它们看成 $0, 1, 2$。这样一来，一种涂色方案就对应着一个长度为 $m$ 的三进制数，其十进制的范围为 $[0, 3^m)$。

因此，我们可以枚举 $[0, 3^m)$ 范围内的所有整数，将其转换为长度为 $m$ 的三进制串，再判断其是否满足任意相邻的两个数位均不相同即可。

随后我们就可以使用动态规划来计算方案数了。我们用 $f[i][\textit{mask}]$ 表示我们已经对 $0, 1, \cdots, i$ 行进行了涂色，并且第 $i$ 行的涂色方案对应的三进制表示为 $\textit{mask}$ 的前提下的总方案数。在进行状态转移时，我们可以考虑第 $i-1$ 行的涂色方案 $\textit{mask}'$：

$$
f[i][\textit{mask}] = \sum_{\textit{mask} ~与~ \textit{mask}' 同一数位上的数字均不相同} f[i-1][\textit{mask}']
$$

只要 $\textit{mask}'$ 与 $\textit{mask}$ 同一数位上的数字均不相同，就说明这两行可以相邻，我们就可以进行状态转移。

最终的答案即为所有满足 $\textit{mask} \in [0, 3^m)$ 的 $f[n-1][\textit{mask}]$ 之和。

细节

上述动态规划中的边界条件在于第 $0$ 行的涂色。当 $i=0$ 时，$f[i-1][..]$ 不是合法状态，无法进行转移，我们需要对它们进行特判：即如果 $\textit{mask}$ 任意相邻的两个数位均不相同，那么 $f[0][\textit{mask}] = 1$，否则 $f[0][\textit{mask}] = 0$。

在其余情况下的状态转移时，对于给定的 $\textit{mask}$，我们总是要找出所有满足要求的 $\textit{mask}'$，因此我们不妨也把它们预处理出来，具体可以参考下方给出的代码。

最后需要注意的是，在状态转移方程中，$f[i][..]$ 只会从 $f[i-1][..]$ 转移而来，因此我们可以使用两个长度为 $3^m$ 的一维数组，交替地进行状态转移。

代码

###C++

class Solution {
private:
    static constexpr int mod = 1000000007;

public:
    int colorTheGrid(int m, int n) {
        // 哈希映射 valid 存储所有满足要求的对一行进行涂色的方案
        // 键表示 mask，值表示 mask 的三进制串（以列表的形式存储）
        unordered_map<int, vector<int>> valid;

        // 在 [0, 3^m) 范围内枚举满足要求的 mask
        int mask_end = pow(3, m);
        for (int mask = 0; mask < mask_end; ++mask) {
            vector<int> color;
            int mm = mask;
            for (int i = 0; i < m; ++i) {
                color.push_back(mm % 3);
                mm /= 3;
            }
            bool check = true;
            for (int i = 0; i < m - 1; ++i) {
                if (color[i] == color[i + 1]) {
                    check = false;
                    break;
                }
            }
            if (check) {
                valid[mask] = move(color);
            }
        }

        // 预处理所有的 (mask1, mask2) 二元组，满足 mask1 和 mask2 作为相邻行时，同一列上两个格子的颜色不同
        unordered_map<int, vector<int>> adjacent;
        for (const auto& [mask1, color1]: valid) {
            for (const auto& [mask2, color2]: valid) {
                bool check = true;
                for (int i = 0; i < m; ++i) {
                    if (color1[i] == color2[i]) {
                        check = false;
                        break;
                    }
                }
                if (check) {
                    adjacent[mask1].push_back(mask2);
                }
            }
        }

        vector<int> f(mask_end);
        for (const auto& [mask, _]: valid) {
            f[mask] = 1;
        }
        for (int i = 1; i < n; ++i) {
            vector<int> g(mask_end);
            for (const auto& [mask2, _]: valid) {
                for (int mask1: adjacent[mask2]) {
                    g[mask2] += f[mask1];
                    if (g[mask2] >= mod) {
                        g[mask2] -= mod;
                    }
                }
            }
            f = move(g);
        }

        int ans = 0;
        for (int num: f) {
            ans += num;
            if (ans >= mod) {
                ans -= mod;
            }
        }
        return ans;
    }
};

###Python

class Solution:
    def colorTheGrid(self, m: int, n: int) -> int:
        mod = 10**9 + 7
        # 哈希映射 valid 存储所有满足要求的对一行进行涂色的方案
        # 键表示 mask，值表示 mask 的三进制串（以列表的形式存储）
        valid = dict()
        
        # 在 [0, 3^m) 范围内枚举满足要求的 mask
        for mask in range(3**m):
            color = list()
            mm = mask
            for i in range(m):
                color.append(mm % 3)
                mm //= 3
            if any(color[i] == color[i + 1] for i in range(m - 1)):
                continue
            valid[mask] = color
        
        # 预处理所有的 (mask1, mask2) 二元组，满足 mask1 和 mask2 作为相邻行时，同一列上两个格子的颜色不同
        adjacent = defaultdict(list)
        for mask1, color1 in valid.items():
            for mask2, color2 in valid.items():
                if not any(x == y for x, y in zip(color1, color2)):
                    adjacent[mask1].append(mask2)
        
        f = [int(mask in valid) for mask in range(3**m)]
        for i in range(1, n):
            g = [0] * (3**m)
            for mask2 in valid.keys():
                for mask1 in adjacent[mask2]:
                    g[mask2] += f[mask1]
                    if g[mask2] >= mod:
                        g[mask2] -= mod
            f = g
            
        return sum(f) % mod

###Java

class Solution {
    static final int mod = 1000000007;

    public int colorTheGrid(int m, int n) {
        // 哈希映射 valid 存储所有满足要求的对一行进行涂色的方案
        Map<Integer, List<Integer>> valid = new HashMap<>();
        // 在 [0, 3^m) 范围内枚举满足要求的 mask
        int maskEnd = (int) Math.pow(3, m);
        for (int mask = 0; mask < maskEnd; ++mask) {
            List<Integer> color = new ArrayList<>();
            int mm = mask;
            for (int i = 0; i < m; ++i) {
                color.add(mm % 3);
                mm /= 3;
            }
            boolean check = true;
            for (int i = 0; i < m - 1; ++i) {
                if (color.get(i).equals(color.get(i + 1))) {
                    check = false;
                    break;
                }
            }
            if (check) {
                valid.put(mask, color);
            }
        }

        // 预处理所有的 (mask1, mask2) 二元组，满足 mask1 和 mask2 作为相邻行时，同一列上两个格子的颜色不同
        Map<Integer, List<Integer>> adjacent = new HashMap<>();
        for (int mask1 : valid.keySet()) {
            for (int mask2 : valid.keySet()) {
                boolean check = true;
                for (int i = 0; i < m; ++i) {
                    if (valid.get(mask1).get(i).equals(valid.get(mask2).get(i))) {
                        check = false;
                        break;
                    }
                }
                if (check) {
                    adjacent.computeIfAbsent(mask1, k -> new ArrayList<>()).add(mask2);
                }
            }
        }

        Map<Integer, Integer> f = new HashMap<>();
        for (int mask : valid.keySet()) {
            f.put(mask, 1);
        }
        for (int i = 1; i < n; ++i) {
            Map<Integer, Integer> g = new HashMap<>();
            for (int mask2 : valid.keySet()) {
                for (int mask1 : adjacent.getOrDefault(mask2, new ArrayList<>())) {
                    g.put(mask2, (g.getOrDefault(mask2, 0) + f.getOrDefault(mask1, 0)) % mod);
                }
            }
            f = g;
        }

        int ans = 0;
        for (int num : f.values()) {
            ans = (ans + num) % mod;
        }
        return ans;
    }
}

###C#

public class Solution {
    private const int mod = 1000000007;

    public int ColorTheGrid(int m, int n) {
        // 哈希映射 valid 存储所有满足要求的对一行进行涂色的方案
        var valid = new Dictionary<int, List<int>>();
        // 在 [0, 3^m) 范围内枚举满足要求的 mask
        int maskEnd = (int)Math.Pow(3, m);
        for (int mask = 0; mask < maskEnd; ++mask) {
            var color = new List<int>();
            int mm = mask;
            for (int i = 0; i < m; ++i) {
                color.Add(mm % 3);
                mm /= 3;
            }
            bool check = true;
            for (int i = 0; i < m - 1; ++i) {
                if (color[i] == color[i + 1]) {
                    check = false;
                    break;
                }
            }
            if (check) {
                valid[mask] = color;
            }
        }

        // 预处理所有的 (mask1, mask2) 二元组，满足 mask1 和 mask2 作为相邻行时，同一列上两个格子的颜色不同
        var adjacent = new Dictionary<int, List<int>>();
        foreach (var mask1 in valid.Keys) {
            foreach (var mask2 in valid.Keys) {
                bool check = true;
                for (int i = 0; i < m; ++i) {
                    if (valid[mask1][i] == valid[mask2][i]) {
                        check = false;
                        break;
                    }
                }
                if (check) {
                    if (!adjacent.ContainsKey(mask1)) {
                        adjacent[mask1] = new List<int>();
                    }
                    adjacent[mask1].Add(mask2);
                }
            }
        }

        var f = new Dictionary<int, int>();
        foreach (var mask in valid.Keys) {
            f[mask] = 1;
        }
        for (int i = 1; i < n; ++i) {
            var g = new Dictionary<int, int>();
            foreach (var mask2 in valid.Keys) {
                if (adjacent.ContainsKey(mask2)) {
                    foreach (var mask1 in adjacent[mask2]) {
                        if (!g.ContainsKey(mask2)) {
                            g[mask2] = 0;
                        }
                        g[mask2] = (g[mask2] + f[mask1]) % mod;
                    }
                }
            }
            f = g;
        }

        int ans = 0;
        foreach (var num in f.Values) {
            ans = (ans + num) % mod;
        }
        return ans;
    }
}

###Go

const mod = 1000000007

func colorTheGrid(m int, n int) int {
// 哈希映射 valid 存储所有满足要求的对一行进行涂色的方案
valid := make(map[int][]int)

// 在 [0, 3^m) 范围内枚举满足要求的 mask
maskEnd := int(math.Pow(3, float64(m)))
for mask := 0; mask < maskEnd; mask++ {
color := make([]int, m)
mm := mask
for i := 0; i < m; i++ {
color[i] = mm % 3
mm /= 3
}
check := true
for i := 0; i < m-1; i++ {
if color[i] == color[i+1] {
check = false
break
}
}
if check {
valid[mask] = color
}
}

// 预处理所有的 (mask1, mask2) 二元组，满足 mask1 和 mask2 作为相邻行时，同一列上两个格子的颜色不同
adjacent := make(map[int][]int)
for mask1 := range valid {
for mask2 := range valid {
check := true
for i := 0; i < m; i++ {
if valid[mask1][i] == valid[mask2][i] {
check = false
break
}
}
if check {
adjacent[mask1] = append(adjacent[mask1], mask2)
}
}
}

f := make(map[int]int)
for mask := range valid {
f[mask] = 1
}
for i := 1; i < n; i++ {
g := make(map[int]int)
for mask2 := range valid {
for _, mask1 := range adjacent[mask2] {
g[mask2] = (g[mask2] + f[mask1]) % mod
}
}
f = g
}

ans := 0
for _, num := range f {
ans = (ans + num) % mod
}
return ans
}

###C

#define MOD 1000000007

struct ListNode *createListNode(int val) {
    struct ListNode *obj = (struct ListNode*)malloc(sizeof(struct ListNode));
    obj->val = val;
    obj->next = NULL;
    return obj;
}

void freeList(struct ListNode *list) {
    while (list) {
        struct ListNode *p = list;
        list = list->next;
        free(p);
    }
}

typedef struct {
    int key;
    struct ListNode *val;
    UT_hash_handle hh;
} HashItem; 

HashItem *hashFindItem(HashItem **obj, int key) {
    HashItem *pEntry = NULL;
    HASH_FIND_INT(*obj, &key, pEntry);
    return pEntry;
}

bool hashAddItem(HashItem **obj, int key, int val) {
    HashItem *pEntry = hashFindItem(obj, key);
    struct ListNode *p = createListNode(val);
    if (!pEntry) {
        pEntry = (HashItem *)malloc(sizeof(HashItem));
        pEntry->key = key;
        pEntry->val = p;
        HASH_ADD_INT(*obj, key, pEntry);
    } else {
        p->next = pEntry->val;
        pEntry->val = p;
    }
    return true;
}

bool hashSetItem(HashItem **obj, int key, struct ListNode *list) {
    HashItem *pEntry = hashFindItem(obj, key);
    if (!pEntry) {
        pEntry = (HashItem *)malloc(sizeof(HashItem));
        pEntry->key = key;
        pEntry->val = list;
        HASH_ADD_INT(*obj, key, pEntry);
    } else {
        freeList(pEntry->val);
        pEntry->val = list;
    }
    return true;
}

struct ListNode* hashGetItem(HashItem **obj, int key) {
    HashItem *pEntry = hashFindItem(obj, key);
    if (!pEntry) {
        return NULL;
    }
    return pEntry->val;
}

void hashFree(HashItem **obj) {
    HashItem *curr = NULL, *tmp = NULL;
    HASH_ITER(hh, *obj, curr, tmp) {
        HASH_DEL(*obj, curr); 
        freeList(curr->val); 
        free(curr);
    }
}

// 主函数
int colorTheGrid(int m, int n) {
    // 哈希映射 valid 存储所有满足要求的对一行进行涂色的方案
    // 键表示 mask，值表示 mask 的三进制串（以列表的形式存储）
    HashItem *valid = NULL;
    // 在 [0, 3^m) 范围内枚举满足要求的 mask
    int mask_end = pow(3, m);
    for (int mask = 0; mask < mask_end; ++mask) {
        int mm = mask;
        int color[m];
        for (int i = 0; i < m; ++i) {
            color[i] = mm % 3;
            mm /= 3;
        }
        bool check = true;
        for (int i = 0; i < m - 1; ++i) {
            if (color[i] == color[i + 1]) {
                check = false;
                break;
            }
        }
        if (check) {
            for (int i = 0; i < m; i++) {
                hashAddItem(&valid, mask, color[i]);
            }
        }
    }

    // 预处理所有的 (mask1, mask2) 二元组，满足 mask1 和 mask2 作为相邻行时，同一列上两个格子的颜色不同
    HashItem *adjacent = NULL;
    for (HashItem *pEntry1 = valid; pEntry1; pEntry1 = pEntry1->hh.next) {
        int mask1 = pEntry1->key;
        for (HashItem *pEntry2 = valid; pEntry2; pEntry2 = pEntry2->hh.next) {
            int mask2 = pEntry2->key;
            bool check = true;
            for (struct ListNode *p1 = pEntry1->val, *p2 = pEntry2->val; p1 && p2; p1 = p1->next, p2 = p2->next) {
                if (p1->val == p2->val) {
                    check = false;
                    break;
                }
            }
            if (check) {
                hashAddItem(&adjacent, mask1, mask2);
            }
        }
    }

    int f[mask_end];
    memset(f, 0, sizeof(f));
    for (HashItem *pEntry = valid; pEntry; pEntry = pEntry->hh.next) {
        int mask = pEntry->key;
        f[mask] = 1;
    }
    for (int i = 1; i < n; ++i) {
        int g[mask_end];
        memset(g, 0, sizeof(g));
        for (HashItem *pEntry1 = valid; pEntry1; pEntry1 = pEntry1->hh.next) {
            int mask2 = pEntry1->key;
            for (struct ListNode *p = hashGetItem(&adjacent, mask2); p != NULL; p = p->next) {
                int mask1 = p->val;
                g[mask2] += f[mask1];
                if (g[mask2] >= MOD) {
                    g[mask2] -= MOD;
                }
            }
        }
        memcpy(f, g, sizeof(f));
    }

    int ans = 0;
    for (int i = 0; i < mask_end; i++) {
        ans += f[i];
        if (ans >= MOD) {
            ans -= MOD;
        }
    }
    hashFree(&valid);
    hashFree(&adjacent);
    return ans;
}

###JavaScript

var colorTheGrid = function(m, n) {
    const mod = 1000000007;
    // 哈希映射 valid 存储所有满足要求的对一行进行涂色的方案
    const valid = new Map();
    // 在 [0, 3^m) 范围内枚举满足要求的 mask
    const maskEnd = Math.pow(3, m);
    for (let mask = 0; mask < maskEnd; ++mask) {
        const color = [];
        let mm = mask;
        for (let i = 0; i < m; ++i) {
            color.push(mm % 3);
            mm = Math.floor(mm / 3);
        }
        let check = true;
        for (let i = 0; i < m - 1; ++i) {
            if (color[i] === color[i + 1]) {
                check = false;
                break;
            }
        }
        if (check) {
            valid.set(mask, color);
        }
    }

    // 预处理所有的 (mask1, mask2) 二元组，满足 mask1 和 mask2 作为相邻行时，同一列上两个格子的颜色不同
    const adjacent = new Map();
    for (const [mask1, color1] of valid.entries()) {
        for (const [mask2, color2] of valid.entries()) {
            let check = true;
            for (let i = 0; i < m; ++i) {
                if (color1[i] === color2[i]) {
                    check = false;
                    break;
                }
            }
            if (check) {
                if (!adjacent.has(mask1)) {
                    adjacent.set(mask1, []);
                }
                adjacent.get(mask1).push(mask2);
            }
        }
    }

    let f = new Map();
    for (const [mask, _] of valid.entries()) {
        f.set(mask, 1);
    }
    for (let i = 1; i < n; ++i) {
        const g = new Map();
        for (const [mask2, _] of valid.entries()) {
            for (const mask1 of adjacent.get(mask2) || []) {
                g.set(mask2, ((g.get(mask2) || 0) + f.get(mask1)) % mod);
            }
        }
        f = g;
    }

    let ans = 0;
    for (const num of f.values()) {
        ans = (ans + num) % mod;
    }
    return ans;
}

###TypeScript

function colorTheGrid(m: number, n: number): number {
    const mod = 1000000007;
    // 哈希映射 valid 存储所有满足要求的对一行进行涂色的方案
    const valid = new Map<number, number[]>();

    // 在 [0, 3^m) 范围内枚举满足要求的 mask
    const maskEnd = Math.pow(3, m);
    for (let mask = 0; mask < maskEnd; ++mask) {
        const color: number[] = [];
        let mm = mask;
        for (let i = 0; i < m; ++i) {
            color.push(mm % 3);
            mm = Math.floor(mm / 3);
        }
        let check = true;
        for (let i = 0; i < m - 1; ++i) {
            if (color[i] === color[i + 1]) {
                check = false;
                break;
            }
        }
        if (check) {
            valid.set(mask, color);
        }
    }

    // 预处理所有的 (mask1, mask2) 二元组，满足 mask1 和 mask2 作为相邻行时，同一列上两个格子的颜色不同
    const adjacent = new Map<number, number[]>();
    for (const [mask1, color1] of valid.entries()) {
        for (const [mask2, color2] of valid.entries()) {
            let check = true;
            for (let i = 0; i < m; ++i) {
                if (color1[i] === color2[i]) {
                    check = false;
                    break;
                }
            }
            if (check) {
                if (!adjacent.has(mask1)) {
                    adjacent.set(mask1, []);
                }
                adjacent.get(mask1)!.push(mask2);
            }
        }
    }

    let f = new Map<number, number>();
    for (const [mask, _] of valid.entries()) {
        f.set(mask, 1);
    }
    for (let i = 1; i < n; ++i) {
        const g = new Map<number, number>();
        for (const [mask2, _] of valid.entries()) {
            for (const mask1 of adjacent.get(mask2) || []) {
                g.set(mask2, ((g.get(mask2) || 0) + f.get(mask1)!) % mod);
            }
        }
        f = g;
    }

    let ans = 0;
    for (const num of f.values()) {
        ans = (ans + num) % mod;
    }
    return ans;
}

###Rust

use std::collections::HashMap;

const MOD: i32 = 1_000_000_007;

impl Solution {
    pub fn color_the_grid(m: i32, n: i32) -> i32 {
        let m = m as usize;
        let n = n as usize;
        // 哈希映射 valid 存储所有满足要求的对一行进行涂色的方案
        let mut valid = HashMap::new();
        // 在 [0, 3^m) 范围内枚举满足要求的 mask
        let mask_end = 3i32.pow(m as u32);
        for mask in 0..mask_end {
            let mut color = Vec::new();
            let mut mm = mask;
            for _ in 0..m {
                color.push(mm % 3);
                mm /= 3;
            }
            let mut check = true;
            for i in 0..m - 1 {
                if color[i] == color[i + 1] {
                    check = false;
                    break;
                }
            }
            if check {
                valid.insert(mask, color);
            }
        }

        // 预处理所有的 (mask1, mask2) 二元组，满足 mask1 和 mask2 作为相邻行时，同一列上两个格子的颜色不同
        let mut adjacent = HashMap::new();
        for (&mask1, color1) in &valid {
            for (&mask2, color2) in &valid {
                let mut check = true;
                for i in 0..m {
                    if color1[i] == color2[i] {
                        check = false;
                        break;
                    }
                }
                if check {
                    adjacent.entry(mask1).or_insert(Vec::new()).push(mask2);
                }
            }
        }

        let mut f = HashMap::new();
        for &mask in valid.keys() {
            f.insert(mask, 1);
        }
        for _ in 1..n {
            let mut g = HashMap::new();
            for &mask2 in valid.keys() {
                let mut total = 0;
                if let Some(list) = adjacent.get(&mask2) {
                    for &mask1 in list {
                        total = (total + f.get(&mask1).unwrap_or(&0)) % MOD;
                    }
                }
                g.insert(mask2, total);
            }
            f = g;
        }

        let mut ans = 0;
        for &num in f.values() {
            ans = (ans + num) % MOD;
        }
        ans
    }
}

复杂度分析

• 时间复杂度：$O(3^{2m} \cdot n)$。

  • 预处理 $\textit{mask}$ 的时间复杂度为 $O(m \cdot 3^m)$；

  • 预处理 $(\textit{mask}, \textit{mask}')$ 二元组的时间复杂度为 $O(3^{2m})$；

  • 动态规划的时间复杂度为 $O(3^{2m} \cdot n)$，其在渐近意义下大于前两者。

• 空间复杂度：$O(3^{2m})$。

  • 存储 $\textit{mask}$ 的哈希映射需要的空间为 $O(m \cdot 3^m)$；

  • 存储 $(\textit{mask}, \textit{mask}')$ 二元组需要的空间为 $O(3^{2m})$，在渐进意义下大于其余两者；

  • 动态规划存储状态需要的空间为 $O(3^m)$。

不过需要注意的是，在实际的情况下，当 $m=5$ 时，满足要求的 $\textit{mask}$ 仅有 $48$ 个，远小于 $3^m=324$；满足要求的 $(\textit{mask}, \textit{mask}')$ 二元组仅有 $486$ 对，远小于 $3^{2m}=59049$。因此该算法的实际运行时间会较快。

A代表第一种颜色，B代表第二种颜色，C代表第三种颜色。

0代表红色，1代表绿色，2代表蓝色。

1. m=1

第一行有3种情况，且接下来的所有行，都是2种情况

    long long mod = 1000000007;
    int ans=3;
    for(int i=1;i<n;++i)    
        ans= (ans * 2LL) % mod;
    return ans;

2. m=2

所有颜色排列有6种

01, 02, 10, 12, 20, 21

可分类为AB
对于第一行为AB，第二行则有BA、BC、CA三种情况，第三行同理有对应三种情况，第n行同理有三种情况。

    long long mod = 1000000007;
    int ans=6;
    for(int i=1;i<n;++i)
        ans= (ans * 3LL) % mod;
    return ans;

3. m=3

所有颜色排列有12种

010, 012, 020, 021, 101, 102, 120, 121, 201, 202, 210, 212

可分类为ABC和ABA

• ABC类：共6种：012, 021, 102, 120, 201, 210；
• ABA类：共6种：010, 020, 101, 121, 202, 212。

则可据此根据上一行的类型递推该行的类型种数。

• 第 i - 1 行是 ABC 类，第 i 行是 ABC 类：以 012 为例，那么第 i 行只能是120 或 201，方案数为 2；
• 第 i - 1 行是 ABC 类，第 i 行是 ABA 类：以 012 为例，那么第 i 行只能是101 或 121，方案数为 2；
• 第 i - 1 行是 ABA 类，第 i 行是 ABC 类：以 010 为例，那么第 i 行只能是102 或 201，方案数为 2；
• 第 i - 1 行是 ABA 类，第 i 行是 ABA 类：以 010 为例，那么第 i 行只能是101，121 或 202，方案数为 3。

故有递推式

f[i][0] = 2 * f[i - 1][0] + 2 * f[i - 1][1];
f[i][1] = 2 * f[i - 1][0] + 3 * f[i - 1][1];

4. m=4

所有颜色排列有24种
可分类为ABCA、ABCB、ABAB、ABAC
（实际上ABCB和ABAC可归为一类，见评论区用户AndrewPei代码）

• ABCA类：共6种
• ABCB类：共6种
• ABAB类：共6种
• ABAC类：共6种

则可据此根据上一行的类型递推该行的类型种数。

• 第 i - 1 行是 ABCA 类，第 i 行是 ABCA 类：方案数为 3；
• 第 i - 1 行是 ABCA 类，第 i 行是 ABCB 类：方案数为 2；
• 第 i - 1 行是 ABCA 类，第 i 行是 ABAB 类：方案数为 1；
• 第 i - 1 行是 ABCA 类，第 i 行是 ABAC 类：方案数为 2。
• 第 i - 1 行是 ABCB 类，第 i 行是 ABCA 类：方案数为 2；
• 第 i - 1 行是 ABCB 类，第 i 行是 ABCB 类：方案数为 2；
• 第 i - 1 行是 ABCB 类，第 i 行是 ABAB 类：方案数为 1；
• 第 i - 1 行是 ABCB 类，第 i 行是 ABAC 类：方案数为 2。
• 第 i - 1 行是 ABAB 类，第 i 行是 ABCA 类：方案数为 1；
• 第 i - 1 行是 ABAB 类，第 i 行是 ABCB 类：方案数为 1；
• 第 i - 1 行是 ABAB 类，第 i 行是 ABAB 类：方案数为 2；
• 第 i - 1 行是 ABAB 类，第 i 行是 ABAC 类：方案数为 1。
• 第 i - 1 行是 ABAC 类，第 i 行是 ABCA 类：方案数为 2；
• 第 i - 1 行是 ABAC 类，第 i 行是 ABCB 类：方案数为 2；
• 第 i - 1 行是 ABAC 类，第 i 行是 ABAB 类：方案数为 1；
• 第 i - 1 行是 ABAC 类，第 i 行是 ABAC 类：方案数为 2。

故有递推式

f[i][0] = 3 * f[i - 1][0] + 2 * f[i - 1][1] + 1 * f[i - 1][2] + 2 * f[i - 1][3];
f[i][1] = 2 * f[i - 1][0] + 2 * f[i - 1][1] + 1 * f[i - 1][2] + 2 * f[i - 1][3];
f[i][2] = 1 * f[i - 1][0] + 1 * f[i - 1][1] + 2 * f[i - 1][2] + 1 * f[i - 1][3];
f[i][3] = 2 * f[i - 1][0] + 2 * f[i - 1][1] + 1 * f[i - 1][2] + 2 * f[i - 1][3];

5. m=5

同理，实在是写不下去了，直接上递推式

f[i][0] = 3 * f[i - 1][0] + 2 * f[i - 1][1] + 2 * f[i - 1][2] + 1 * f[i - 1][3] + 0 * f[i - 1][4] + 1 * f[i - 1][5] + 2 * f[i - 1][6] + 2 * f[i - 1][7];
f[i][1] = 2 * f[i - 1][0] + 2 * f[i - 1][1] + 2 * f[i - 1][2] + 1 * f[i - 1][3] + 1 * f[i - 1][4] + 1 * f[i - 1][5] + 1 * f[i - 1][6] + 1 * f[i - 1][7];
f[i][2] = 2 * f[i - 1][0] + 2 * f[i - 1][1] + 2 * f[i - 1][2] + 1 * f[i - 1][3] + 0 * f[i - 1][4] + 1 * f[i - 1][5] + 2 * f[i - 1][6] + 2 * f[i - 1][7];
f[i][3] = 1 * f[i - 1][0] + 1 * f[i - 1][1] + 1 * f[i - 1][2] + 2 * f[i - 1][3] + 1 * f[i - 1][4] + 1 * f[i - 1][5] + 1 * f[i - 1][6] + 1 * f[i - 1][7];
f[i][4] = 0 * f[i - 1][0] + 1 * f[i - 1][1] + 0 * f[i - 1][2] + 1 * f[i - 1][3] + 2 * f[i - 1][4] + 1 * f[i - 1][5] + 0 * f[i - 1][6] + 1 * f[i - 1][7];
f[i][5] = 1 * f[i - 1][0] + 1 * f[i - 1][1] + 1 * f[i - 1][2] + 1 * f[i - 1][3] + 1 * f[i - 1][4] + 2 * f[i - 1][5] + 1 * f[i - 1][6] + 1 * f[i - 1][7];
f[i][6] = 2 * f[i - 1][0] + 1 * f[i - 1][1] + 2 * f[i - 1][2] + 1 * f[i - 1][3] + 0 * f[i - 1][4] + 1 * f[i - 1][5] + 2 * f[i - 1][6] + 1 * f[i - 1][7];
f[i][7] = 2 * f[i - 1][0] + 1 * f[i - 1][1] + 2 * f[i - 1][2] + 1 * f[i - 1][3] + 1 * f[i - 1][4] + 1 * f[i - 1][5] + 1 * f[i - 1][6] + 2 * f[i - 1][7];

代码如下(貌似系数可以矩阵快速幂递推来着，等我哪天有时间再试试)

class Solution {
public:
    int colorTheGrid(int m, int n) {
        long long mod = 1000000007;
        if(m==1)
        {
            int ans=3;
            for(int i=1;i<n;++i)    ans= ans * 2LL % mod;
            return ans;
        }
        else if(m==2)
        {
            int fi = 6;
            for(int i=1;i<n;++i)    fi= 3LL * fi % mod;
            return fi;
        }
        else if(m==3)
        {
            int fi0 = 6, fi1 = 6;
            for (int i = 1; i < n; ++i) {
                int new_fi0 = (2LL * fi0 + 2LL * fi1) % mod;
                int new_fi1 = (2LL * fi0 + 3LL * fi1) % mod;
                fi0 = new_fi0;
                fi1 = new_fi1;
            }
            return ((long long)fi0 + fi1) % mod;
        }
        else if(m==4)
        {
            //ABAB//ABAC//ABCA//ABCB
            int fi0 = 6, fi1 = 6, fi2=6, fi3=6;
            for (int i = 1; i < n; ++i) {
                int new_fi0 = (3LL * fi0 + 2LL * fi1+ 1LL*fi2+ 2LL*fi3) % mod;
                int new_fi1 = (2LL * fi0 + 2LL * fi1+ 1LL*fi2+2LL*fi3) % mod;
                int new_fi2 = (1LL * fi0 + 1LL * fi1+ 2LL*fi2 +1LL*fi3) % mod;
                int new_fi3 = (2LL * fi0 + 2LL * fi1+ 1LL*fi2+2LL*fi3) % mod;
                fi0 = new_fi0;
                fi1 = new_fi1;
                fi2 = new_fi2;
                fi3 = new_fi3;
            }
            return ((long long)fi0 + fi1+ fi2+ fi3) % mod;
        }
        else
        {
            //ABABA//ABABC//ABACA//ABACB//ABCAB//ABCAC//ABCBA//ABCBC
            int fi0 = 6, fi1 = 6, fi2=6 ,fi3 =6, fi4=6, fi5=6, fi6=6, fi7=6;
            for (int i = 1; i < n; ++i) {
                int new_fi0 = (3LL * fi0 + 2LL * fi1+ 2LL*fi2+ 1LL*fi3+ 0LL*fi4 +1LL*fi5 +2LL*fi6+2LL*fi7) % mod;
                int new_fi1 = (2LL * fi0 + 2LL * fi1+ 2LL*fi2+ 1LL*fi3+ 1LL*fi4 +1LL*fi5 +1LL*fi6+1LL*fi7) % mod;
                int new_fi2 = (2LL * fi0 + 2LL * fi1+ 2LL*fi2+ 1LL*fi3+ 0LL*fi4 +1LL*fi5 +2LL*fi6+2LL*fi7) % mod;
                int new_fi3 = (1LL * fi0 + 1LL * fi1+ 1LL*fi2+ 2LL*fi3+ 1LL*fi4 +1LL*fi5 +1LL*fi6+1LL*fi7) % mod;
                int new_fi4 = (0LL * fi0 + 1LL * fi1+ 0LL*fi2+ 1LL*fi3+ 2LL*fi4 +1LL*fi5 +0LL*fi6+1LL*fi7) % mod;
                int new_fi5 = (1LL * fi0 + 1LL * fi1+ 1LL*fi2+ 1LL*fi3+ 1LL*fi4 +2LL*fi5 +1LL*fi6+1LL*fi7) % mod;
                int new_fi6 = (2LL * fi0 + 1LL * fi1+ 2LL*fi2+ 1LL*fi3+ 0LL*fi4 +1LL*fi5 +2LL*fi6+1LL*fi7) % mod;
                int new_fi7 = (2LL * fi0 + 1LL * fi1+ 2LL*fi2+ 1LL*fi3+ 1LL*fi4 +1LL*fi5 +1LL*fi6+2LL*fi7) % mod;
                fi0 = new_fi0;
                fi1 = new_fi1;
                fi2 = new_fi2;
                fi3 = new_fi3;
                fi4 = new_fi4;
                fi5 = new_fi5;
                fi6 = new_fi6;
                fi7 = new_fi7;
            }
            return ((long long)fi0 + fi1+ fi2+ fi3+ fi4 + fi5+ fi6+ fi7) % mod;
        }
    }
};

综上所述

1. 对于m = 1，可分为1种情况
2. 对于m > 1，可分为2^(m-2)种情况

故时间复杂度为O((2^m)*n)

前言

如果只有红绿两种颜色，可以把这两种颜色分别用 $0$ 和 $1$ 表示，用一个长为 $m$ 的二进制数表示一行的颜色。

例如 $m=5$，二进制数 $01010_{(2)}$ 表示红绿红绿红。

本题有红绿蓝三种颜色，可以分别用 $0,1,2$ 表示，用一个长为 $m$ 的三进制数表示一行的颜色。

例如 $m=5$，三进制数 $01202_{(3)}$ 表示红绿蓝红蓝。

注：本题不区分左右，三进制数从高到低读还是从低到高读都可以。

思路

首先预处理所有合法的（没有相邻相同颜色的）三进制数，记在数组 $\textit{valid}$ 中。

然后对于每个 $\textit{valid}[i]$，预处理它的下一列颜色，要求左右相邻颜色不同。把 $\textit{valid}$ 的下标记在数组 $\textit{nxt}[i]$ 中。

预处理这些数据之后，就可以 DP 了。

对于 $m\times n$ 的网格，如果最后一列填的是三进制数 $\textit{valid}[j]$，那么问题为：对于 $m\times (n-1)$ 的网格，最后一列填的是三进制数 $\textit{valid}[j]$ 的情况下的涂色方案数。

继续，如果倒数第二列填的是三进制数 $\textit{valid}[k]$，那么接下来要解决的问题为：对于 $m\times (n-2)$ 的网格，右边一列填的是三进制数 $\textit{valid}[k]$ 的情况下的涂色方案数。

所以定义 $\textit{dfs}(i,j)$ 表示对于 $m\times i$ 的网格，右边第 $i+1$ 列填的是三进制数 $\textit{valid}[j]$ 的情况下的涂色方案数。

枚举第 $i$ 列填颜色 $\textit{valid}[k]$（其中 $k$ 是 $\textit{nxt}[j]$ 中的元素），问题变成对于 $m\times (i-1)$ 的网格，右边第 $i$ 列填的是三进制数 $\textit{valid}[k]$ 的情况下的涂色方案数。

累加得

$$
\textit{dfs}(i,j) = \sum_{k} \textit{dfs}(i-1,k)
$$

递归边界：$\textit{dfs}(0,j) = 1$，表示找到了一个合法涂色方案。

递归入口：$\displaystyle\sum\limits_{j} \textit{dfs}(n-1, j)$。第 $n$ 列填颜色 $\textit{valid}[j]$。

细节

三进制数最大为 $22\ldots 2_{(3)} = 3^m-1$。枚举 $[0,3^m-1]$ 中的三进制数，怎么判断一个三进制数是否合法？

我们需要取出三进制数中的每一位。

回想一下十进制数 $12345$ 怎么取出百位的 $3$：$12345$ 除以 $100$ 下取整，得到 $123$，再模 $10$，得到 $3$。

所以对于三进制数，可以除以 $3^i$ 下取整，再模 $3$。

为什么可以在 DP 的计算过程中取模？可以看 模运算的世界：当加减乘除遇上取模。

写法一：记忆化搜索

class Solution:
    def colorTheGrid(self, m: int, n: int) -> int:
        pow3 = [3 ** i for i in range(m)]
        valid = []
        for color in range(3 ** m):
            for i in range(1, m):
                if color // pow3[i] % 3 == color // pow3[i - 1] % 3:  # 相邻颜色相同
                    break
            else:  # 没有中途 break，合法
                valid.append(color)

        nv = len(valid)
        nxt = [[] for _ in range(nv)]
        for i, color1 in enumerate(valid):
            for j, color2 in enumerate(valid):
                for p3 in pow3:
                    if color1 // p3 % 3 == color2 // p3 % 3:  # 相邻颜色相同
                        break
                else:  # 没有中途 break，合法
                    nxt[i].append(j)

        MOD = 1_000_000_007
        @cache  # 缓存装饰器，避免重复计算 dfs（一行代码实现记忆化）
        def dfs(i: int, j: int) -> int:
            if i == 0:
                return 1  # 找到了一个合法涂色方案
            return sum(dfs(i - 1, k) for k in nxt[j]) % MOD
        return sum(dfs(n - 1, j) for j in range(nv)) % MOD

class Solution {
    private static final int MOD = 1_000_000_007;

    public int colorTheGrid(int m, int n) {
        int[] pow3 = new int[m];
        pow3[0] = 1;
        for (int i = 1; i < m; i++) {
            pow3[i] = pow3[i - 1] * 3;
        }

        List<Integer> valid = new ArrayList<>();
        next:
        for (int color = 0; color < pow3[m - 1] * 3; color++) {
            for (int i = 1; i < m; i++) {
                if (color / pow3[i] % 3 == color / pow3[i - 1] % 3) { // 相邻颜色相同
                    continue next;
                }
            }
            valid.add(color);
        }

        int nv = valid.size();
        List<Integer>[] nxt = new ArrayList[nv];
        Arrays.setAll(nxt, i -> new ArrayList<>());
        for (int i = 0; i < nv; i++) {
            next2:
            for (int j = 0; j < nv; j++) {
                for (int p3 : pow3)
                    if (valid.get(i) / p3 % 3 == valid.get(j) / p3 % 3) { // 相邻颜色相同
                        continue next2;
                    }
                nxt[i].add(j);
            }
        }

        int[][] memo = new int[n][nv];
        for (int[] row : memo) {
            Arrays.fill(row, -1);
        }

        long ans = 0;
        for (int j = 0; j < nv; j++) {
            ans += dfs(n - 1, j, nxt, memo);
        }
        return (int) (ans % MOD);
    }

    private int dfs(int i, int j, List<Integer>[] nxt, int[][] memo) {
        if (i == 0) {
            return 1; // 找到了一个合法涂色方案
        }
        if (memo[i][j] != -1) { // 之前计算过
            return memo[i][j];
        }
        long res = 0;
        for (int k : nxt[j]) {
            res += dfs(i - 1, k, nxt, memo);
        }
        return memo[i][j] = (int) (res % MOD); // 记忆化
    }
}

class Solution {
    const int MOD = 1'000'000'007;
public:
    int colorTheGrid(int m, int n) {
        vector<int> pow3(m);
        pow3[0] = 1;
        for (int i = 1; i < m; i++) {
            pow3[i] = pow3[i - 1] * 3;
        }

        vector<int> valid;
        for (int color = 0; color < pow3[m - 1] * 3; color++) {
            bool ok = true;
            for (int i = 1; i < m; i++) {
                if (color / pow3[i] % 3 == color / pow3[i - 1] % 3) { // 相邻颜色相同
                    ok = false;
                    break;
                }
            }
            if (ok) {
                valid.push_back(color);
            }
        }

        int nv = valid.size();
        vector<vector<int>> nxt(nv);
        for (int i = 0; i < nv; i++) {
            for (int j = 0; j < nv; j++) {
                bool ok = true;
                for (int k = 0; k < m; k++) {
                    if (valid[i] / pow3[k] % 3 == valid[j] / pow3[k] % 3) { // 相邻颜色相同
                        ok = false;
                        break;
                    }
                }
                if (ok) {
                    nxt[i].push_back(j);
                }
            }
        }

        vector memo(n, vector<int>(nv, -1));
        auto dfs = [&](this auto&& dfs, int i, int j) -> int {
            if (i == 0) {
                return 1; // 找到了一个合法涂色方案
            }
            int& res = memo[i][j]; // 注意这里是引用
            if (res != -1) { // 之前计算过
                return res;
            }
            res = 0;
            for (int k : nxt[j]) {
                res = (res + dfs(i - 1, k)) % MOD;
            }
            return res;
        };

        long long ans = 0;
        for (int j = 0; j < nv; j++) {
            ans += dfs(n - 1, j);
        }
        return ans % MOD;
    }
};

func colorTheGrid(m, n int) int {
const mod = 1_000_000_007
pow3 := make([]int, m)
pow3[0] = 1
for i := 1; i < m; i++ {
pow3[i] = pow3[i-1] * 3
}

valid := []int{}
next:
for color := range pow3[m-1] * 3 {
for i := range m - 1 {
if color/pow3[i+1]%3 == color/pow3[i]%3 { // 相邻颜色相同
continue next
}
}
valid = append(valid, color)
}

nv := len(valid)
nxt := make([][]int, nv)
for i, color1 := range valid {
next2:
for j, color2 := range valid {
for _, p3 := range pow3 {
if color1/p3%3 == color2/p3%3 { // 相邻颜色相同
continue next2
}
}
nxt[i] = append(nxt[i], j)
}
}

memo := make([][]int, n)
for i := range memo {
memo[i] = make([]int, nv)
for j := range memo[i] {
memo[i][j] = -1
}
}
var dfs func(int, int) int
dfs = func(i, j int) (res int) {
if i == 0 {
return 1 // 找到了一个合法涂色方案
}
p := &memo[i][j]
if *p != -1 { // 之前计算过
return *p
}
defer func() { *p = res }() // 记忆化
for _, k := range nxt[j] {
res += dfs(i-1, k)
}
return res % mod
}

ans := 0
for j := range nv {
ans += dfs(n-1, j)
}
return ans % mod
}

复杂度分析

有多少个状态？$\textit{valid}$ 有多长？

对于一列长为 $m$ 的涂色方案，第一个颜色有 $3$ 种，其余颜色不能与上一个颜色相同，所以都是 $2$ 种。所以 $\textit{valid}$ 的长度为

$$
3\cdot 2^{m-1}
$$

所以状态个数为 $i$ 的个数 $\mathcal{O}(n)$ 乘以 $j$ 的个数 $\mathcal{O}(2^m)$，一共有 $\mathcal{O}(n2^m)$ 个状态。

• 时间复杂度：$\mathcal{O}(n4^m)$。由于每个状态只会计算一次，动态规划的时间复杂度 $=$ 状态个数 $\times$ 单个状态的计算时间。本题状态个数等于 $\mathcal{O}(n2^m)$，单个状态的计算时间为 $\mathcal{O}(2^m)$，所以总的时间复杂度为 $\mathcal{O}(n4^m)$。
• 空间复杂度：$\mathcal{O}(4^m + n2^m)$。其中 $\mathcal{O}(4^m)$ 是 $\textit{nxt}$ 需要的空间，$\mathcal{O}(n2^m)$ 是记忆化搜索需要的空间。

写法二：递推

把记忆化搜索 1:1 翻译成递推，原理见 动态规划入门：从记忆化搜索到递推【基础算法精讲 17】。

class Solution:
    def colorTheGrid(self, m: int, n: int) -> int:
        pow3 = [3 ** i for i in range(m)]
        valid = []
        for color in range(3 ** m):
            for i in range(1, m):
                if color // pow3[i] % 3 == color // pow3[i - 1] % 3:  # 相邻颜色相同
                    break
            else:  # 没有中途 break，合法
                valid.append(color)

        nv = len(valid)
        nxt = [[] for _ in range(nv)]
        for i, color1 in enumerate(valid):
            for j, color2 in enumerate(valid):
                for p3 in pow3:
                    if color1 // p3 % 3 == color2 // p3 % 3:  # 相邻颜色相同
                        break
                else:  # 没有中途 break，合法
                    nxt[i].append(j)

        MOD = 1_000_000_007
        f = [[0] * nv for _ in range(n)]
        f[0] = [1] * nv  # dfs 的递归边界就是 DP 数组的初始值
        for i in range(1, n):
            for j in range(nv):
                f[i][j] = sum(f[i - 1][k] for k in nxt[j]) % MOD
        return sum(f[-1]) % MOD  # 递归入口就是答案

class Solution {
    private static final int MOD = 1_000_000_007;

    public int colorTheGrid(int m, int n) {
        int[] pow3 = new int[m];
        pow3[0] = 1;
        for (int i = 1; i < m; i++) {
            pow3[i] = pow3[i - 1] * 3;
        }

        List<Integer> valid = new ArrayList<>();
        next:
        for (int color = 0; color < pow3[m - 1] * 3; color++) {
            for (int i = 1; i < m; i++) {
                if (color / pow3[i] % 3 == color / pow3[i - 1] % 3) { // 相邻颜色相同
                    continue next;
                }
            }
            valid.add(color);
        }

        int nv = valid.size();
        List<Integer>[] nxt = new ArrayList[nv];
        Arrays.setAll(nxt, i -> new ArrayList<>());
        for (int i = 0; i < nv; i++) {
            next2:
            for (int j = 0; j < nv; j++) {
                for (int p3 : pow3)
                    if (valid.get(i) / p3 % 3 == valid.get(j) / p3 % 3) { // 相邻颜色相同
                        continue next2;
                    }
                nxt[i].add(j);
            }
        }

        int[][] f = new int[n][nv];
        Arrays.fill(f[0], 1);
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < nv; j++) {
                for (int k : nxt[j]) {
                    f[i][j] = (f[i][j] + f[i - 1][k]) % MOD;
                }
            }
        }

        long ans = 0;
        for (int j = 0; j < nv; j++) {
            ans += f[n - 1][j];
        }
        return (int) (ans % MOD);
    }
}

class Solution {
    const int MOD = 1'000'000'007;
public:
    int colorTheGrid(int m, int n) {
        vector<int> pow3(m);
        pow3[0] = 1;
        for (int i = 1; i < m; i++) {
            pow3[i] = pow3[i - 1] * 3;
        }

        vector<int> valid;
        for (int color = 0; color < pow3[m - 1] * 3; color++) {
            bool ok = true;
            for (int i = 1; i < m; i++) {
                if (color / pow3[i] % 3 == color / pow3[i - 1] % 3) { // 相邻颜色相同
                    ok = false;
                    break;
                }
            }
            if (ok) {
                valid.push_back(color);
            }
        }

        int nv = valid.size();
        vector<vector<int>> nxt(nv);
        for (int i = 0; i < nv; i++) {
            for (int j = 0; j < nv; j++) {
                bool ok = true;
                for (int k = 0; k < m; k++) {
                    if (valid[i] / pow3[k] % 3 == valid[j] / pow3[k] % 3) { // 相邻颜色相同
                        ok = false;
                        break;
                    }
                }
                if (ok) {
                    nxt[i].push_back(j);
                }
            }
        }

        vector f(n, vector<int>(nv));
        ranges::fill(f[0], 1);
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < nv; j++) {
                for (int k : nxt[j]) {
                    f[i][j] = (f[i][j] + f[i - 1][k]) % MOD;
                }
            }
        }

        long long ans = 0;
        for (int j = 0; j < nv; j++) {
            ans += f[n - 1][j];
        }
        return ans % MOD;
    }
};

func colorTheGrid(m, n int) int {
const mod = 1_000_000_007
pow3 := make([]int, m)
pow3[0] = 1
for i := 1; i < m; i++ {
pow3[i] = pow3[i-1] * 3
}

valid := []int{}
next:
for color := range pow3[m-1] * 3 {
for i := range m - 1 {
if color/pow3[i+1]%3 == color/pow3[i]%3 { // 相邻颜色相同
continue next
}
}
valid = append(valid, color)
}

nv := len(valid)
nxt := make([][]int, nv)
for i, color1 := range valid {
next2:
for j, color2 := range valid {
for _, p3 := range pow3 {
if color1/p3%3 == color2/p3%3 { // 相邻颜色相同
continue next2
}
}
nxt[i] = append(nxt[i], j)
}
}

f := make([][]int, n)
for i := range f {
f[i] = make([]int, nv)
}
for j := range f[0] {
f[0][j] = 1
}
for i := 1; i < n; i++ {
for j := range f[i] {
for _, k := range nxt[j] {
f[i][j] += f[i-1][k]
}
f[i][j] %= mod
}
}

ans := 0
for _, fv := range f[n-1] {
ans += fv
}
return ans % mod
}

复杂度分析

• 时间复杂度：$\mathcal{O}(n4^m)$。理由同写法一。
• 空间复杂度：$\mathcal{O}(4^m + n2^m)$。注：用滚动数组可以优化至 $\mathcal{O}(4^m)$。

附：矩阵快速幂

$n=10^{18}$ 也可以通过。

原理讲解

import numpy as np

MOD = 1_000_000_007

# a^n @ f0
def pow(a: np.ndarray, n: int, f0: np.ndarray) -> np.ndarray:
    res = f0
    while n:
        if n & 1:
            res = a @ res % MOD
        a = a @ a % MOD
        n >>= 1
    return res

class Solution:
    def colorTheGrid(self, m: int, n: int) -> int:
        pow3 = [3 ** i for i in range(m)]
        valid = []
        for color in range(3 ** m):
            for i in range(1, m):
                if color // pow3[i] % 3 == color // pow3[i - 1] % 3:  # 相邻颜色相同
                    break
            else:  # 没有中途 break，合法
                valid.append(color)

        nv = len(valid)
        m = np.zeros((nv, nv), dtype=object)
        for i, color1 in enumerate(valid):
            for j, color2 in enumerate(valid):
                for p3 in pow3:
                    if color1 // p3 % 3 == color2 // p3 % 3:  # 相邻颜色相同
                        break
                else:  # 没有中途 break，合法
                    m[i, j] = 1

        f0 = np.ones((nv,), dtype=object)
        res = pow(m, n - 1, f0)
        return np.sum(res) % MOD

import numpy as np

MOD = 1_000_000_007

class Solution:
    def colorTheGrid(self, m: int, n: int) -> int:
        pow3 = [3 ** i for i in range(m)]
        valid = []
        for color in range(3 ** m):
            for i in range(1, m):
                if color // pow3[i] % 3 == color // pow3[i - 1] % 3:  # 相邻颜色相同
                    break
            else:  # 没有中途 break，合法
                valid.append(color)

        nv = len(valid)
        m = np.zeros((nv, nv), dtype=object)
        for i, color1 in enumerate(valid):
            for j, color2 in enumerate(valid):
                for p3 in pow3:
                    if color1 // p3 % 3 == color2 // p3 % 3:  # 相邻颜色相同
                        break
                else:  # 没有中途 break，合法
                    m[i, j] = 1

        f0 = np.ones((nv,), dtype=object)
        res = np.linalg.matrix_power(m, n - 1) @ f0
        return np.sum(res) % MOD

复杂度分析

• 时间复杂度：$\mathcal{O}(2^{m\omega} \log n)$。矩阵长宽均为 $\mathcal{O}(2^m)$，计算一次矩阵乘法需要 $\mathcal{O}((2^m)^\omega)$ 的时间，其中 $\omega\le 3$。
• 空间复杂度：$\mathcal{O}(4^m)$。

双倍经验

1411. 给 N x 3 网格图涂色的方案数

分类题单

如何科学刷题？

1. 滑动窗口与双指针（定长/不定长/单序列/双序列/三指针/分组循环）
2. 二分算法（二分答案/最小化最大值/最大化最小值/第K小）
3. 单调栈（基础/矩形面积/贡献法/最小字典序）
4. 网格图（DFS/BFS/综合应用）
5. 位运算（基础/性质/拆位/试填/恒等式/思维）
6. 图论算法（DFS/BFS/拓扑排序/基环树/最短路/最小生成树/网络流）
7. 动态规划（入门/背包/划分/状态机/区间/状压/数位/数据结构优化/树形/博弈/概率期望）
8. 常用数据结构（前缀和/差分/栈/队列/堆/字典树/并查集/树状数组/线段树）
9. 数学算法（数论/组合/概率期望/博弈/计算几何/随机算法）
10. 贪心与思维（基本贪心策略/反悔/区间/字典序/数学/思维/脑筋急转弯/构造）
11. 链表、二叉树与回溯（前后指针/快慢指针/DFS/BFS/直径/LCA/一般树）
12. 字符串（KMP/Z函数/Manacher/字符串哈希/AC自动机/后缀数组/子序列自动机）

我的题解精选（已分类）

欢迎关注 B站@灵茶山艾府

## Task > Write a shader that splits the screen

一、核心设计理念差异 1. 数据流向的明确性 ‌props/emit‌ 遵循严格的单向数据流： ‌provide/inject‌ 则是隐式的跨层级通信： 二、必须使用 props/emit 的场景 1

一、provide/inject 基础原理 1. 基本用法 2. 响应式数据传递 二、provide/inject 的优势 1. 组件树穿透能力 ‌场景‌：多层嵌套组件共享配置 2. 减少 props

不让用 $\texttt{sort}$ 吗？有意思……

技巧：O(1) 插入元素

假设现在有一个有序数组 $a=[0,0,1,1,2,2]$。在 $a$ 中插入一个 $0$，同时保证 $a$ 是有序的，你会怎么做？

最暴力的想法是，把 $0$ 插在数组的最左边，原来的元素全体右移一位，得到 $[0,0,0,1,1,2,2]$。这样做是 $\mathcal{O}(n)$ 的。

实际上，我们可以「狸猫换太子」：不是插入元素，而是修改元素！

对比一下插入前后：

• 插入前 $[0,0,1,1,2,2]$。
• 插入后 $[0,0,0,1,1,2,2]$。

竖着看，其实只有 $3$ 个位置变了：

1. 原来的 $a[2]$ 变成 $0$。
2. 原来的 $a[4]$ 变成 $1$。
3. 末尾新增一个 $2$，相当于 $a[6]=2$。

怎么知道要修改的位置（下标）？

1. 维护 $0$ 的个数，即为改成 $0$ 的位置，记作 $p_0$。上例中 $p_0=2$。把 $a[p_0]$ 改成 $0$。
2. 维护 $0$ 和 $1$ 的个数，即为改成 $1$ 的位置，记作 $p_1$。上例中 $p_1=4$。把 $a[p_1]$ 改成 $1$。
3. 末尾新增的位置记作 $i$，把 $a[i]$ 改成 $2$。

细节

如果 $a$ 中没有 $2$ 呢？上面第三步就错了。

比如现在 $a=[1]$，插入一个 $0$，变成 $[0,1]$。

如果按照上面三步走，最后把 $a[1]$ 改成 $2$，得到的是 $[0,2]$，这就错了。

要写很多 $\texttt{if-else}$，特判这些特殊情况吗？

不需要，我们可以倒过来算：先把 $a[1]$ 改成 $2$，再把 $a[1]$ 改成 $1$（覆盖），最后 $a[0]$ 改成 $0$，得到 $[0,1]$。这种「覆盖」等价于「没有 $2$ 的时候不改成 $2$」。

如果插入的是 $1$ 呢？

跳过「把 $a[p_0]$ 改成 $0$」这一步。

如果插入的是 $2$ 呢？

只需要把 $a[i]$ 改成 $2$ 即可。

本题思路

对 $\textit{nums}$ 执行插入排序，也就是对 $i=0,1,2,\ldots,n-1$ 依次执行如下过程：

• 现在前缀 $\textit{nums}[0]$ 到 $\textit{nums}[i-1]$ 是有序的，我们把 $\textit{nums}[i]$ 插入到这个有序前缀中，从而把前缀 $\textit{nums}[0]$ 到 $\textit{nums}[i]$ 变成有序的。
• 算法执行完后，$\textit{nums}$ 就是一个有序数组了。

class Solution:
    def sortColors(self, nums: List[int]) -> None:
        p0 = p1 = 0
        for i, x in enumerate(nums):
            nums[i] = 2
            if x <= 1:
                nums[p1] = 1
                p1 += 1
            if x == 0:
                nums[p0] = 0
                p0 += 1

class Solution {
    public void sortColors(int[] nums) {
        int p0 = 0;
        int p1 = 0;
        for (int i = 0; i < nums.length; i++) {
            int x = nums[i];
            nums[i] = 2;
            if (x <= 1) {
                nums[p1++] = 1;
            }
            if (x == 0) {
                nums[p0++] = 0;
            }
        }
    }
}

class Solution {
public:
    void sortColors(vector<int>& nums) {
        int p0 = 0, p1 = 0;
        for (int i = 0; i < nums.size(); i++) {
            int x = nums[i];
            nums[i] = 2;
            if (x <= 1) {
                nums[p1++] = 1;
            }
            if (x == 0) {
                nums[p0++] = 0;
            }
        }
    }
};

void sortColors(int* nums, int numsSize) {
    int p0 = 0, p1 = 0;
    for (int i = 0; i < numsSize; i++) {
        int x = nums[i];
        nums[i] = 2;
        if (x <= 1) {
            nums[p1++] = 1;
        }
        if (x == 0) {
            nums[p0++] = 0;
        }
    }
}

func sortColors(nums []int) {
    p0, p1 := 0, 0
    for i, x := range nums {
        nums[i] = 2
        if x <= 1 {
            nums[p1] = 1
            p1++
        }
        if x == 0 {
            nums[p0] = 0
            p0++
        }
    }
}

var sortColors = function(nums) {
    let p0 = 0, p1 = 0;
    for (let i = 0; i < nums.length; i++) {
        const x = nums[i];
        nums[i] = 2;
        if (x <= 1) {
            nums[p1++] = 1;
        }
        if (x === 0) {
            nums[p0++] = 0;
        }
    }
};

impl Solution {
    pub fn sort_colors(nums: &mut Vec<i32>) {
        let mut p0 = 0;
        let mut p1 = 0;
        for i in 0..nums.len() {
            let x = nums[i];
            nums[i] = 2;
            if x <= 1 {
                nums[p1] = 1;
                p1 += 1;
            }
            if x == 0 {
                nums[p0] = 0;
                p0 += 1;
            }
        }
    }
}

复杂度分析

• 时间复杂度：$\mathcal{O}(n)$，其中 $n$ 是 $\textit{nums}$ 的长度。
• 空间复杂度：$\mathcal{O}(1)$。

分类题单

如何科学刷题？

1. 滑动窗口与双指针（定长/不定长/单序列/双序列/三指针/分组循环）
2. 二分算法（二分答案/最小化最大值/最大化最小值/第K小）
3. 单调栈（基础/矩形面积/贡献法/最小字典序）
4. 网格图（DFS/BFS/综合应用）
5. 位运算（基础/性质/拆位/试填/恒等式/思维）
6. 图论算法（DFS/BFS/拓扑排序/基环树/最短路/最小生成树/网络流）
7. 动态规划（入门/背包/划分/状态机/区间/状压/数位/数据结构优化/树形/博弈/概率期望）
8. 常用数据结构（前缀和/差分/栈/队列/堆/字典树/并查集/树状数组/线段树）
9. 数学算法（数论/组合/概率期望/博弈/计算几何/随机算法）
10. 贪心与思维（基本贪心策略/反悔/区间/字典序/数学/思维/脑筋急转弯/构造）
11. 链表、二叉树与回溯（前后指针/快慢指针/DFS/BFS/直径/LCA/一般树）
12. 字符串（KMP/Z函数/Manacher/字符串哈希/AC自动机/后缀数组/子序列自动机）

我的题解精选（已分类）

欢迎关注 B站@灵茶山艾府

在前端开发的面试中，HTML 是最基础也是最重要的知识点之一。 尤其是大厂的前端面试，往往会围绕 HTML 的核心概念和语义化标签进行深入考察。 本文将带你梳理一些常见的 HTML 面试问题

编者注： Git worktree 是 Git 提供的一个强大功能，它允许你在同一个仓库中同时处理多个分支，而不会干扰当前的工作环境。1) 通过创建新的 worktree，你可以并行处理多个任务，比如

axios还用封装？ 不着急，咱先聊聊为什么要封装axios，或者说我们的封装目标是什么。axios还用封装？ 不着急，咱先聊聊为什么要封装axios，或者说我们的封装目标是什么。

这篇文章主要介绍cesium怎么在断网条件下进行开发和调试，具体内容包括地图与地形的下载，切片和部署。最后会在断网条件下进行初始cesium。

npm link到本地测试时，遇到了报错：Warning: Invalid hook call，经过多轮排查，最终发现到React多实例冲突与pnpm对peerDependencies的隐式安装是关键

在withCredentials场景下，Koa2 通过动态源校验、中间件封装及安全策略配置，可有效解决跨域凭证携带问题。核心原则是：严格限制允许的源，避免滥用通配符，始终遵循最小权限原则。通过结合环境

在 React 开发中，闭包陷阱是一个常见且令人头疼的问题。当我们在 `useEffect`、`us

目录 获取DOM节点 通过ID查找节点 通过标签名查找节点 通过类名查找节点 通过CSS选择器查找单个节点 通过CSS选择器查找所有节点 通过关系获取节点 获取下一个兄弟节点 获取上一个兄弟节点

本文详细介绍了多种前端开发中常见的功能实现，涵盖了交互组件、表单处理、数据存储、动态内容处理、实用工具、用户体验优化和视觉效果等多个方面。具体内容包括轮播图、Tab切换、模态框、下拉菜单、手风琴效果、

本文主要介绍了异步编程、跨域问题和懒加载技术。在异步编程部分，详细解释了其基本概念、事件循环机制、JavaScript中的常见实现方式（如回调函数、Promise、async/await）以及最佳实践

MCP（Model Context Protocol）是一种用于大语言模型与外部工具交互的协议框架。它允许大语言模型能够调用各种外部工具来扩展其能力边界，如访问文件系统、搜索引擎、数据库等。