No.3009 Union-Find でつながろう！
タグ : / 解いたユーザー数 12
作問者 :
ジュ・ビオレ・グレイス
/ テスター :
👑 
p-adic
注意
本問題の制限時間は2,000ミリ秒です。かなり厳しいため高速な言語の使用を推奨します。問題文
$N$ 桁の2進数表記の文字列が $M$ 個 $B_1, \cdots, B_M$ と与えられる。$B_m$ の第 $n$ 桁を $b_{m, n}$ とする。本問題では、ビット和、ビット積をそれぞれ $C | D, \ C \& D$ と表すことにする。
集合 $\{0,1,...,2^N-1\}$ の部分集合 $T$ であって以下の条件を満たすものをよい集合と呼ぶ。
- $0, B_1, \cdots, B_M, 2^N-1 \in \mathcal{T}$
- $C,D \in \mathcal{T}$ ならば $C\&D, C|D \in \mathcal{T}$
$0 \leq C < 2^{N}$ について、$C \& D_1 \neq 0, C$ かつ $C \& D_2 \neq 0, C$ となる $D_1, D_2 \in \mathcal{T}$ を適当に選べば $C \& (D_1 | D_2) = C$ かつ $C \& (D_1 \& D_2) = 0$ とできるとき $C$ は分割可能であると呼ぶことにする。
$0 \leq C < 2^{N}$ が 分割不可能であり、$C \& C' = C$ となる分割不可能な $0 \leq C' < 2^N$ が $C$ 以外に存在しないとき、$C$ は極大分割不可能であるという。極大分割不可能な $C$ の個数を出力せよ。
背景
$\mathcal T$ は、有限集合 $X = \{1, \cdots, N \}$ 上の位相と呼ばれる構造になっている（Wikipedia）。すなわち、$N$ 桁の2進数表記の数 $b_1 \cdots b_N$ と $X$ の部分集合 $\{ i \in X : b_i = 1 \}$ を同一視すると、
$\emptyset, X \in \mathcal T,$
$U, V \in \mathcal T \Rightarrow U \cap V \in \mathcal T,$
$U, V \in \mathcal T \Rightarrow U \cup V \in \mathcal T$
を満たしている。
この問題は、位相空間としての連結成分の個数を求める問題である。
入力
$M \ N$
$b_{1, 1} b_{1, 2} \cdots b_{1, N}$
$b_{2, 1} b_{2, 2} \cdots b_{2, N}$
$\vdots$
$b_{M, 1} b_{M, 2} \cdots b_{M, N}$
$1 \leq M \leq 1024,$
$1 \leq N \leq 4096,$
$b_{i, j} \in \{ 0, 1 \} \ (1 \leq i \leq M, \ 1 \leq j \leq N).$
各 $B_m = b_{m, 1} b_{m, 2} \cdots b_{m, N}$ たちが相異なるとは限らないことに注意。
出力
最後に改行してください。
サンプル
サンプル1
入力
4 4 1100 1010 1001 1100
出力
1
$\mathcal{T} = \{ 0000, 1000, 1001, 1010, 1011, 1100, 1101, 1110, 1111 \}$ である。極大分割不可能なものは $1111$ しか存在しないため、1 である。
サンプル2
入力
2 3 100 011
出力
2
$100, 011$ の2つである。
サンプル3
入力
1 16 0000000000000000
出力
1
$1111111111111111$ の1つである。
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。