CF1957D 题解

· · 题解

题意

定义 f(l,r) 为 a_l 到 a_r 的异或和，三元组 (x,y,z) 合法当且仅当 1\le x\le y\le z\le n，且 f(x,y)\oplus f(y,z)>f(x,z)，求合法三元组的个数。

思路

展开式子，得到 f(x,y)\oplus f(y,z)=f(x,z)\oplus a_y，考虑枚举每个 i 作为 y 的贡献，问题转化为求满足 x\le y\le z 且 f(x,z)\oplus a_y>f(x,z) 的二元组 (x,z) 数量。

考虑 f(x,z) 要怎样才能异或上 a_y 后变大。发现若 a_y 二进制下最高位为第 k 位，则 f(x,y) 的第 k 位为 0 即合法，否则不合法。

考虑证明，显然 a_y 最高位的值一定大于 \frac{a_y}{2}，所以 f(x,z) 异或 a_y 后，第 k 位增加的值一定比后面的位总共减少的值大，结果一定增加；反之也一样。

那么需要快速求出某一位为 0 的 f(x,z) 数量，考虑使用前缀和。设 b_i 为 a_1 至 a_i 的异或和，那么 f(x,z)=b_{x-1}\oplus b_z。特别地，有 b_0=0。

如此 f(x,z) 第 k 位为 0 就转化为 b_{x-1} 和 b_z 的第 k 位相同。因此再设 s_{i,j} 表示 b_0 到 b_i 中第 j 位为 1 的个数，这样用乘法原理即可快速求出合法的 (x,z) 个数。

代码

#include<iostream>
#include<cmath>
#define int long long
using namespace std;
const int N=1e5+10;
const int K=30+10;
int read()
{
    int s=0,w=1;
    char ch=getchar();
    while(ch<'0'||ch>'9') { if(ch=='-') w=-1; ch=getchar();}
    while(ch>='0'&&ch<='9') { s=s*10+ch-'0'; ch=getchar();}
    return s*w;
}
int T,n,ans,a[N],b[N],s[N][K],h[N];//h[i]表示a[i]的最高位，其余如上述 
signed main()
{
    T=read();
    while(T--)
    {
        n=read(),ans=0;
        for(int i=1;i<=n;i++) a[i]=read(),b[i]=b[i-1]^a[i],h[i]=floor(log2(a[i]));
        for(int i=1;i<=n;i++)
        {
            for(int j=0;j<=30;j++) s[i][j]=s[i-1][j];
            int ct=0;
            while(b[i])
            {
                if(b[i]&1) s[i][ct]++;
                b[i]>>=1,ct++;
            }
        }//按思路维护各数组 
        for(int i=1;i<=n;i++) 
        {
            int ta=s[i-1][h[i]],tb=s[n][h[i]]-s[i-1][h[i]];//b[x-1]与b[z]同为1的数量 
            int tc=i-ta,td=n-i+1-tb;//同为0的数量，注意x=1时b[0]也要考虑进去 
            ans+=ta*tb+tc*td;//统计方案数 
        }
        cout<<ans<<'\n';
    }
    return 0;
}