問題一覧 > 通常問題

No.1142 XOR と XOR

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 125
作問者 : 👑 nullnull / テスター : tyawanmusityawanmusi
5 ProblemId : 4608 / 出題時の順位表
問題文最終更新日: 2020-07-18 23:20:28

問題文

ある整数列 $a$ と整数の組 $(l, r)$ について、 $\displaystyle \bigoplus_{i = l}^{r} a_i = a_l\ xor\ a_{l+1}\ xor\ \dots\ xor\ a_r$ とします。ここで $a\ xor\ b$ は $a$ と $b$ の bitwise xor です。
長さ $N$ の数列 $a_1, a_2, \dots, a_N$ と長さ $M$ の数列 $b_1, b_2, \dots, b_M$ が与えられます。
以下の条件を満たす整数の組 $(n, u, l_1, l_2)$ の数を求めてください。

  • $\displaystyle \bigoplus_{x = n}^{u} a_x\ xor\ \displaystyle \bigoplus_{y = l_1}^{l_2} b_y = K\ (1 \le n \le u \le N, 1 \le l_1 \le l_2 \le M)$
ただし、答えが非常に大きくなる場合があるので、$(10^9 + 7)$ で割った余りを出力してください。

制約

  • $1 \le N, M \le 2 \times 10^5$
  • $0 \le a_i, b_j, K < 1024 = 2^{10}(1 \le i \le N, 1 \le j \le M)$
  • 入力はすべて整数

入力

$N\ M\ K$
$a_1\ a_2\ \dots\ a_N$
$b_1\ b_2\ \dots\ b_M$

出力

条件を満たす整数の組の数 $mod\ (10^9+7)$ を一行に出力してください。最後に改行してください。

サンプル

サンプル1
入力
3 3 0
1 2 3
3 4 5
出力
5

$(1, 2, 1, 1), (2, 2, 1, 3), (3, 3, 1, 1), (1, 1, 2, 3), (2, 3, 2, 3)$ の 5 通りです。

サンプル2
入力
10 10 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
出力
3025

すべての選び方が条件を満たします。

サンプル3
入力
14 15 213
363 836 692 58 166 525 170 143 844 457 761 36 395 191
441 941 303 945 986 379 588 946 808 262 672 10 503 901 806
出力
21

$(10^9+7)$ で割った余りを出力することに注意してください。

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