题解：P10853 【MX-X2-T2】「Cfz Round 4」Xor Counting

Butterfly_qwq · 2024-08-10 19:17:04 · 题解

简单题。

考虑什么时候会满足条件，设 a_i<a_j。

现在 a_i 和 a_j 的最高位不能相同，否则，a_i\oplus a_j<a_i。

然后 a_i 的最高位在 a_j 中必须是 1，否则 a_i\oplus a_j>a_j。

显然只需统计满足这些条件的数目就行了。枚举 i，看有多少个 j 满足条件，具体直接维护两个数组，一个是有多少个数满足最高位是定值，一个是有多少数的第定值位是 1。

#include<bits/stdc++.h>
#define int long long
using namespace std;
int t,n,ans,a[500005],hb[500005],ct1[500005],ct2[500005];
int highbit(int x)
{
    if(!x)return 114514;
    for(int j=30;~j;j--)if(x&(1<<j))return j;
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>t;
    while(t--)
    {
        memset(ct1,0,sizeof(ct1));
        memset(ct2,0,sizeof(ct2));
        cin>>n;
        for(int i=1;i<=n;i++)cin>>a[i];
        for(int i=1;i<=n;i++)
        {
            hb[i]=highbit(a[i]);
            ct2[hb[i]]++;
            for(int j=30;~j;j--)if(a[i]&(1<<j))ct1[j]++;
        }ans=0;
        for(int i=1;i<=n;i++)
        {
            if(a[i])ans+=ct1[hb[i]]-ct2[hb[i]];
            else ans+=n;
        }
        cout<<ans<<'\n';
    }
}