セルオートマトンの逆操作 [yukicoder No.663]

https://yukicoder.me/problems/no/663

前提知識

解法

https://yukicoder.me/submissions/243142

関数g(a,b,c)を用意しておこう。
これは上がa,b,cの時に下がどうなるかを返す。
　
先頭から順番に決めていくが、2つ前だけがそれ以降の決定に影響する。
そのため、2つ前を保持しながらDPで数え上げていこう。
循環するので、最初の部分だけ全探索して、DPしていこう。
「f(v0, v1) := 最初がv0で次がv1である場合の正しい組合せ数」
この中でDPをしていくが、
「dp[i][a][b] := i番目まで確定して2つ前がaで1つ前がbで正しい組み合わせ数」
これで先頭から正しい組み合わせ数を数え上げていく。
最後まで数え上げたら、先頭の2つを使って残りの整合性を確認しながら、答えをまとめていく。

int N, E[2020];
//---------------------------------------------------------------------------------------------------
int g(int a, int b, int c) {
    if (a == 0 and b == 0 and c == 0) return 0;
    if (a == 1 and b == 0 and c == 0) return 0;
    if (a == 1 and b == 1 and c == 1) return 0;
    return 1;
}
//---------------------------------------------------------------------------------------------------
mint dp[2020][2][2];
mint f(int v0, int v1) {
    rep(i, 0, N + 1) rep(a, 0, 2) rep(b, 0, 2) dp[i][a][b] = 0;
    dp[2][v0][v1] = 1;
    rep(i, 2, N) rep(a, 0, 2) rep(b, 0, 2) rep(c, 0, 2) if (g(a, b, c) == E[i - 1]) {
        dp[i + 1][b][c] += dp[i][a][b];
    }

    mint ans = 0;
    rep(a, 0, 2) rep(b, 0, 2) {
        if (g(a, b, v0) == E[N - 1] and g(b, v0, v1) == E[0]) ans += dp[N][a][b];
    }
    return ans;
}
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    rep(i, 0, N) cin >> E[i];

    mint ans = 0;
    rep(v0, 0, 2) rep(v1, 0, 2) ans += f(v0, v1);
    cout << ans << endl;
}