HDU 5650.so easy

358


题目  




Description  



Given an array with
n
n
integers, assume f(S)f(S) as the result of executing xor operation among all the elements of set SS. e.g. if S={1,2,3}S={1,2,3} then f(S)=0f(S)=0.

your task is: calculate xor of all f(s)f(s), here s⊆Ss⊆S.


Input  



This problem has multi test cases. First line contains a single integer T(T≤20)T(T≤20) which represents the number of test cases.
For each test case, the first line contains a single integer number n(1≤n≤1,000)n(1≤n≤1,000) that represents the size of the given set. then the following line consists of nn different integer numbers indicate elements(≤109≤109) of the given set.


Output  



For each test case, print a single integer as the answer.


Sample Input  



1 3 1 2 3


Sample Output  



0


Hint    



In the sample,S={1,2,3}S={1,2,3}, subsets of SS are: ∅∅, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3}


题解



非常简单的一道题,但是理解题意得难度要大于做出来……


其题意就是要求出集合{S}的所有子集{s}元素异或的异或

同一个数自己对自己异或为0

0对任何书异或都是该数本身

a^b^a=b

同时,异或操作满足交换律的结合律

因此,只要一个元素出现偶数次,就可以不再考虑该数


可以发现,除非只有一个元素,否则每个元素在最后总的计算中必定出现偶数次,因此,当n=0时,答案为该数本身,否则,答案为0

代码



/*
By:OhYee
Github:OhYee
Email:oyohyee@oyohyee.com
Blog:http://www.cnblogs.com/ohyee/

かしこいかわいい?
エリーチカ!
要写出来Хорошо的代码哦~
*/
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <string>
#include <iostream>
#include <vector>
#include <list>
#include <queue>
#include <stack>
using namespace std;

//DEBUG MODE
#define debug 0

//循环
#define REP(n) for(int o=0;o<n;o++)

const int maxn = 10000;
int n, m;
int Map[maxn][maxn];

void Do() {
    int n;
    scanf("%d", &n);
    int temp, ans;
    if (n==1) {
        REP(n) {
            if (o == 0) 
                scanf("%d", &ans);
            
            else 
                scanf("%*d", &temp);
        }
    }
    else {
        REP(n)
            scanf("%*d");
        ans = 0;
    }
    
    printf("%d\n", ans);
}


int main() {
    int T;
    scanf("%d", &T);
    while (T--) {
        Do();
    }
    return 0;
}
发布评论
  • 点击查看/关闭被识别为广告的评论