結果

問題 No.663 セルオートマトンの逆操作
ユーザー はむこはむこ
提出日時 2018-01-30 23:41:13
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 2 ms / 2,000 ms
コード長 1,578 bytes
コンパイル時間 1,246 ms
コンパイル使用メモリ 148,524 KB
実行使用メモリ 4,380 KB
最終ジャッジ日時 2023-08-28 16:43:14
合計ジャッジ時間 2,842 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge14
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
4,376 KB
testcase_01 AC 2 ms
4,376 KB
testcase_02 AC 1 ms
4,376 KB
testcase_03 AC 2 ms
4,376 KB
testcase_04 AC 2 ms
4,380 KB
testcase_05 AC 1 ms
4,376 KB
testcase_06 AC 2 ms
4,380 KB
testcase_07 AC 1 ms
4,376 KB
testcase_08 AC 2 ms
4,380 KB
testcase_09 AC 1 ms
4,380 KB
testcase_10 AC 2 ms
4,380 KB
testcase_11 AC 2 ms
4,376 KB
testcase_12 AC 2 ms
4,380 KB
testcase_13 AC 2 ms
4,376 KB
testcase_14 AC 1 ms
4,376 KB
testcase_15 AC 2 ms
4,376 KB
testcase_16 AC 2 ms
4,376 KB
testcase_17 AC 1 ms
4,376 KB
testcase_18 AC 1 ms
4,380 KB
testcase_19 AC 2 ms
4,376 KB
testcase_20 AC 2 ms
4,376 KB
testcase_21 AC 2 ms
4,380 KB
testcase_22 AC 1 ms
4,376 KB
testcase_23 AC 2 ms
4,380 KB
testcase_24 AC 2 ms
4,376 KB
testcase_25 AC 2 ms
4,380 KB
testcase_26 AC 2 ms
4,376 KB
testcase_27 AC 1 ms
4,376 KB
testcase_28 AC 1 ms
4,376 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#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