题目描述

现有一个有n 个元素的序列 \(a = [a_{1}, a_{2}, \cdots , a_{n}]\)，定义其价值为 \(\sum_{i=1}^{n}a_{i} \oplus i\)
给出这样一个序列，求其所有排列的价值 \(v_{i}\) 的或 \(v_{1}| v_{2} | \cdots | v_{n-1} | v_{n}\)
其中 \(|\) 为位运算或操作，\(\oplus\) 为位运算异或操作

题目格式

输入

输入的第一行是一个整数 n (2<=n<=10)，表示需排列的数的个数。接下来一行是 n 个整数，数的范围是 0 到 100000，每两个相邻数据间用一个空格分隔。

输出

一个整数，代表所有排列价值的或。

样例1

输入

3
1 2 3

输出

6

提示

3 的全排列有
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1
对应的价值为
\(1\oplus1+2\oplus2+3\oplus3=0\)
\(1\oplus1+3\oplus2+2\oplus3=2\)
\(2\oplus1+1\oplus2+3\oplus3=6\)
\(2\oplus1+3\oplus2+1\oplus3=6\)
\(3\oplus1+1\oplus2+2\oplus3=6\)
\(3\oplus1+2\oplus2+1\oplus3=4\)
其所有价值的或为
\(0 | 2 | 6 | 6 | 6 | 4 = 6\)

/* created by LYZ */
#include<iostream>
using namespace std;

int value = 0;
void swap(int &a, int &b){
	int u = a;
	a = b;
	b = u;

}
int fullPermutation(int *array, int n, int m){//从n到m进行全排列 n是当前的位置 m是结尾的位置
	int sum = 0;
	if (n < m){
		for (int i = n; i < m; i++){
			{ swap(array[i], array[n]);
			}//交换i和n位置的数，让i位置的数作为下次全排列的头部
			fullPermutation(array, n + 1, m);//对n+1后的数进行全排列
			{ swap(array[i], array[n]);
			};//把刚刚交换的数交换回来
		}
	}
	if (n == m){//排列完成

		for (int i = 0; i < m; i++){
			sum += (array[i] ^ (i + 1));//确定异或价值的和
		}
		value |= sum;//进行或运算
	}
	return value;

}


int main(){

	int n;
	cin >> n;
	int a[20];
	for (int i = 0; i < n; i++)
		cin >> a[i];
	cout << fullPermutation(a, 0, n) << endl;


	return 0;
}