1411. 给 N x 3 網格圖塗色的方案數

小貼士：此題可以用矩陣快速冪，但我自己也不知道具體該怎麼做，哈哈。

思路

一共有 3 種顏色可以選，題目要求一共有多少種填色方式，滿足「相鄰不同色」的條件，填滿n x 3的格子。
題目已經給出n = 1的情況，一共有 12 種方式可以填。
我們可以將情況分為兩種，ABA型與ABC型，

• ABA型，代表用了 2 種顏色，必定有一個顏色用了兩次。
• ABC型，代表用了 3 種顏色，每個顏色各用一遍。

而兩種方案的下一列，要求跟上一列不相鄰，一共有幾種方案可以選？

程式碼

class Solution {
public:
    int numOfWays(int n) {
        const int MOD = 1e9 + 7;
        long long aba = 6, abc = 6;
        for(int i = 1; i < n; ++i) {
            long long next_aba = (aba * 3 + abc * 2) % MOD;
            long long next_abc = (aba * 2 + abc * 2) % MOD;
            aba = next_aba;
            abc = next_abc;
        }
        return (aba + abc) % MOD;
    }
};

複雜度分析

• 時間複雜度：$O(n)$
• 空間複雜度：$O(1)$