結果

問題 No.663 セルオートマトンの逆操作
ユーザー はむこ
提出日時 2018-01-30 23:41:13
言語 C++11
(gcc 4.8.5)
結果
AC  
実行時間 3 ms
コード長 1,578 Byte
コンパイル時間 1,004 ms
使用メモリ 8,920 KB
最終ジャッジ日時 2019-07-20 17:38:54

テストケース

テストケース表示
入力 結果 実行時間
使用メモリ
small1.txt AC 2 ms
6,868 KB
small2.txt AC 2 ms
8,920 KB
small3.txt AC 3 ms
6,868 KB
small4.txt AC 3 ms
6,868 KB
small5.txt AC 2 ms
6,868 KB
small6.txt AC 2 ms
6,872 KB
small7.txt AC 1 ms
6,872 KB
small8.txt AC 2 ms
6,868 KB
small9.txt AC 3 ms
6,872 KB
small10.txt AC 2 ms
6,872 KB
small11.txt AC 2 ms
6,872 KB
small12.txt AC 2 ms
6,872 KB
small13.txt AC 2 ms
6,872 KB
small14.txt AC 2 ms
6,868 KB
small15.txt AC 3 ms
6,868 KB
small16.txt AC 2 ms
6,868 KB
test1.txt AC 2 ms
6,872 KB
test2.txt AC 1 ms
6,872 KB
test3.txt AC 2 ms
6,872 KB
test4.txt AC 2 ms
6,872 KB
test5.txt AC 2 ms
6,872 KB
test6.txt AC 2 ms
6,868 KB
test7.txt AC 3 ms
6,872 KB
test8.txt AC 3 ms
6,868 KB
test9.txt AC 2 ms
6,868 KB
test10.txt AC 2 ms
6,872 KB
test11.txt AC 3 ms
6,868 KB
test12.txt AC 2 ms
6,868 KB
test13.txt AC 3 ms
6,868 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