题解 | 圣

#include <bits/stdc++.h>
using namespace std ;
typedef long long ll;
const int N = 3e5+10;
ll a[N];
void solve()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
    }

    ll ans = 0;
    for(int i=1;i<=n;i++)
    {
        ans^=a[i];
    }
    cout<<ans<<'\n';
}

int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        solve();
    }

    return 0;
}

不难发现，每次a[i]都会与a[i]自己本身进行一次&运算，所以最终 | 的结果一定是包含a[i]的，又发现，a[i]本身与其他数进行&运算最后的结果，含1的位数一定是a[i]的子集，所以最后与其他所有数的&结果一定等于a[i]本身，所以最终只需要所有数异或一遍就是答案，时间复杂度O(n)