No.1210 XOR Grid

問題提出提出一覧質問統計解説

問題文テストジャッジコードジェネレータ

問題一覧 > 通常問題

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 109
作問者 :

simasima_71 / テスター :

Rho

7 ProblemId : 4846 / 出題時の順位表 / 自分の提出

問題文最終更新日: 2020-08-29 23:00:40

問題文

縦 $N$ 行横 $M$ 列のマス目があります。また、 $N$ 個の整数 $A_{1}, A_{2}, \dots A_{N}$ と $M$ 個の整数 $B_{1}, B_{2}, \dots B_{M}$ が与えられます。
この全てのマスに $2^{X}$ 未満の非負整数を書きます。その結果、 $i$ 行目の全ての数のXORが $A_{i}$ 、 $j$ 列目の全ての数のXORが $B_{j}$ になるようにしたいです。
このような書き込み方は何通りありますか? $10^{9} + 7$ で割った余りを出力してください。

入力

 $N M X$ 
 $A_{1} \dots A_{N}$ 
 $B_{1} \dots B_{M}$

入力は全て整数
$1 \leq N, M \leq 200000 = 2 \times 10^{5}$
$1 \leq X \leq 60$
$0 \leq A_{i}, B_{j} < 2^{X}$

出力

書き込み方を $(10^{9} + 7)$ で割った余りを出力してください。
最後に改行してください。

サンプル

サンプル1

入力

2 2 1
1 0
0 1

出力

$1$ 行目に $(1, 0)$ 、 $2$ 行目に $(1, 1)$
$1$ 行目に $(0, 1)$ 、 $2$ 行目に $(0, 0)$
この2通りの書き込み方があります。

サンプル2

入力

1 1 60
12345
67890

出力

書き込み方が存在しないときは $0$ を出力してください。

サンプル3

入力

10 8 60
998 977 811 700 609 444 915 39 578 800
941 749 221 649 397 613 804 883

出力

542426066

$(10^{9} + 7)$ で割った余りを出力してください。

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。