题解：P12177 [蓝桥杯 2025 省 Python B] 异或和

· · 题解

二进制拆位 + 贡献计算 + 快写输出 int128

原式：

\sum_{i=1}^{n} \sum_{j=i+1}^{n} (a_i \oplus a_j) \times (j - i)

等价于：

\sum\limits_{k=0}^{20} \Bigg( 2^k \times \sum\limits_{i=1}^{n}\sum\limits_{j=i+1}^{n} (j-i)[a_{i, k} \not=a_{j, k}] \Bigg)

为了更贴合我们的习惯，我们调换一下 i 和 j 的大小关系：

\sum\limits_{k=0}^{20} \Bigg( 2^k \times \sum\limits_{i=1}^{n}\sum\limits_{j=1}^{i-1} (i-j)[a_{i, k} \not=a_{j, k}] \Bigg)

不难发现可以使用贡献计算的方式解决。

用 cnt_{k,0/1} 记录枚举到的前 i 个数的二进制表示下第 k 位为 0/1 的个数。

再用 sum_{k,0/1} 记录枚举到的前 i 个数的二进制表示下第 k 位为 0/1 的下标总和。

设当前枚举到的第 i 个数的二进制表示下第 k 位为 bit。

那么问题就转化为：

\sum\limits_{k=0}^{20} \Bigg( 2^k \times \sum\limits_{i=1}^{n}(cnt_{k,bit \oplus 1} \times i - sum_{k,bit \oplus 1} )\Bigg)

由于 2^k 可以达到 2^{20}=10^6 规模，任意的 (i,j) 数对可以达到 n^2=10^{10} 规模，而 i-j 又可以达到 n=10^5 规模。共 10^6 \times 10^{10} \times 10^5 = 10^{21} 规模，所以可能爆 long long，需要开 __int128。

\large \mathscr Talk \quad is \quad cheap \ , \ Show \quad me \quad the \quad code. 
#define rep(x,y,z) for(int x=y;x<=z;x++)
#define per(x,y,z) for(int x=y;x>=z;x--)
typedef long long LL;
const int N=1e5+5;
LL n;
LL a[N];
LL cnt[22][2],sum[22][2];
inline void write(__int128 x){
    if(x>9) write(x/10);
    putchar(x%10+'0');
}
void solve(){
    cin>>n;
    rep(i,1,n) cin>>a[i];
    __int128 ans=0;
    per(k,20,0){
        rep(i,1,n){
            int bit=(a[i]>>k)&1;
            ans+=(1LL<<k)*(cnt[k][bit^1]*i-sum[k][bit^1]);
            cnt[k][bit]++,sum[k][bit]+=i;
        }
    }
    write(ans);
}