D - We Like AGC

https://atcoder.jp/contests/abc122/tasks/abc122_d

解法

dp[i][m] := 長さがiで後ろ3文字がmとなる個数として、後ろに足した文字によって

dp[i+1][t] += dp[i][m]  と遷移したい

3文字の状態はACGT をそれぞれ1234とみなして10進数で扱うとわかりやすい

後ろに文字を付け足した後に ?AGC , ?ACG , ?GAC , A?GC , AG?Cのいずれかになっている場合アウトである

https://atcoder.jp/contests/abc122/submissions/4698279

void solve() {
    cin >> n;
    vvm(dp, n + 1, 10000);
    dp[0][0] = 1;
    rep(i, n) {
        rep(m, 10000) {
            if (dp[i][m] == 0)continue;
            rep(v, 1, 5) {
                int t = (m % 1000) * 10 + v;
                if (t % 1000 == 123 || t % 1000 == 132 || t % 1000 == 312 || t == 1132|| t == 1232|| t == 1332 || t == 1432|| t == 1312|| t == 1322|| t == 1332|| t == 1342)continue;
                dp[i + 1][t] += dp[i][m];
            }
        }
    }
    cout << sum(dp[n]) << endl;
}