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

解题思路是:

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;
}
上一篇:Java网络编程--简单聊天程序


下一篇:远程工作社区|远程工作|APCOW社区|AP社区