Universal Cup Judging System

Universal Cup

Límite de tiempo: 2.0 s Límite de memoria: 1024 MB Puntuación total: 100 Hackeable ✓
Estadísticas

給定一個長度為 $n$ ($n \ge 2$) 的整數序列,記作 $a_{1,2,\ldots,n}$,以及一個長度為 $m$ ($m \ge 2$) 的整數序列,記作 $b_{1,2,\ldots,m}$,我們可以構造一個 $n \times m$ 的矩陣 $c$,使得 $c_{i,j} = a_i \oplus b_j$ ($1 \le i \le n, 1 \le j \le m$),其中 $\oplus$ 表示按位元互斥或(bitwise XOR)運算。

請決定有多少對 $(i, j)$ ($1 \le i < n, 1 \le j < m$) 滿足矩陣 $c$ 中由 $\begin{bmatrix} c_{i,j} & c_{i,j+1} \\ c_{i+1,j} & c_{i+1,j+1} \end{bmatrix}$ 所給出的子矩形區域具有 $\begin{bmatrix} x & x + 1 \\ x + 2 & x + 3 \end{bmatrix}$ 的形式,亦即滿足 $c_{i,j+1} = c_{i,j} + 1$、$c_{i+1,j} = c_{i,j} + 2$ 且 $c_{i+1,j+1} = c_{i,j} + 3$。

輸入格式

第一行包含一個整數 $T$ ($1 \le T \le 10^5$),代表測試資料的組數。

對於每組測試資料:

第一行包含兩個以空格分隔的整數 $n, m$ ($2 \le n, m \le 2 \times 10^5$),代表矩陣 $c$ 的列數與行數。

第二行包含 $n$ 個以空格分隔的整數,代表 $a_1, a_2, \ldots, a_n$ ($0 \le a_i < 2^{30}$)。

第三行包含 $m$ 個以空格分隔的整數,代表 $b_1, b_2, \ldots, b_m$ ($0 \le b_i < 2^{30}$)。

保證所有測試資料中 $n$ 的總和不超過 $2 \times 10^5$,且 $m$ 的總和不超過 $2 \times 10^5$。

輸出格式

對於每組測試資料,輸出單行一個整數,代表有多少對 $(i, j)$ 滿足條件。

範例

輸入格式 1

5
2 2
0 2
0 1
3 3
6 4 2
6 7 10
5 4
4 6 5 1 3
1 0 2 3
7 2
7 3 1 4 0 0 1
6 5
5 5
1 7 5 3 1
3 2 7 7 6

輸出格式 1

1
2
1
0
6

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.