← 返回题目列表

Codeforces · 1368/D

D. AND、OR 和平方和

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

Gottfried 学习了二进制数表示。然后他提出了这个任务并将其呈现给你。

给你一个 $$$n$$$ 非负整数的集合 $$$a_1, \ldots, a_n$$$。您可以执行以下操作:选择两个不同的索引 $$$1 \leq i, j \leq n$$$。如果在运算之前$$$a_i = x$$$,$$$a_j = y$$$,那么在运算之后$$$a_i = x~\mathsf{AND}~y$$$,$$$a_j = x~\mathsf{OR}~y$$$,其中$$$\mathsf{AND}$$$和$$$\mathsf{OR}$$$分别是按位AND和OR (有关正式描述,请参阅注释部分)。该操作可以执行任意次数(可能为零)。

完成所有操作后,计算 $$$\sum_{i=1}^n a_i^2$$$ — 所有 $$$a_i$$$ 的平方和。你能达到的最大平方和是多少?

输入

第一行包含一个整数 $$$n$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$)。

第二行包含 $$$n$$$ 整数 $$$a_1, \ldots, a_n$$$ ($$$0 \leq a_i < 2^{20}$$$)。

输出

打印单个整数 - 经过多次(可能为零)运算后可以获得的最大可能平方和。

示例

输入 #1

1
123

输出 #1

15129

输入 #2

3
1 3 5

输出 #2

51

输入 #3

2
349525 699050

输出 #3

1099509530625

注意

在第一个示例中无法进行任何操作,因此答案是 $$$123^2$$$。

在第二个示例中,我们可以获得集合$$$1, 1, 7$$$,以及$$$1^2 + 1^2 + 7^2 = 51$$$。

如果 $$$x$$$ 和 $$$y$$$ 以具有相同位数(可能带有前导零)的二进制表示,则当且仅当 $$$x$$$ 和 $$$y$$$ 的相应位都设置为 $$$1$$$ 时,$$$x~\mathsf{AND}~y$$$ 的每一位都设置为 $$$1$$$。类似地,当且仅当 $$$x$$$ 和 $$$y$$$ 的相应位中的至少一个设置为 $$$1$$$ 时,$$$x~\mathsf{OR}~y$$$ 的每一位设置为 $$$1$$$。例如,$$$x = 3$$$ 和 $$$y = 5$$$ 表示为 $$$011_2$$$ 和 $$$101_2$$$(最高位在前)。然后,$$$x~\mathsf{AND}~y = 001_2 = 1$$$,以及$$$x~\mathsf{OR}~y = 111_2 = 7$$$。