[典型90] 086 - Snuke's Favorite Arrays（★5）

[Q] https://atcoder.jp/contests/typical90/tasks/typical90_ch

・N=12だから2^12っぽい。
1. 60桁を1桁ずつみていく。
2. 2^Nで採用するNをbit全探索。採用したbitがQ通りの条件に合致するか確認する。
3. 桁ごとの組み合わせの積が解答。

Q. 入力例1
N=4 Q=2
1 2 3 50
2 3 4 45

50:110010
|  |  |
a  b  c  d
   |  |  |
  45:101101

1. 桁ごとに見ていく。
・1桁目だけ見る
50:110010
45:101101
        ^1桁目
        
0  0  0
a  b  c  d
   1  1  1

2. abcdをbit全探索。
abcdを、0000 ~ 1111 まで 2^4通り調べればいい。

・0000 は
a|b|c = 0
b|c|d = 0 != 1  // 2 3 4 45 の条件に違反

・0001 は
a|b|c = 0
b|c|d = 1
で合致するので、
++add // 1

・0010 は
a|b|c = 1 // 1 2 3 50 に違反

・0011 ~ 1111 は違反。

3. 1桁目の清算。
ans *= add // 1


1. 2桁目を見る
50:110010
45:101101
       ^ 2桁目

2. 2^4 bit全探索
0000 NG
0001 NG
0010 NG
...
1000 ++add // 1
1001 NG
...
1111 NG

add = 1なので、
ans *= add // 1

60桁目まで走査し
ans = 13

実装

bool is_pop(ll hash, ll d) { return (hash >> d) & 1; }

ll X[55], Y[55], Z[55], W[55];
int main() {
 cincout();

 ll N, Q;
 cin >> N >> Q;
 rep(q, Q) {
   cin >> X[q] >> Y[q] >> Z[q] >> W[q];
   --X[q];
   --Y[q];
   --Z[q];
 }

 mint ans = 1;
 rep(i, 60) {
   mint add = 0;
   // Wのi桁目のbitをQ通り格納
   bool bits[55];
   rep(j, Q) bits[j] = is_pop(W[j], i);
   // 2^N全探索
   rep(j, 1LL << N) {
     // Q通りcheck
     rep(k, Q) {
       ll x = X[k], y = Y[k], z = Z[k];
       bool test = is_pop(j, x) | is_pop(j, y) | is_pop(j, z);
       if (test != bits[k]) break;
       if (k == Q - 1) ++add;
     }
   }
   ans *= add;
 }
 cout << ans << endl;
}

https://atcoder.jp/contests/typical90/submissions/27932104