题解 | #小红的漂亮串（二）#

漂亮串种类数 = 所有串的种类数-不含'red'串-只含1个'red'串。
所有串种类数 = 26^n。 长度为 i 的不含'red'串种类数f[i]，和只含一个'red'串种类数g[i]，可以通过递推得到。 f[i] = f[i-1]*26 - f[i-3]，排除f[i-3]+r+e+d的情况。 g[i] = g[i-1]*26 + f[i-3] - g[i-3]，排除g[i-3]+r+e+d的情况，加上f[i-3]+r+e+d的情况。 最终答案是 26^n - f[n] - g[n]

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e6+10, mod=1e9+7;
ll n, f[N], g[N], z;
    
int main()
{
    cin>>n;
    f[0]=1, f[1]=26, f[2]=26*26;    //不含red的字符串种类
    g[0]=0, g[1]=0, g[2]=0;         //只含一个red的字符串种类
    z=26*26;                        //所有字符串种类
    for(int i=3;i<=n;++i){
        z=z*26;
        z=z%mod;
        f[i]=(f[i-1]*26-f[i-3])%mod;
        g[i]=(g[i-1]*25+f[i-3]-g[i-3])%mod;
    }
    cout<<(z-f[n]-g[n]+mod)%mod;
    return 0;
}