結果

問題 No.2159 Filling 4x4 array
ユーザー 👑 NachiaNachia
提出日時 2022-11-04 20:50:18
言語 C++17
(gcc 13.2.0 + boost 1.83.0)
結果
AC  
実行時間 287 ms / 5,000 ms
コード長 3,444 bytes
コンパイル時間 846 ms
コンパイル使用メモリ 86,532 KB
実行使用メモリ 4,944 KB
最終ジャッジ日時 2023-08-05 01:09:57
合計ジャッジ時間 14,968 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge13
このコードへのチャレンジ（β）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 287 ms
4,640 KB
testcase_01 AC 6 ms
4,424 KB
testcase_02 AC 284 ms
4,776 KB
testcase_03 AC 283 ms
4,632 KB
testcase_04 AC 281 ms
4,768 KB
testcase_05 AC 282 ms
4,772 KB
testcase_06 AC 283 ms
4,596 KB
testcase_07 AC 282 ms
4,580 KB
testcase_08 AC 282 ms
4,768 KB
testcase_09 AC 283 ms
4,640 KB
testcase_10 AC 282 ms
4,584 KB
testcase_11 AC 282 ms
4,592 KB
testcase_12 AC 283 ms
4,688 KB
testcase_13 AC 283 ms
4,788 KB
testcase_14 AC 282 ms
4,748 KB
testcase_15 AC 282 ms
4,788 KB
testcase_16 AC 284 ms
4,684 KB
testcase_17 AC 283 ms
4,580 KB
testcase_18 AC 284 ms
4,624 KB
testcase_19 AC 283 ms
4,648 KB
testcase_20 AC 282 ms
4,912 KB
testcase_21 AC 283 ms
4,580 KB
testcase_22 AC 282 ms
4,584 KB
testcase_23 AC 283 ms
4,684 KB
testcase_24 AC 282 ms
4,644 KB
testcase_25 AC 276 ms
4,892 KB
testcase_26 AC 277 ms
4,924 KB
testcase_27 AC 278 ms
4,684 KB
testcase_28 AC 277 ms
4,600 KB
testcase_29 AC 274 ms
4,944 KB
testcase_30 AC 280 ms
4,680 KB
testcase_31 AC 275 ms
4,652 KB
testcase_32 AC 275 ms
4,748 KB
testcase_33 AC 276 ms
4,628 KB
testcase_34 AC 277 ms
4,632 KB
testcase_35 AC 273 ms
4,576 KB
testcase_36 AC 279 ms
4,684 KB
testcase_37 AC 277 ms
4,636 KB
testcase_38 AC 274 ms
4,632 KB
testcase_39 AC 276 ms
4,644 KB
testcase_40 AC 278 ms
4,600 KB
testcase_41 AC 275 ms
4,688 KB
testcase_42 AC 270 ms
4,604 KB
testcase_43 AC 276 ms
4,704 KB
testcase_44 AC 279 ms
4,592 KB
testcase_45 AC 6 ms
4,412 KB
testcase_46 AC 6 ms
4,380 KB
testcase_47 AC 6 ms
4,376 KB
testcase_48 AC 6 ms
4,376 KB
testcase_49 AC 6 ms
4,380 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <algorithm>
#include <atcoder/modint>
using namespace std;
#define rep(i,n) for(int i=0; i<(int)(n); i++)
using Modint = atcoder::static_modint<998244353>;

const long long stateNum = 4*4*4*4*4*4*4*4;
const long long LOG_A = 30;


/*
    w1 w2 w3 w4
h1  b0 b1 b2 c4
h2  b3 b4 b5 c5
h3  b6 b7 b8 c6
h4  c0 c1 c2 c3

*/


// 位相の係数を整理した関数
int Iso(int w1, int w2, int w3, int w4, int h1, int h2, int h3, int h4){
    int res = 0;
    res = res * 4 + h4;
    res = res * 4 + h3;
    res = res * 4 + h2;
    res = res * 4 + h1;
    res = res * 4 + w4;
    res = res * 4 + w3;
    res = res * 4 + w2;
    res = res * 4 + w1;
    return res;
}

