- 描述
-
老师正在为即将毕业的同学们准备一场舞会，有 2N 个同学会参加这场舞会，他们会被分成 N 对跳舞，每个人有一个编号，如果编号为 i 的同学和编号为 j 的同学配对，那么这一对舞伴的满意度是 Ai,j (i<j)，我们规定整个舞会的满意度为每一对舞伴的满意度的异或和，也就是说，当同学们分成 N 组后，第 k 对同学的满意度为 Ak，那么舞会的满意度为 A1⊕A2⊕A3⊕...⊕AN （其中⊕为异或符号）。
请你求出本场舞会满意度的最大值。
- 输入
- 第一行给出一个数 N (1<=N<=8) 表示有 2N 个人参加舞会。
接下来给出一个矩阵，表示 i 和 j 配对时的满意度：
A1,2, A1,3, ..., A1,2N-1， A1,2N
A2,3, A2,4, ..., A2,2N
...
A2N-1,2N
其中 1<=N<=8, 0<=Ai,j<=230。 - 输出
- 一个整数，表示本场舞会满意度的最大值。
- 样例输入
-
2 13 5 9 10 14 7
- 样例输出
-
11
- 提示
- 如果{1,2}, {3,4}，那么 ans=13⊕7=10;
如果{1,3}, {2,4}，那么 ans=5⊕14=11;
如果{1,4}, {2,3}，那么 ans=9⊕10=3;
所以，最后答案为 max(10,11,3)=11。
数据约定:
对于 40% 的数据, N<=5;
对于全部数据, 1<=N<=8, 0<=Ai,j<=230。
