Lut本科回忆录

看通信原理去咯~

构造包含 $A$ 个字串 $s$ 的总长度为 $n$ 的字符串的方案数。
空间复杂度 $O(2 * A * size(s))$，时间复杂度 $O(n * A * size(s))$
这题我们的 $s$ 长度为 $3$， $A$ 为 $3$，那么时间复杂度就简化为了 $O(n)$

#include <bits/stdc++.h>
#define all(x) x.begin(),x.end()
#define pb(x) push_back(x)
#define PII pair<int, int>
#define INF 1ll << 30
#define ll long long
using namespace std;
const int N = 2e5 + 10, MOD = 1e9 + 7;
ll dp[2][4][3], ans = 0;
int main(){
    //ios::sync_with_stdio(0); cin.tie(0);
    int n; cin >> n;
    dp[0][1][0] = 1;
    for(int i = 1; i <= n; ++ i){
        for(int j = 1; j <= 3; ++ j){
            dp[i & 1][j][0] = (dp[!(i & 1)][j - 1][2] + dp[!(i & 1)][j][0] * 25 + dp[!(i & 1)][j][1] * 24 + dp[!(i & 1)][j][2] * 25) % MOD;
            dp[i & 1][j][1] = (dp[!(i & 1)][j][1] + dp[!(i & 1)][j][0]) % MOD;
            dp[i & 1][j][2] = dp[!(i & 1)][j][1];
        }
        ans = (ans * 26 + dp[!(i & 1)][3][2]) % MOD;
    }
    cout << ans;
}