int getConstraint8(int w1, int w2, int w3, int w4, int h1, int h2, int h3, int h4){ return h4%2*128 + h3%2*64 + h2%2*32 + h1%2*16 + w4%2*8 + w3%2*4 + w2%2*2 + w1%2; }

int getWHDiff(int w1, int w2, int w3, int w4, int h1, int h2, int h3, int h4){ return w1+w2+w3+w4-h1-h2-h3-h4+12; }


// 各状態の制約 8 ビットを計算
int Table1[stateNum];
void calcTable1(){
    rep(w1,4) rep(w2,4) rep(w3,4) rep(w4,4) rep(h1,4) rep(h2,4) rep(h3,4) rep(h4,4){
        Table1[Iso(w1,w2,w3,w4,h1,h2,h3,h4)] = getConstraint8(w1,w2,w3,w4,h1,h2,h3,h4);
    }
}

// 制約 8 ビットと、遷移 9 ビットから位相の変化量を計算
int Table2[1<<8][1<<9];
int Table2I[1<<8] = {};
void calcTable2(){
    rep(c7,1<<7) rep(b9,1<<9){
        int G[4][4] = {};
        rep(y,3){
            rep(x,3) G[y][x] = (b9>>(3*y+x))&1;
            rep(x,3) G[y][3] ^= G[y][x];
            rep(x,3) G[3][x] ^= G[y][x];
            G[y][3] ^= (c7>>(4+y))&1;
        }
        rep(x,3) G[3][x] ^= (c7>>x)&1;
        G[3][3] = ((c7>>3) ^ G[0][3] ^ G[1][3] ^ G[2][3]) & 1;
        int c8 = c7 | ((G[3][0] ^ G[3][1] ^ G[3][2] ^ G[3][3]) << 7);
        int Wsum[4] = {};
        rep(y,4) rep(x,4) Wsum[x] += G[y][x];
        int Hsum[4] = {};
        rep(y,4) rep(x,4) Hsum[y] += G[y][x];
        Table2[c8][Table2I[c8]++] = Iso(Wsum[0], Wsum[1], Wsum[2], Wsum[3], Hsum[0], Hsum[1], Hsum[2], Hsum[3]);
    }
}

vector<int> validList[25];
void calcValidList(){
    rep(w1,4) rep(w2,4) rep(w3,4) rep(w4,4) rep(h1,4) rep(h2,4) rep(h3,4) rep(h4,4){
        validList[getWHDiff(w1,w2,w3,w4,h1,h2,h3,h4)].push_back(Iso(w1,w2,w3,w4,h1,h2,h3,h4));
    }
}

int main(){
    calcTable1();
    calcTable2();
    calcValidList();

    long long A[8] = {};
    rep(i,8){ cin >> A[i]; A[i] -= 4; }
    if(A[0] + A[1] + A[2] + A[3] != A[4] + A[5] + A[6] + A[7]){
        cout << "0\n";
        return 0;
    }

    vector<Modint> dp(stateNum);
    dp[Iso(0,0,0,0,0,0,0,0)] = 1;

    int WHDiff = 12;

    for(int d=0; d<LOG_A; d++){
        int a[8];
        for(int i=0; i<8; i++) a[i] = A[i]%2;
        int constraint8 = getConstraint8(a[0], a[1], a[2], a[3], a[4], a[5], a[6], a[7]);
        int c8Iso = Iso(a[0], a[1], a[2], a[3], a[4], a[5], a[6], a[7]);

        vector<Modint> tmp(stateNum);
        for(int s : validList[WHDiff]){
            int c8 = Table1[s] ^ constraint8;
            rep(b8, Table2I[c8]){
                int t = (s + Table2[c8][b8] - c8Iso) / 2;
                tmp[t] += dp[s];
            }
        }

        swap(tmp, dp);

        WHDiff = 12 + (WHDiff - getWHDiff(a[0], a[1], a[2], a[3], a[4], a[5], a[6], a[7])) / 2;

        for(int i=0; i<8; i++) A[i] /= 2;
    }

    cout << dp[Iso(0,0,0,0,0,0,0,0)].val() << '\n';
    return 0;
}
0