← 返回题目列表

Codeforces · 1416/C

C. 异或逆

中文机器翻译题面 查看原题

给定一个数组 $$$a$$$,其中包含 $$$n$$$ 非负整数。你必须选择一个非负整数$$$x$$$并根据以下规则形成一个大小为$$$n$$$的新数组$$$b$$$:对于从$$$1$$$到$$$n$$$的所有$$$i$$$,$$$b_i = a_i \oplus x$$$($$$\oplus$$$表示按位异或运算)。

$$$b$$$ 数组中的反转是一对整数 $$$i$$$ 和 $$$j$$$,使得 $$$1 \le i < j \le n$$$ 和 $$$b_i > b_j$$$。

您应该选择 $$$x$$$,以使 $$$b$$$ 中的反转数量最小化。如果 $$$x$$$ 有多个选项 — 输出最小的一个。

输入

第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 3 \cdot 10^5$$$) — $$$a$$$ 中的元素数量。

第二行包含 $$$n$$$ 以空格分隔的整数 $$$a_1$$$, $$$a_2$$$, ..., $$$a_n$$$ ($$$0 \le a_i \le 10^9$$$),其中 $$$a_i$$$ 是 $$$a$$$ 的第 $$$i$$$ 个元素。

输出

输出两个整数:$$$b$$$ 中可能的最小反转数,以及实现这些反转数的 $$$x$$$ 的最小可能值。

示例

输入 #1

4
0 1 3 2

输出 #1

1 0

输入 #2

9
10 7 9 10 7 5 5 3 5

输出 #2

4 14

输入 #3

3
8 10 3

输出 #3

0 8

注意

在第一个示例中,最好通过选择 $$$x = 0$$$ 使数组保持原样。

在第二个示例中,选择 $$$x = 14$$$ 会产生 $$$b$$$:$$$[4, 9, 7, 4, 9, 11, 11, 13, 11]$$$。它有 $$$4$$$ 反转:

- $$$i = 2$$$, $$$j = 3$$$;
- $$$i = 2$$$, $$$j = 4$$$;
- $$$i = 3$$$,$$$j = 4$$$;
- $$$i = 8$$$,$$$j = 9$$$。

在第三个示例中,选择 $$$x = 8$$$ 会产生 $$$b$$$:$$$[0, 2, 11]$$$。它没有反转。