No.3229 Liar Game Comibination
タグ : / 解いたユーザー数 43
作問者 :
ジュ・ビオレ・グレイス
/ テスター :
👑 
p-adic
問題文
$N$ 人の人間 $H_n$ を考えます。これらの人間は正直者または嘘つきのどちらか一方なのですが、次のように断片的な情報しか分かっていません:
入力から $\{1, \dots, N\}$ の部分集合 $S_m \ (m = 1 ,\dots, M)$ が $M$ 個与えられ、各 $m$ に対して集合 $\{ i \in S_m \, | \, H_i$ は正直者である $ \} $ の要素数は偶数です。
各人間 $H_i$ が正直者・嘘つきである組み合わせは全部で $2^N$ 通りありますが、そのうち上の条件を $m=1, \cdots, M$ の全てで満たすような組み合わせの個数を $K$ で割った余りを出力してください。
入力
$N\ M \ K$ $S_1$ $\vdots$ $S_M$
$1 \leq N \leq 2560,$
$1 \leq M \leq 2560,$
$1 < K < 2^{31}.$
$S_m$ は $0$ または $1$ からなる長さ $N$ の文字列で与えられ、左から $n$ 番目の文字が $1$ であるような $n$ からなる集合を表しています。後述のサンプル1も参照のこと。
出力
条件を満たす正直者・嘘つきの組み合わせの個数を $K$ で割った余りを出力し、最後に改行してください。
サンプル
サンプル1
入力
4 4 10 1000 1100 1110 1111
出力
1
$S_1 = \{ 1 \},$
$S_2 = \{ 1, 2 \},$
$S_3 = \{ 1, 2, 3 \},$
$S_4 = \{ 1, 2, 3, 4 \}$
なので、$H_1, H_2, H_3, H_4$ は全員嘘つきであることが分かります。したがって取りうる組み合わせは $1$ 通りです。
サンプル2
入力
6 4 11 101100 000111 111110 010101
出力
8
取りうる組み合わせは $8$ 通りです。
サンプル3
入力
10 10 10000000 1100110011 1001010111 0011010000 0000001100 1101110111 1111010010 1010010110 1010101011 1110000010 0000101010
出力
2
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。