圣【牛客tracker 每日一题】

圣

时间限制：1秒 空间限制：256M

网页链接

牛客tracker

牛客tracker & 每日一题，完成每日打卡，即可获得牛币。获得相应数量的牛币，能在【牛币兑换中心】，换取相应奖品！助力每日有题做，丰盈牛币日益多！

题目描述

给定n nn个数a i a_iai​，求值：X O R i = 1 n O R j = 1 n ( a i XOR_{i=1}^nOR_{j=1}^n(a_iXORi=1n​ORj=1n​(ai​A N D ANDANDa j ) a_j)aj​)，其中符号X O R i = 1 n a i = ( a 1 XOR_{i=1}^na_i=(a_1XORi=1n​ai​=(a1​X O R XORXORa 2 ⋯ X O R a_2 ⋯ XORa2​⋯XORa n ) a_n)an​)，另外两个符号同理。

例如n = 2 n=2n=2时即计算：[ ( a 1 [(a_1[(a1​A N D ANDANDa 1 ) a_1)a1​)O R OROR( a 1 (a_1(a1​A N D ANDANDa 2 ) ] a_2)]a2​)]X O R XORXOR[ ( a 2 [(a_2[(a2​A N D ANDANDa 1 ) a_1)a1​)O R OROR( a 2 (a_2(a2​A N D ANDANDa 2 ) ] a_2)]a2​)]的值。

伪代码：init()读入，print()输出 T ←init()fork ←1..T n ←init()fori ←1..n a[i]←init()ans ←0fori ←1..n tp ←0forj ←1..n tp ← tpor(a[i]anda[j])ans ← ansxortpprint(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 ≤ 1 0 5 ) T(1≤T≤10^5)T(1≤T≤105)，表示数据组数。

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

第二行输入n nn个正整数，表示a i ( 1 ≤ a i ≤ 1 0 9 ) a_i(1≤a_i≤10^9)ai​(1≤ai​≤109)。

输出描述：

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

示例1

输入：

1 2 1 1

输出：

0

解题思路

通过数学推导简化原表达式，发现对于每个i ii，O R j = 1 n ( a i OR_{j=1}^n (a_iORj=1n​(ai​&a j ) a_j)aj​)的结果等价于a i a_iai​（因j = i j=ij=i时a i a_iai​&a i = a i a_i=a_iai​=ai​，其余a i a_iai​&a j ≤ a i a_j≤a_iaj​≤ai​，或运算后结果仍为a i a_iai​），因此原表达式X O R i = 1 n O R j = 1 n ( a i XOR_{i=1}^nOR_{j=1}^n(a_iXORi=1n​ORj=1n​(ai​A N D ANDANDa j ) a_j)aj​)可简化为所有a i a_iai​的异或和；基于此，解题时无需按原伪代码的O ( n 2 ) O(n²)O(n2)嵌套循环，直接对每组数据读取n nn个a i a_iai​并计算其异或和即可；该方法将时间复杂度降至O ( n ) O(n)O(n)，适配T TT达1 e 5 1e51e5、∑ n ≤ 5 e 5 ∑n≤5e5∑n≤5e5的输入规模，避免了冗余的嵌套运算，通过规律推导高效且精准地输出每组数据的答案。

代码内容

#include<bits/stdc++.h>usingnamespacestd;typedeflonglongll;typedefpair<ll,ll>pii;constll p=1e9+7;constll N=2e5+10;voidsolve(){ll n;cin>>n;ll x=0;for(ll i=1;i<=n;i++){ll y;cin>>y;x^=y;}cout<<x<<endl;}intmain(){ll t;cin>>t;while(t--)solve();return0;}