Contents

1. 1. 题目：
2. 2. 输入：
3. 3. 输出：
4. 4. 输入样例：
5. 5. 输出样例：
6. 6. Hint(提示)
7. 7. 分析：

正解：

1. 1. 分析：

题目：

　　已知一个包含 n 个元素的正整数集合 S，设 f(S) 为集合 S 中所有元素的异或(XOR)的结果。
如： S={1,2,3}, 则 f(S) = 0
给出集合 S，你需要计算 将所有 f(s) 进行异或后的值, 这里 s⊆S.

输入：

　　多组测试数据。第一行包含一个整数 T (T≤20) 表示组数。
每组测试数据第一行包含一个数 n (1≤n≤1,000) 表示集合的大小，第二行为 n 的数表示集合元素。第 i(1≤i≤n) 个数 0≤ai≤1000,000,000 且数据保证所给集合中没有重复元素。

输出：

　　对于每组测试数据，输出一个数，表示将所有的 f(s)的异或之后的值。

输入样例：

1
3
1 2 3

输出样例：

0

Hint(提示)

样例中， S={1,2,3}, 它的子集有∅, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3}， 空集则f(s)为0，如果子集中只有一个元素则f(s)就是那个元素

分析：

这题我先想到的就是位向量法把所有子集遍历一遍，后来一看数据量，肯定会超时的，所以肯定不能用这个方法了，太慢了，不过还是写了下，当作练习把。

//非空集合有2^ｎ －１个，所以用递归很慢，这道题用递归过不了
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <cctype>
#define MAXN 1010
using namespace std;

int n;
int a[MAXN];
int vis[MAXN];
int f;

void print_subset(int cur){

    int i;
    if(cur == n){
        for(int j = 0 ; j < n; j++) if(vis[j]){
            f = f ^ a[j];
        }
        return ;
    }
    vis[cur] = 1;
　　print_subset(cur + 1);
    vis[cur] = 0;
　　print_subset(cur + 1);
}

int main(){

    int T;
    scanf("%d", &T);
    while(T--){
        f = 0;//初始化为空集

        memset(vis, 0, sizeof(vis));
        memset(a, 0, sizeof(a));
        scanf("%d", &n);
        for(int i = 0; i < n; i++){
            scanf("%d", &a[i]);
        }
        print_subset(0);

        printf("%d\n", f);
    }
    return 0;
}

---

正解：

分析：

• 非空子集有2^ｎ －１个(例：{1,2}的子集：{∅},{1},{2},{1,2})
• 集合中的每个元素在所有子集中出现的总次数为：
  2^(n - 1)次
• 所以如果n > 1， 则每个元素都出现偶数次，对x偶数次异或后得本身(例：5个数，则有4次异或)，
  对x奇数次异或后得0(例：4个数，则有3次异或)，所以当n = 1时，答案就是x, (x和0异或后还是x)

#include<stdio.h>
int main(){

    int n, m, i, j, a, b;
    scanf("%d", &n);
    for (i = 1; i <= n; i++)
    {
        scanf("%d", &m);
        for (j = 1; j <= m; j++)
        {
            scanf("%d", &b);
        }
        if (m > 1) printf("%d\n", 0);
        else printf("%d\n", b);
    }
    return 0;
}