No.3229 Liar Game Comibination
タグ : / 解いたユーザー数 44
作問者 :
ジュ・ビオレ・グレイス
/ テスター :
👑 
p-adic
Problem Statement
Consider $N$ humans $H_n$. Each of these humans is either honest or a liar, but only the following fragmentary information is known:
$M$ subsets $S_m \ (m = 1 ,\dots, M)$ of $\{1, \dots, N\}$ are given in the input, and for each $m$, the number of elements of the set $\{ i \in S_m \, | \, H_i$ is honest $ \} $ is even.
There are $2^N$ combinations in total of each human $H_i$ being honest or a liar. Among them, output the number of combinations that satisfy the above condition for all of $m=1, \cdots, M$, modulo $K$.
Input
$N\ M \ K$ $S_1$ $\vdots$ $S_M$
$1 \leq N \leq 2560,$
$1 \leq M \leq 2560,$
$1 < K < 2^{31}.$
$S_m$ is given as a string of length $N$ consisting of $0$ or $1$, and represents the set of those $n$ for which the $n$-th character from the left is $1$. See also Sample 1 below.
Output
Output the number of combinations of honest people and liars satisfying the condition, modulo $K$, followed by a newline.
Sample
Sample 1
Input
4 4 10 1000 1100 1110 1111
Output
1
$S_1 = \{ 1 \},$
$S_2 = \{ 1, 2 \},$
$S_3 = \{ 1, 2, 3 \},$
$S_4 = \{ 1, 2, 3, 4 \}$
so we can tell that $H_1, H_2, H_3, H_4$ are all liars. Therefore, there is $1$ possible combination.
Sample 2
Input
6 4 11 101100 000111 111110 010101
Output
8
There are $8$ possible combinations.
Sample 3
Input
10 10 10000000 1100110011 1001010111 0011010000 0000001100 1101110111 1111010010 1010010110 1010101011 1110000010 0000101010
Output
2
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。