Codeforces Round #242 (Div. 2) C. Magic Formulas

解题思路是：

Q=q₁^q_2.......^q_n = p₁^p₂......^p_n^((1%1)^....(1%n))^((2%1)^......(2%n))^....

故Q的求解过程分成两部分

第一部分是求p₁^p₂......^p_n

第二部分是求((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 = 0,p;
    cin>>n;
    vector<int> table(n+1,0);
    for(int i = 1 ; i <= n; ++ i){
        cin >> p; res^=p;                       //针对p1^p2......^pn
        if((n-i)%2) res^=i;                     //针对上三角
        table[i]^=table[i-1]^i;                 //打表
    }
    int a = 1;
    for(int i = 0 ; i < n ; ++ i){              //针对下三角
        int num = (n-i)/a, leave = (n-i)%a;
        if(num%2) res^=table[a-1];
        if(leave) res^=table[leave-1];
        a++;
    }
    cout<<res<<endl;
}