HDU 5344 MZL's XOR 解題詳解：利用異或性質優化計算

題目背景與核心觀察

HDU 5344 MZL's XOR 是一道經典的異或運算應用題。給定一個由線性同餘法生成的陣列 A（長度 n = 5×10⁵），要求計算所有 A[i] + A[j] (1 ≤ i, j ≤ n) 的異或值。直接雙重迴圈複雜度高達 O(n²)，必須尋找數學規律優化。

關鍵洞察：異或的配對抵消性質

異或運算滿足 x ⊕ x = 0。對於任意 i ≠ j，A[i] + A[j] 與 A[j] + A[i] 數值相同，會在異或總和中成對抵消。因此，只有 i = j 時的 2 × A[i] 會保留下來。問題瞬間簡化為計算：

Ans = (2×A₁) ⊕ (2×A₂) ⊕ ... ⊕ (2×Aₙ)

陣列生成與線性遞推

陣列定義為：
A₁ = 0
Aᵢ = (Aᵢ₋₁ × m + z) mod l （i ≥ 2）

由於 A₁ = 0，且 2×0 = 0 不影響異或結果，迴圈可從 i = 2 開始。每次迭代只需維護前一值 tmp，按公式更新並累積 ans ^= (2 * tmp)，時間複雜度 O(n)，空間 O(1)，極易通過限制。

完整參考代碼（C++）

#include <cstdio>
using namespace std;

int main() {
    int T; 
    scanf("%d", &T);
    while (T--) {
        long long n, m, z, l;
        scanf("%lld%lld%lld%lld", &n, &m, &z, &l);
        long long ans = 0, tmp = 0; // tmp 代表 A[i-1]，初始為 A₁=0
        for (int i = 2; i <= n; ++i) {
            tmp = (tmp * m + z) % l; // 計算 A[i]
            ans ^= (2 * tmp);        // 累積 2*A[i]
        }
        printf("%lld\n", ans);
    }
    return 0;
}

複雜度與常見陷阱

• 時間：O(T × n)，n = 5×10⁵，T ≤ 20，約 10⁷ 次簡單運算，遠低於 2 秒時限。
• 空間：O(1)，無需存儲整個陣列。
• 資料型別：m, z, l ≤ 5×10⁵，中間乘積 tmp * m 可能達 2.5×10¹¹，必須用 long long（64 位）。
• 邊界：n=1 時迴圈不執行，ans=0 正確（只有 2×A₁=0）。