AT_abc236_d [ABC236D] Dance

题目描述

有 $2N$ 个人，编号为 $1, 2, \ldots, 2N$，参加舞会。他们将被分成 $N$ 组，每组 $2$ 人，一起跳舞。

对于组成一组的两个人，若编号较小的是 $i$，编号较大的是 $j$，则这组的“相性”为 $A_{i, j}$。
若 $N$ 个两人组的相性分别为 $B_1, B_2, \ldots, B_N$，则“整个舞会的乐趣”为 $B_1 \oplus B_2 \oplus \cdots \oplus B_N$（即所有相性的按位异或和）。

你可以自由选择如何将 $2N$ 个参与者分成 $N$ 个两人组。请输出“整个舞会的乐趣”可能取得的最大值。

输入格式

输入通过标准输入给出，格式如下：

$N$ $A_{1, 2}$ $A_{1, 3}$ $A_{1, 4}$ $\cdots$ $A_{1, 2N}$ $A_{2, 3}$ $A_{2, 4}$ $\cdots$ $A_{2, 2N}$ $A_{3, 4}$ $\cdots$ $A_{3, 2N}$ $\vdots$ $A_{2N-1, 2N}$

输出格式

请输出“整个舞会的乐趣”可能取得的最大值。

输入输出样例 #1

输入 #1

2
4 0 1
5 3
2

输出 #1

6

输入输出样例 #2

输入 #2

1
5

输出 #2

5

输入输出样例 #3

输入 #3

5
900606388 317329110 665451442 1045743214 260775845 726039763 57365372 741277060 944347467
369646735 642395945 599952146 86221147 523579390 591944369 911198494 695097136
138172503 571268336 111747377 595746631 934427285 840101927 757856472
655483844 580613112 445614713 607825444 252585196 725229185
827291247 105489451 58628521 1032791417 152042357
919691140 703307785 100772330 370415195
666350287 691977663 987658020
1039679956 218233643
70938785

输出 #3

1073289207

说明/提示

限制条件

• $1 \leq N \leq 8$
• $0 \leq A_{i, j} < 2^{30}$
• 所有输入均为整数

样例解释 1

用 $\lbrace i, j\rbrace$ 表示由人 $i$ 和人 $j$ 组成的两人组。将 $4$ 个人分成 $2$ 个两人组的方法有如下 $3$ 种：

• 分为 $\lbrace 1, 2\rbrace, \lbrace 3, 4\rbrace$ 两组。此时，整个舞会的乐趣为 $A_{1, 2} \oplus A_{3, 4} = 4 \oplus 2 = 6$。
• 分为 $\lbrace 1, 3\rbrace, \lbrace 2, 4\rbrace$ 两组。此时，整个舞会的乐趣为 $A_{1, 3} \oplus A_{2, 4} = 0 \oplus 3 = 3$。
• 分为 $\lbrace 1, 4\rbrace, \lbrace 2, 3\rbrace$ 两组。此时，整个舞会的乐趣为 $A_{1, 4} \oplus A_{2, 3} = 1 \oplus 5 = 4$。

因此，整个舞会的乐趣可能取得的最大值为 $6$。

样例解释 2

只能组成 $\lbrace 1, 2\rbrace$ 这一组，此时整个舞会的乐趣为 $5$。

由 ChatGPT 4.1 翻译