思路：先统计所有的含red子串的可能（可连续可不连续)，然后统计含连续red的可能，前者减去后者。前者设计4个状态，对应ABCD，分别是：A没出现r，B前面仅出现r，C，前面以此出现re。D依次出现redA【i】【j】的含义：i取012代表分别red结尾，j代表序列长度-1，A表示这样的取值所处状态，注意有一些矩阵由于违反规定一直是0，可以不更新。ABCD中有若干转移方程，注意特殊情况，可以从上级转移到下级，否则，只能同级转换。代码未取模。#include <bits/stdc++.h>#include <algorithm>using namespace std;class Solution{public:    /**     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可     *     *     * @param n int整型     * @return int整型     */    int kawaiiStrings(int n)    {        long long A[3][n];//前面无r        long long B[3][n];//出现r                long long C[3][n];//出现re                long long D[3][n];//出现red                        memset(A, 0, sizeof(A));        memset(B, 0, sizeof(B));        memset(C, 0, sizeof(C));        memset(D, 0, sizeof(D));        //cout << "OK";        A[0][0]=0;        A[1][0]=1;       //e        A[2][0]=1;       //d                B[0][0]=1;       //r                B[2][1]=1;      //rd                C[1][1]=1;      //re                D[2][2]=1;      //red                        //C[2][2]=1;        //cout << "OK";                        for (int i=1;i<n;i++){            //A[0][i]=0;            A[1][i]=A[1][i-1]+A[2][i-1];            A[2][i]=A[2][i-1]+A[1][i-1];                              B[0][i]=B[2][i-1]+B[0][i-1]+A[1][i-1]+A[2][i-1];            //B[1][i]=0;            B[2][i]=B[2][i-1]+B[0][i-1];                        C[0][i]=C[0][i-1]+C[1][i-1];            C[1][i]=C[1][i-1]+C[0][i-1]+B[0][i-1]+B[2][i-1];            //C[2][i]=0;                        D[0][i]=D[0][i-1]+D[1][i-1]+D[2][i-1];            D[1][i]=D[1][i-1]+D[0][i-1]+D[2][i-1];            D[2][i]=D[2][i-1]+C[1][i-1]+D[0][i-1]+D[1][i-1]+C[0][i-1];              }                long long ans = 0;        for (int i = 0; i < 3; ++i)            ans = (ans + D[i][n-1]) ;                //没有连续red            long long no_red[n+1];        memset(no_red, 0, sizeof(no_red));        no_red[0]=1;        no_red[1]=3;        no_red[2]=9;        for (int i=3;i<=n;i++)            //没有连续red              no_red[i] = (no_red[i - 1] * 3 - no_red[i - 3]);        //有连续red           //print(pow(3,n)-no_red[n])                    return ans-((pow(3,n)-no_red[n]));    }};int main(){    Solution S;    int n;    cin>>n;    cout << S.kawaiiStrings(n);    return 0;}