/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 400 点
問題文
1, 2, \ldots, 2N と番号づけられた 2N 人の人が舞踏会に参加します。 彼らは N 個の 2 人組にわかれてダンスを踊ります。
2 人組を構成する人のうち、番号の小さい方の人が人 i 、番号の大きい方の人が人 j のとき、
その 2 人組の「相性」は A_{i, j} です。
N 個の 2 人組の相性がそれぞれ B_1, B_2, \ldots, B_N であるとき、
「舞踏会全体の楽しさ」はそれらのビットごとの排他的論理和である B_1 \oplus B_2 \oplus \cdots \oplus B_N です。
「 2N 人の参加者が N 個の 2 人組に分かれる方法」を自由に選べるとき、「舞踏会全体の楽しさ」としてあり得る最大値を出力してください。
制約
- 1 \leq N \leq 8
- 0 \leq A_{i, j} < 2^{30}
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
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
2 4 0 1 5 3 2
出力例 1
6
人 i と人 j からなる 2 人組を \lbrace i, j\rbrace で表します。 4 人が 2 個の 2 人組にわかれる方法は下記の 3 通りです。
- \lbrace 1, 2\rbrace, \lbrace 3, 4\rbrace という 2 組にわかれる。 このとき、舞踏会全体の楽しさは A_{1, 2} \oplus A_{3, 4} = 4 \oplus 2 = 6 です。
- \lbrace 1, 3\rbrace, \lbrace 2, 4\rbrace という 2 組にわかれる。 このとき、舞踏会全体の楽しさは A_{1, 3} \oplus A_{2, 4} = 0 \oplus 3 = 3 です。
- \lbrace 1, 4\rbrace, \lbrace 2, 3\rbrace という 2 組にわかれる。 このとき、舞踏会全体の楽しさは A_{1, 4} \oplus A_{2, 3} = 1 \oplus 5 = 4 です。
よって、舞踏会全体の楽しさとしてあり得る最大値は 6 です。
入力例 2
1 5
出力例 2
5
人 1 と人 2 からなる 2 人組のみが作られ、このときの舞踏会全体の楽しさは 5 です。
入力例 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
Score : 400 points
Problem Statement
2N people numbered 1, 2, \ldots, 2N attend a ball. They will group into N pairs and have a dance.
If Person i and Person j pair up, where i is smaller than j, the affinity of that pair is A_{i, j}.
If the N pairs have the affinity of B_1, B_2, \ldots, B_N, the total fun of the ball is the bitwise XOR of them: B_1 \oplus B_2 \oplus \cdots \oplus B_N.
Print the maximum possible total fun of the ball when the 2N people can freely group into N pairs.
Constraints
- 1 \leq N \leq 8
- 0 \leq A_{i, j} < 2^{30}
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
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}
Output
Print the maximum possible total fun of the ball.
Sample Input 1
2 4 0 1 5 3 2
Sample Output 1
6
Let \lbrace i, j\rbrace denote a pair of Person i and Person j. There are three ways for the four people to group into two pairs, as follows.
- Group into \lbrace 1, 2\rbrace, \lbrace 3, 4\rbrace. The total fun of the ball here is A_{1, 2} \oplus A_{3, 4} = 4 \oplus 2 = 6.
- Group into \lbrace 1, 3\rbrace, \lbrace 2, 4\rbrace. The total fun of the ball here is A_{1, 3} \oplus A_{2, 4} = 0 \oplus 3 = 3.
- Group into \lbrace 1, 4\rbrace, \lbrace 2, 3\rbrace. The total fun of the ball here is A_{1, 4} \oplus A_{2, 3} = 1 \oplus 5 = 4.
Therefore, the maximum possible total fun of the ball is 6.
Sample Input 2
1 5
Sample Output 2
5
There will be just a pair of Person 1 and Person 2, where the total fun of the ball is 5.
Sample Input 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
Sample Output 3
1073289207