← 返回题单

题单练习位运算

← 上一题下一题 →

A6467 | $异或和$

时间限制1s

内存限制128MB

通过 / 提交0/0

题目描述

给定两个数组：长度为 $n$ 的数组 $a$ 和长度为 $m$ 的数组 $b$。你可以进行任意多次如下操作： 选择 $b$ 中的任意一个元素 $b_j$，并将 所有 $a$ 中的元素同时替换为 $a_i \leftarrow a_i \;|\; b_j$（按位或）。 设数组 $a$ 的异或和为 $a_1 \oplus a_2 \oplus \cdots \oplus a_n$（记号 $\oplus$ 表示按位异或）。 请你求出在进行若干次操作之后，数组 $a$ 的异或和的最小值与最大值。 你可以进行 $0$ 次或多次操作；也可以多次选择同一个 $b_j$（再次选择对结果不再产生额外影响）。

输入格式

多组测试数据。 第一行一个整数 $t$（$1 \le t \le 10^4$），表示测试组数。 对于每组数据：- 第一行两个整数 $n,m$（$1 \le n,m \le 2\times 10^5$）。 - 第二行 $n$ 个整数 $a_1,a_2,\ldots,a_n$。 - 第三行 $m$ 个整数 $b_1,b_2,\ldots,b_m$。 保证所有测试数据中 $n$ 的总和与 $m$ 的总和均不超过 $2\times 10^5$。 元素范围：$0 \le a_i,b_i \le 10^9$。

输出格式

对于每组数据，输出一行两个整数，分别表示 最小可能异或和 与 最大可能异或和 。

输入输出样例

输入 #1

输出 #1

0 1
2 3

C++ 编辑器

输入

输出