| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 2048 MB | 56 | 22 | 21 | 42.000% |
You are given an array $A$ of $N$ integers: $[A_1, A_2, \dots , A_N ]$.
The array $A$ is $(p, q)$-xorderable if it is possible to rearrange $A$ such that for each pair $(i, j)$ that satisfies 1ドル ≤ i < j ≤ N,ドル the following conditions must be satisfied after the rearrangement: $A_i \oplus p ≤ A_j \oplus q$ and $A_i \oplus q ≤ A_j \oplus p$. The operator $\oplus$ represents the bitwise xor.
You are given another array $X$ of length $M$: $[X_1, X_2, \dots , X_M]$. Calculate the number of pairs $(u, v)$ where array $A$ is $(X_u, X_v)$-xorderable for 1ドル ≤ u < v ≤ M$.
The first line consists of two integers $N$ $M$ (2ドル ≤ N, M ≤ 200,円 000$).
The second line consists of $N$ integers $A_i$ (0ドル ≤ A_i < 2^{30}$).
The third line consists of $M$ integers $X_u$ (0ドル ≤ X_u < 2^{30}$).
Output a single integer representing the number of pairs $(u, v)$ where array $A$ is $(X_u, X_v)$-xorderable for 1ドル ≤ u < v ≤ M$.
3 4 0 3 0 1 2 1 1
3
The array $A$ is $(1, 1)$-xorderable by rearranging the array $A$ to $[0, 0, 3]$.
5 2 0 7 13 22 24 12 10
1
The array $A$ is $(12, 10)$-xorderable by rearranging the array $A$ to $[13, 0, 7, 24, 22]$.
3 3 0 0 0 1 2 3
0