leetcode 1411(递推)

1411: 给N*3 网格图涂色的方案数

我们把满足要求的 type 都写出来，一共有 12 种：010, 012, 020, 021, 101, 102, 120, 121, 201, 202, 210, 212。

我们可以把它们分成两类：

• ABC 类：三个颜色互不相同，一共有 6 种：012, 021, 102, 120, 201, 210；
• ABA 类：左右两侧的颜色相同，也有 6 种：010, 020, 101, 121, 202, 212。

class Solution { public: int numOfWays(int n) { constexpr int MOD=1'000'000'007; int fi0=6,fi1=6; //n=1时的两种状态数:ABC类 or ABA类 for(int i=2;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 (fi0+fi1)%MOD; } };