LeetCode 1411. 给 N x 3 网格图涂色的方案数(计数DP、矩阵加速递推)

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

暴力计数DP 考虑$n$行的方案数，向$n+1$行递推的时候，只需要考虑上一行的状态即可。 合法的就转移。 时间复杂度:$O(27\ast 27\ast N)$ class Solution { public: typedef long long ll; int mod = 1e9+7; int numOfWays(int N) { ll f[5010][3][3][3] = {0}; for(int i=0;i<3;i++) for(int j=0;j<3;j++) for(int k=0;k<3;k++) f[1][i][j][k] = check(-1,-1,-1,i,j,k); for(int n=1;n<N;n++){ for(int i1=0;i1<3;i1++){ for(int j1=0;j1<3;j1++){ for(int k1=0;k1<3;k1++){ for(int i2=0;i2<3;i2++){ for(int j2=0;j2<3;j2++){ for(int k2=0;k2<3;k2++){ if(!check(i1,j1,k1,i2,j2,k2)) continue; f[n+1][i2][j2][k2] = (f[n+1][i2][j2][k2]+f[n][i1][j1][k1])%mod; } } } } } } } ll ans = 0; for(int i=0;i<3;i++) for(int j=0;j<3;j++) for(int k=0;k<3;k++) ans = (ans+f[N][i][j][k])%mod; return ans; } bool check(int i1,int j1,int k1,int i2,int j2,int k2){ return i1!=i2 && j1!=j2 && k1!=k2 && j2!=i2 && k2!=j2; } }; 递推关系优化、矩阵加速递推 仔细分析一下，上一行的状态，无非两类：$ABA$型、$ABC$型， 于是向下一行转移的时候，只需要考虑下一行的ABA型如何来，ABC型如何来即可。 简单分析一下， 得到如下递推式。

$$a_n=2\ast a_{n-1}+2\ast b_{n-1}$$ $$b_n=2\ast a_{n-1}+3\ast b_{n-1}$$

利用矩阵加速递推的思想，可以写成。 $[a_n,b_n]=[a_{n-1},b_{n-1}]\ast \left(\begin{array}{cc}2& 2\\ 2& 3\end{array}\right)$

于是利用矩阵的快速幂，可以使得时间复杂度降到$log(n)$

当然最后的方案数是$a_n+b_n$

class Solution { public: typedef long long LL; int mod = 1e9+7; int numOfWays(int n) { LL A[2][2] = {2,2,2,3}, B[2][2] = {1,0,0,1}; LL f[2] = {6,6}; quick_mul(A,n-1,B); LL ans = 0; for(int i=0;i<2;i++) ans = (ans+f[i]*B[0][i]%mod+f[i]*B[1][i])%mod; return ans; } void matrix_mul(LL A[][2],LL B[][2]){ LL C[2][2] = {0,0,0,0}; for(int i=0;i<2;i++){ for(int j=0;j<2;j++){ for(int k=0;k<2;k++){ C[i][j] = (C[i][j]+A[i][k]*B[k][j]%mod)%mod; } } } memcpy(B,C,sizeof C); } void quick_mul(LL A[][2],int n,LL B[][2]){ while(n){ if(n&1) matrix_mul(A,B); matrix_mul(A,A); n >>= 1; } } };