No.1210 XOR Grid
タグ : / 解いたユーザー数 111
作問者 :
simasima_71
/ テスター :
Rho
Problem Statement
There is a grid with $N$ rows and $M$ columns. You are also given $N$ integers $A_1,\ A_2,\dots\ A_N$ and $M$ integers $B_1,\ B_2, \dots\ B_M$.
You write a non-negative integer less than $2^X$ in every cell. You want the XOR of all numbers in row $i$ to be $A_i$, and the XOR of all numbers in column $j$ to be $B_j$.
How many ways are there to write the numbers in this way? Output the count modulo $10^9+7$.
Input
$N\ M\ X$ $A_1\ \dots\ A_N$ $B_1\ \dots\ B_M$
All inputs are integers.
$1 \le N{,}M \le 200000=2 \times 10^5$
$1 \le X \le 60$
$0 \le A_i{,}B_j < 2^X$
Output
Output the number of ways to write the numbers modulo $({10}^9+7)$.
Print a newline at the end.
Sample
Sample 1
Input
2 2 1 1 0 0 1
Output
2
$(1,0)$ in row $1$ and $(1,1)$ in row $2$
$(0,1)$ in row $1$ and $(0,0)$ in row $2$
These are the 2 ways to write the numbers.
Sample 2
Input
1 1 60 12345 67890
Output
0
If no valid way to write the numbers exists, output $0$.
Sample 3
Input
10 8 60 998 977 811 700 609 444 915 39 578 800 941 749 221 649 397 613 804 883
Output
542426066
Output the answer modulo $({10}^9+7)$.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。