圣

题目描述

链接：登录—专业IT笔试面试备考平台_牛客网
来源：牛客网

给定 nnn 个数 aia_iai​，求值：XORi=1nORj=1n(ai AND aj)text{XOR}_{i=1}^{n}text{OR}_{j=1}^{n}(a_i~text{AND}~a_j)XORi=1n​ORj=1n​(ai​ AND aj​)，其中符号 XORi=1nai=(a1 XOR a2 ⋯ XOR an)text{XOR}_{i=1}^{n}a_i=(a_1~text{XOR}~a_2~cdots~text{XOR}~a_n)XORi=1n​ai​=

例如 n=2n=2n=2 时即计算：[(a1 AND a1) OR (a1 AND a2)]XOR[(a2 AND a1) OR(a2 AND a2)]left[(a_1~text{AND}~a_1)~text{OR}~(a_1~text{AND}~a_2)right]text{XOR}left[(a_2~text{AND}~a_1)~text{OR}(a_2~text{AND}~a_2)right][(a1​ AND a1​) OR (a1​ AND a2​)]XOR[(a2​ AND a1​) OR(a2​ AND a2​)] 的值。

（摘自 oiwiki）

伪代码：init() 读入，print() 输出
T ← init()
for k ← 1 .. T
    n ← init()
    for i ← 1 .. n
        a[i] ← init()
    ans ← 0
    for i ← 1 .. n
        tp ← 0
        for j ← 1 .. n
            tp ← tp or (a[i] and a[j])
        ans ← ans xor tp
    print(ans)
C/C++ 语言版：
for (k = 1; k <= T; ++k) {
  n = init();
  for (i = 1; i <= n; ++i)
    a[i] = init();
  ans = 0;
  for (i = 1; i <= n; ++i) {
    tp = 0;
    for (j = 1; j <= n; ++j)
      tp |= (a[i] & a[j]);
    ans ^= tp;
  }
}

全文第一行输入一个正整数 T(1≤T≤105)T(1le Tle10^5)T(1≤T≤105)，表示数据组数。

对每组数据，第一行输入一个正整数 n(1≤n≤105,∑n≤5×105)n(1le nle10^5,sum nle5times10^5)n(1≤n≤105,∑n≤5×105)。

第二行输入 nnn 个正整数，表示 ai(1≤ai≤109)a_i(1le a_ile10^9)ai​(1≤ai​≤109)。

对每组数据，输出一行一个整数表示答案。

示例1

复制1 2 1 1

1
2
1 1

复制0

0

#include
#include
#include

using namespace std;
int T,n,x,res;
int main()
{
    scanf("%d",&T);
    while(T--)
    {
        res=0;
        scanf("%d",&n);
        for(int i=1;i<=n;i++)
        {
          scanf("%d",&x);
          res^=x;//与0异或不变，与1异或取反
        }
        cout< 
解析：
 


 举例：[(a1​ AND a1​) OR (a1​ AND a2​)]XOR[(a2​ AND a1​) OR(a2​ AND a2​)] 的值。
 
[(a1​ AND a1​) OR (a1​ AND a2​)]前边一部分就是a1，实际上
 
a1​ AND a1  就是a1
 
a1​ AND a2​ 结果就是小于a1 而且小于a2,  结果是在a1的基础上将一部分的1,给变成0
 
a1与这样的结果OR结果还是a1 
 
实际最后的结果就是a1
 
最终结果个个数据相互异或
 
 
与0异或不变，与1异或相反