题目描述
现有一个有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;
}