解题思路是:
Q=q1^q2.......^qn = p1^p2......^pn^((1%1)^....(1%n))^((2%1)^......(2%n))^....
故Q的求解过程分成两部分
第一部分是求p1^p2......^pn
第二部分是求((1%1)^....(1%n))^((2%1)^......(2%n))^....
将其化成矩形的形式
1%1 1%2 ........... 1%n
2%1 2%2 ............ 2%n
.....................................
n%1 n%2 ............. n%n
当i小于除数时,即 i%j = i (i<j)
故该矩形的上对角线变成
1%1 1 ........... 1 (n-1)个1
2%1 2%2 ............ 2 (n-2)个2
..................................... ........
(n-1)%1................ n-1
n%1 n%2 ............. n%n 0个n
注意偶数个相同的元素异或结果为0,奇数个相同元素异或结果为本身,0与其他元素异或结果为该元素
故对于矩形上三角 只需要考虑(n-i)的奇偶性 故这部分代码简化为
if(n-i是偶数) res^=i;
现在考虑矩形下三角,将下三角取余数的
0
0 0
0 1 0
. 0 1 ..
. 1 2
. . 0 ...................
. . .
0 .........................................
根据规律
第一列为0循环变化
第二列为0~1循环变化
第i列为 0 ~i-1 循环变化
...........
第i列元素个数为n-i+1
得到每列的循环个数及剩余的个数
判断循环个数的奇偶,注意偶数个相同的元素异或结果为0,奇数个相同元素异或结果为1,0与任何元素异或结果为该元素
然后将剩余的个数异或即可
#include <iostream>
#include <vector>
using namespace std; int main(){
int n,res = ,p;
cin>>n;
vector<int> table(n+,);
for(int i = ; i <= n; ++ i){
cin >> p; res^=p; //针对p1^p2......^pn
if((n-i)%) res^=i; //针对上三角
table[i]^=table[i-]^i; //打表
}
int a = ;
for(int i = ; i < n ; ++ i){ //针对下三角
int num = (n-i)/a, leave = (n-i)%a;
if(num%) res^=table[a-];
if(leave) res^=table[leave-];
a++;
}
cout<<res<<endl;
}