考虑动态规划：$f(i,j,k)$ 表示填了 $i$ 位，SOS 共 $j$ 个，SOS 填了 $k = 0,1,2$ 位的方案数。

每一次考虑新填入 S，O 或其他的字符转移，时间复杂度 $O(n^2)$。

答案 $ans = \sum_{j=3}^n \sum_{k=0}^2 f(n,j,k)$。

考虑到 $j$ 只增不减，即凑出的 SOS 不会减少，所以当 $j \geq 3$ 时，后面的都可以任意填，正确性也可以从转移的层面简单证明。

故时间复杂度 $O(n)$。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include<bits/stdc++.h>
using namespace std;
#define ll long long 
const int maxn=1e6;
const int mod=1e9+7;
int n;
ll f[maxn+5][5][5];
signed main(){
    freopen("sos.in","r",stdin);
    freopen("sos.out","w",stdout);
    scanf("%d",&n);
    f[0][0][0]=1;
    for(int i=0;i<n;i++){
        for(int j=0;j<3;j++){
            f[i+1][j][0]=(f[i+1][j][0]+25*f[i][j][0]%mod+24*f[i][j][1]%mod+25*f[i][j][2]%mod)%mod;
            f[i+1][j][1]=(f[i+1][j][1]+f[i][j][0]+f[i][j][1])%mod;
            f[i+1][j][2]=(f[i+1][j][2]+f[i][j][1])%mod;
            f[i+1][j+1][0]=(f[i+1][j+1][0]+f[i][j][2])%mod;
        }
    }
    ll ans=0;
    for(int i=1;i<=n;i++){
        ans=26*ans%mod;
        ans=(ans+f[i][3][0]+f[i][3][1]+f[i][3][2])%mod;
    }
    printf("%lld",ans);
    return 0;
}