专栏文章

P13818

HHasNoName
P13818题解参与者 2已保存评论 2

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
2 条
当前快照
1 份
快照标识符
@mio5kkd8
此快照首次捕获于
2025/12/02 13:43
3 个月前
此快照最后确认于
2025/12/02 13:43
3 个月前
查看原文

思路

看到题目中的条件，可依先转化。
由于 popcount(ai⊕aj)≤2\mathrm{popcount}(a_i\oplus a_j) \le 2，popcount(ai⊕ak)≤2\mathrm{popcount}(a_i\oplus a_k) \le 2，popcount(ak⊕aj)≤2\mathrm{popcount}(a_k\oplus a_j) \le 2，ai⊕aj⊕ak=0a_i \oplus a_j \oplus a_k = 0。所以 popcount(ai)≤2\mathrm{popcount}(a_i)\le 2，popcount(aj)≤2\mathrm{popcount}(a_j)\le 2，popcount(ak)≤2\mathrm{popcount}(a_k)\le 2。
不妨设 popcount(ai)≥popcount(aj)≥popcount(ak)\mathrm{popcount}(a_i)\ge\mathrm{popcount}(a_j)\ge\mathrm{popcount}(a_k)，若 popcount(ai)≥3\mathrm{popcount}(a_i)\ge 3，又因为 ai⊕aj⊕ak=0a_i \oplus a_j \oplus a_k = 0 所以 aj⊕ak=aia_j\oplus a_k=a_i，所以 popcount(ak⊕aj)≥3\mathrm{popcount}(a_k\oplus a_j)\ge 3，不符合题意，所以得证。
然后就可以把所有 popcount(ai)>2\mathrm{popcount}(a_i)>2 的数先删掉，然后在计算。
又因为 popcount\mathrm{popcount} 表式一个数的二进制表示中 11 的个数，所以这样的数不会太多。具体的，不会超过 O(log⁡2V)O(\log^2 V) 个。
然后考虑开桶存储每一个数的两个为 11 二进制位在哪位，如果只有一个为 11 二进制位，另一个数位用零代替。
然后考虑动态规划。
定义 fi,jf_{i,j} 表示一个位 11 的二进制位在第 ii 项，另一个在第 jj 项的个数。
答案可以在枚举每个数时计算。
对于每一个数，设它的两位二进制位在第 xx 位和第 yy 位。
则答案将增加 ∑i=0log⁡V(fi,x+fi,y)\sum_{i=0}^{\log V} (f_{i,x}+f_{i,y})。
因为这样拼成的一定合法。
复杂度 O(Tnlog⁡V+Tlog⁡2V)O(Tn\log V+T\log^2 V)，略微卡常可过。

代码

CPP
#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;
}

评论

共 2 条评论，欢迎与作者交流。

正在加载评论...