結果
問題 | No.2159 Filling 4x4 array |
ユーザー |
👑 ![]() |
提出日時 | 2022-11-01 22:01:24 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 2,925 bytes |
コンパイル時間 | 785 ms |
コンパイル使用メモリ | 84,100 KB |
実行使用メモリ | 6,824 KB |
最終ジャッジ日時 | 2024-10-14 22:57:12 |
合計ジャッジ時間 | 2,100 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | WA | - |
testcase_01 | AC | 5 ms
6,820 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 | 5 ms
6,816 KB |
testcase_46 | AC | 5 ms
6,820 KB |
testcase_47 | AC | 5 ms
6,820 KB |
testcase_48 | AC | 5 ms
6,816 KB |
testcase_49 | AC | 5 ms
6,820 KB |
ソースコード
#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; }