P13818

HasNoName · 2025-08-24 23:23:13 · 题解

思路

看到题目中的条件，可依先转化。

由于 \mathrm{popcount}(a_i\oplus a_j) \le 2，\mathrm{popcount}(a_i\oplus a_k) \le 2，\mathrm{popcount}(a_k\oplus a_j) \le 2，a_i \oplus a_j \oplus a_k = 0。所以 \mathrm{popcount}(a_i)\le 2，\mathrm{popcount}(a_j)\le 2，\mathrm{popcount}(a_k)\le 2。

不妨设 \mathrm{popcount}(a_i)\ge\mathrm{popcount}(a_j)\ge\mathrm{popcount}(a_k)，若 \mathrm{popcount}(a_i)\ge 3，又因为 a_i \oplus a_j \oplus a_k = 0 所以 a_j\oplus a_k=a_i，所以 \mathrm{popcount}(a_k\oplus a_j)\ge 3，不符合题意，所以得证。

然后就可以把所有 \mathrm{popcount}(a_i)>2 的数先删掉，然后在计算。

又因为 \mathrm{popcount} 表式一个数的二进制表示中 1 的个数，所以这样的数不会太多。具体的，不会超过 O(\log^2 V) 个。

然后考虑开桶存储每一个数的两个为 1 二进制位在哪位，如果只有一个为 1 二进制位，另一个数位用零代替。

然后考虑动态规划。

定义 f_{i,j} 表示一个位 1 的二进制位在第 i 项，另一个在第 j 项的个数。

答案可以在枚举每个数时计算。

对于每一个数，设它的两位二进制位在第 x 位和第 y 位。

则答案将增加 \sum_{i=0}^{\log V} (f_{i,x}+f_{i,y})。

因为这样拼成的一定合法。

复杂度 O(Tn\log V+T\log^2 V)，略微卡常可过。

代码

#include<bits/stdc++.h>
using namespace std;
#define MOD 1000000007
typedef long long ll;
const int N=300005,L=125;
__int128 a[N];
int cnt[L][L];//cnt:f
void read (__int128& ret) {
    ret = 0; int f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') {if (ch == '-') f = -f; ch = getchar();}
    while (ch >= '0' && ch <= '9') ret = ret * 10 + ch - '0', ch = getchar();
    ret *= f;
}
int popcnt(__int128 x)
{
    int cnt=0;
    while(x)
    {
        cnt++;
        x-=x&(-x);
    }
    return cnt;
}
int main()
{
    int T;
    cin>>T;
    while(T--)
    {
        int n,m=0;
        cin>>n;
        for(int i=0;i<L;i++)
            for(int j=0;j<L;j++)
                cnt[i][j]=0;
        for(int i=1;i<=n;i++)
        {
            __int128 x;
            read(x);
            if(popcnt(x)<=2)a[++m]=x;//只用存储肯能对答案造成贡献的
        }
        n=m;
        ll ans=0;
        for(int i=1;i<=n;i++)
        {
            __int128 u=a[i];
            int x=0,y=0,p=0;
            while(u)
            {
                p++;
                if(u&1)
                {
                    if(!x)x=p;
                    else y=p;
                }
                u>>=1;
            }//得到x,y
            for(int j=0;j<L;j++)
            {
                ans+=cnt[j][x]*cnt[j][y];//一定不要再这里取模！
            }
            cnt[x][y]++;
            cnt[y][x]++;
        }
        cout<<ans%MOD<<'\n';
    }
    return 0;
}