BZOJ 2322 夢想封印：動態維護線性基與路徑異或集合的高斯消元藝術

題目轉化

無向帶權圖，動態加邊（離線倒序轉化刪邊為加邊）。每次詢問：從 1 號點出發，路徑異或和有多少種不同值？

核心數學結構

• 任意路徑異或和 = 1 號點到某點的簡單路徑異或和 ⊕ 若干環的異或和。
• 環的異或和集合 → 維護線性基（高斯消元），大小為 R。
• 簡單路徑異或和集合 → 對線性基消元後去重（用 set），大小為 P。
• 答案 = P * 2^R（每個路徑可任意組合環的線性基向量）。

動態維護策略：以 1 為根的生成樹

• 樹邊 → 對應路徑異或值，加入 set。
• 非樹邊 → 對應環異或值，插入線性基。
• 線性基更新時，需將 set 中所有路徑重新消元去重。

加邊操作分類

1. 兩端點均已訪問：形成環，異或值 z ^ a[x] ^ a[y] 插入線性基。若基更新，重構 set。
2. 僅一端點訪問過：DFS 另一連通塊，將新節點的路徑異或值（消元後）加入 set；遇到非樹邊同樣插入線性基並更新 set。

關鍵代碼片段

// 線性基插入 + set 重構
void Gauss_Elimination(long long x) {
    for (int i = 62; ~i; --i)
        if ((x ^ basis[i]) < x) x ^= basis[i];
    if (!x) return;  // 無新向量
    for (int i = 62; ~i; --i)
        if (x >> i & 1) { basis[i] = x; break; }
    // 重構 set
    vector tmp(s.begin(), s.end());
    s.clear();
    for (auto v : tmp) s.insert(min(v, v ^ x));
}

// DFS 擴展連通塊
void DFS(int x, int from) {
    vis[x] = 1;
    a[x] = a[to] ^ w;  // 路徑異或值
    long long v = a[x];
    for (int i = 62; ~i; --i) v = min(v, v ^ basis[i]);
    s.insert(v);
    for (edge e : adj[x])
        if (e.id != (from ^ 1)) {
            if (!vis[e.to]) DFS(e.to, e.id);
            else Gauss_Elimination(e.w ^ a[x] ^ a[e.to]);
        }
}

複雜度分析

• 每條邊最多導致一次線性基更新（最多 63 次）。
• 每次更新遍歷 set（大小 ≤ n），總體 O(n log n log MAXW)。
• n ≤ 20000，log MAXW ≈ 63，常數優秀可過。

避坑指南

1. set 去重必須在消元後進行，否則同值不同表示會重複。
2. 離線處理：先標記所有被刪除的邊，構建初始圖，再按逆序加邊並記錄答案，最後逆序輸出。
3. 異或基插入順序影響基的形式，但 span 不變，min(v, v^x) 保證唯一表示。