結果

問題 No.2159 Filling 4x4 array
ユーザー 👑 NachiaNachia
提出日時 2022-11-01 22:01:24
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 2,925 bytes
コンパイル時間 947 ms
コンパイル使用メモリ 85,672 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-04-22 23:06:32
合計ジャッジ時間 2,032 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 WA -
testcase_01 AC 6 ms
6,944 KB
testcase_02 WA -
testcase_03 WA -
testcase_04 WA -
testcase_05 WA -
testcase_06 WA -
testcase_07 WA -
testcase_08 WA -
testcase_09 WA -
testcase_10 WA -
testcase_11 WA -
testcase_12 WA -
testcase_13 WA -
testcase_14 WA -
testcase_15 WA -
testcase_16 WA -
testcase_17 WA -
testcase_18 WA -
testcase_19 WA -
testcase_20 WA -
testcase_21 WA -
testcase_22 WA -
testcase_23 WA -
testcase_24 WA -
testcase_25 WA -
testcase_26 WA -
testcase_27 WA -
testcase_28 WA -
testcase_29 WA -
testcase_30 WA -
testcase_31 WA -
testcase_32 WA -
testcase_33 WA -
testcase_34 WA -
testcase_35 WA -
testcase_36 WA -
testcase_37 WA -
testcase_38 WA -
testcase_39 WA -
testcase_40 WA -
testcase_41 WA -
testcase_42 WA -
testcase_43 WA -
testcase_44 WA -
testcase_45 AC 6 ms
6,940 KB
testcase_46 AC 5 ms
6,940 KB
testcase_47 AC 6 ms
6,940 KB
testcase_48 AC 6 ms
6,944 KB
testcase_49 AC 6 ms
6,940 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; }


// 各状態の制約 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]);
    }
}


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

    int A[8] = {};
    rep(i,3){ cin >> A[i]; A[i] -= 3; }
    rep(i,3){ cin >> A[i+4]; A[i+4] -= 3; }
    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;

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

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

        swap(tmp, dp);

        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