結果

問題 No.663 セルオートマトンの逆操作
コンテスト
ユーザー はむこ
提出日時 2018-01-30 23:41:13
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 2 ms / 2,000 ms
コード長 1,578 bytes
コンパイル時間 1,686 ms
コンパイル使用メモリ 162,192 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-12-29 21:53:57
合計ジャッジ時間 2,678 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 29
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>
using namespace std;

#define rep(i,n) for(long long i = 0; i < (long long)(n); i++)
using ll = long long; using vll = vector<ll>;
#define mo  (ll)(1e9+7)

ll n; vll b;
ll baa[2][2][2] = { {{0,-1},{0,1}}, {{1,3},{1,0}}, };

// i(2<=i<n)よりあとを埋める方法であって、
// 直前に埋めたものがp, 直前の直前に埋めたものがppであり、
// 数列の初めがa0, 最後がcであるようなものの数え上げ
ll dp[2020][2][2] = {};
ll dfs(ll i, ll p, ll pp, ll a0, ll c) {
    if (dp[i][p][pp] >= 0) return dp[i][p][pp];
    if (i == n-1) {
        ll dis;
        dis = baa[b[i-1]][pp][p];
        if (dis != 3 && dis != c) return dp[i][p][pp] = 0;
        dis = baa[b[i]][p][c];
        if (dis != 3 && dis != a0) return dp[i][p][pp] = 0;
        return dp[i][p][pp] = 1;
    } else {
        ll state = baa[b[i-1]][pp][p];
        ll ret = 0; 
        if (state == 0 || state == 3)
            (ret += dfs(i+1, 0, p, a0, c)) %= mo;
        if (state == 1 || state == 3)
            (ret += dfs(i+1, 1, p, a0, c)) %= mo;
        return (dp[i][p][pp] = ret) %= mo;
    }
}

int main(void) {
    cin >> n; assert(4<=n&&n<=2000);
    b.resize(n); rep(i, n) cin >> b[i]; rep(i, n) assert(b[i] == 0 || b[i] == 1);

    ll ret = 0;
    vll rule = {0,1,1,1,0,1,1,0};
    rep(maski, 8) if (b[0] == rule[maski]) {
        bitset<3> mask(maski);
        rep(i, 2020) rep(j, 2) rep(h, 2) dp[i][j][h] = -1;
        (ret += dfs(2, mask[0], mask[1], mask[1], mask[2]));
    }
        
    cout << ret % mo << endl;

    return 0;
}
0