蓝桥杯备赛：Day8-小苯的异或和

📚 算法笔记：小苯的异或和 (贡献法与位运算性质)

1. 题目简述

M-小苯的异或疑惑（hard）_北京信息科技大学第十五届程序设计竞赛（同步赛）

• 场景：给定长度为n nn的数组a aa，计算所有满足1 ≤ i < j ≤ n 1 \le i < j \le n1≤i<j≤n的( a i ⊕ a j ) (a_i \oplus a_j)(ai​⊕aj​)的总异或和。
• 核心挑战：n nn高达2 × 10 5 2 \times 10^52×105，两两组合共有n ( n − 1 ) 2 \frac{n(n-1)}{2}2n(n−1)​对，暴力计算会达到2 × 10 10 2 \times 10^{10}2×1010次运算，必然超时。
• 目标：在O ( n ) O(n)O(n)或O ( n log ⁡ n ) O(n \log n)O(nlogn)时间内求出结果。

2. 核心代码 (C++ 实现)

#include <bits/stdc++.h> using namespace std; typedef long long ll; void solve() { int n; if(!(cin >> n)) return; vector<int> a(n); int total_xor = 0; for(int i = 0; i < n; i++) { cin >> a[i]; total_xor ^= a[i]; // 预先计算所有元素的异或总和 } // 关键逻辑判断： // 每个数 a[i] 会出现在 (n-1) 个组合中。 // 如果 (n-1) 是偶数，a[i] 异或偶数次抵消为 0。 // 如果 (n-1) 是奇数，a[i] 异或奇数次等价于异或 1 次。 if ((n - 1) % 2 == 0) { cout << 0 << endl; } else { cout << total_xor << endl; } } int main() { ios::sync_with_stdio(0); cin.tie(0), cout.tie(0); int _ = 1; while(_--) { solve(); } return 0; }

3. 核心考点与注意事项

• 贡献法 (Contribution Technique)：不计算每对组合的结果，而是统计每个元素在最终算式中出现了多少次。
• 异或的归零性：异或运算最核心的性质是x ⊕ x = 0 x \oplus x = 0x⊕x=0。只要某个数出现了偶数次，它在异或链中就会彻底消失。
• 组合数学计数：
  • 元素a k a_kak​会和它前面的k − 1 k-1k−1个数配对，也会和它后面的n − k n-kn−k个数配对。
  • 总次数= ( k − 1 ) + ( n − k ) = n − 1 = (k-1) + (n-k) = n-1=(k−1)+(n−k)=n−1次。
  • 这是一个常数，意味着所有数字出现的次数是一样多的。

🛠️ 位运算基础备忘录