競プロ典型90問 086 Snuke's Favorite Arrays(★5)
まず, 各桁ごとに分割して考える. すると, $ Aの要素を2進数で表した際, 下から$ j桁目について, 条件1は次のようになる. 「すべての$ i(1 \leq i \leq Q), j(0 \leq j < 60)について, $ A_{x_i, j}OR $ A_{y_i, j}OR$ A_{z_i, j} = w_{i, j}を満たす」
なお, 条件2については$ 60bitだけ扱うことにより対処できる.
よって, 各桁ごとに上の条件が満たされるような場合の数を求め, 積の法則を用いてそれらを掛け合わせればよい. これは$ Nの制約に注目し, 各桁ごとにbit全探索を行うことにより実装できる.
よって, この問題を$ L = 60として, $ O(2^NL(N + Q))で解くことができた.