結果

問題 No.2159 Filling 4x4 array
コンテスト
ユーザー Nachia
提出日時 2022-11-04 20:50:18
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 317 ms / 5,000 ms
コード長 3,444 bytes
コンパイル時間 1,010 ms
コンパイル使用メモリ 84,588 KB
最終ジャッジ日時 2025-02-08 17:10:54
ジャッジサーバーID
（参考情報） 		judge5 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 5
other AC * 45
権限があれば一括ダウンロードができます

ソースコード

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