P.S. 之前挂掉的SCNUCPC2020官方题册和题解已补档，请前往 这里 查看

下面介绍组合数学和DP两种解法

事实上这是我大约一年前写的补题笔记,最近在复习DP便拿这道题题解出来分享一下

组合数学

其实就是官方题解，下面给出比较详细的推导

对于每列(每3个)，三色互不相同共有6种情况 (A_3^3 )，只有两种颜色共有6种情况 (先选后排 C_3^2C_3^1 ) ，

显而易见n=1(只有一列)时,答案为6+6=12

n>1时,每一列仍只有6种三色和6种二色情况。

在上一列中：

对于每一种三色，只可能推出四种下一列，且必然是二种三色和二种二色：

以RYG为例，它的下一列仅可能是GRY,YRG,YGY,YRY,前两个为三色，后两个为二色。

另外五个三色GYR,YRG,GRY,YGR,RGY与此相似。

对于每一种二色，只可能推出五种下一列，且必然是二种三色和三种二色：

以RYR为例，它的下一列仅可能是YRG,GRY,YRY,GRG,YGY，前两个为三色，后三个为二色。

另外五种二色RGR,GRG,GYG,YRY,YGY与此相似。

因此，第二列可以由第一列推出，第一列每个颜色都只有一种情况，

根据上面分析，

上一列的每个三色都可以推出下一列的两种三色，两种二色，共4种

上一列的每个二色都可以推出下一列的两种三色，三种二色，共5种

所以n=2的情况数为 6*4 (三色) + 6*5(二色)

且第二列每种三色情况数为2+2(三色推出+二色推出)

每种二色情况数为2+3(三色推出+二色推出)

即n=2情况数为6*(2+2) + 6*(2+3)

设c3表示最后时每种三色情况数，c2表示最后时每种二色情况数，有递推关系：

c3 = 2*c3 + 2*c2

c2 = 2*c3 + 3*c2

answer = 6*c3 + 6*c2

初始状态(n=1)时,c3=c2=1

也就是说，c2 表示当前最后为某种二色情况时，前面的列可以有多少种合理情况；c3 表示当前最后为某种二色情况时，前面的列可以有多少种合理情况

#include <bits/stdc++.h>
#define MOD 1000000007
typedef long long ll;
ll c3=1,c2=1,ans,n,temp3,temp2;
signed main()
{
    scanf("%lld",&n);
    for(;n>1;n--)
    {
        temp3=2*c3+2*c2;
        temp3%=MOD;
        temp2=2*c3+3*c2;
        temp2%=MOD;
        c3=temp3;
        c2=temp2;
    }
    printf("%lld", (6*(c3+c2)) %MOD );
    return 0;
}

DP

这题跟某知名题目We like AGC(也是同年SCNUCPC预选赛的一道题)很像

设dp[h][i][j][k]表示前h列，第h列从上到下颜色分别为i,j,k的情况数，直接暴力可得：

#include <bits/stdc++.h>
#define maxn 5005
using namespace std;
typedef long long ll;

ll dp[maxn][3][3][3];

const int MOD = 1e9 + 7;
int n;
int main()
{
    cin >> n;

    for (int i = 0; i < 3; i++)
        for (int j = 0; j < 3; j++)
            for (int k = 0; k < 3; k++)
                if (i != j && j != k)
                    dp[1][i][j][k] = 1;

    for (int p = 2; p <= n; p++)
        for (int i = 0; i < 3; i++)//i,j,k是当前列
            for (int j = 0; j < 3; j++)
                for (int k = 0; k < 3; k++)
                    for (int a = 0; a < 3; a++)//a,b,c是上一列
                        for (int b = 0; b < 3; b++)
                            for (int c = 0; c < 3; c++)
                                if (i != j && j != k && a != b && b != c && i != a && j != b && k != c)
                                    dp[p][i][j][k] = (dp[p][i][j][k] + dp[p - 1][a][b][c]) % 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++)
                if (i != j && j != k)
                    ans = (ans + dp[n][i][j][k]) % MOD;

    cout << ans << endl;

    return 0;
}

当然，用压缩数组还可以把 h 这一维压成长度为 2 ，但是这题没这个必要

私以为该解法比官方解法更容易懂 (暴力DP比较好理解) //逃

//吐槽: 为什么这里讨论区的公式渲染比题面的公式渲染难看这么多(