BZOJ 3563/3569 DZY Loves Chinese：隨機化 + 高斯消元解異或方程組

問題背景

給定無向圖，每次詢問刪除 k 條邊後圖是否連通。BZOJ 3563（Chinese I）有特殊性質可 O(1) 判斷；BZOJ 3569（Chinese II）為通用版，需高斯消元。

核心數學模型（Chinese II）

1. 任意選一棵生成樹，邊分為「樹邊」與「非樹邊」
2. 每條非樹邊賦隨機 64 位權值 w
3. 樹邊權值 = 覆蓋該樹邊的所有非樹邊權值異或和
4. 刪除一組邊後圖連通 ⇔ 剩餘邊權值異或和 ≠ 0（對應生成樹存在）

高斯消元解異或方程組

每條邊對應一個變量（是否被刪除）。方程組：剩餘邊權異或 = 0。
矩陣行：詢問中的邊，列：基向量（高斯消元過程中構造）。
若方程組有非零解 → 存在刪除方案使圖斷開 → Disconnected。

完整代碼

#include 
using namespace std;
const int MAXN = 100010;
struct Edge { int u,v; bool tree; long long w; } e[MAXN];
int n,m,q;
vector g[MAXN];
bool vis[MAXN];
long long xr[MAXN];

void dfsTree(int u) {
    vis[u]=true;
    for (int id : g[u]) if (!vis[e[id].v]) {
        e[id].tree = true;
        dfsTree(e[id].v);
    }
}
void dfsXor(int u, int fa) {
    for (int id : g[u]) if (e[id].tree && e[id].v != fa) {
        dfsXor(e[id].v, u);
        e[id].w = xr[e[id].v];
        xr[u] ^= xr[e[id].v];
    }
}

bool gauss(vector& a) {
    int n = a.size(), row = 0;
    for (int bit=62; bit>=0; --bit) {
        int sel = -1;
        for (int i=row; i>bit & 1) { sel=i; break; }
        if (sel==-1) continue;
        swap(a[row], a[sel]);
        for (int i=0; i>bit & 1)) a[i] ^= a[row];
        ++row;
    }
    return a.back() != 0; // 最後一行非零 → 有非零解
}

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    cin >> n >> m;
    for (int i=1; i<=m; ++i) {
        cin >> e[i].u >> e[i].v;
        g[e[i].u].push_back(i);
        g[e[i].v].push_back(i);
    }
    dfsTree(1);
    mt19937_64 rng(19970815);
    for (int i=1; i<=m; ++i) if (!e[i].tree) {
        e[i].w = rng();
        xr[e[i].u] ^= e[i].w;
        xr[e[i].v] ^= e[i].w;
    }
    dfsXor(1,0);
    cin >> q;
    int last=0;
    while (q--) {
        int k; cin >> k;
        vector mat;
        for (int i=0; i> id; id ^= last;
            mat.push_back(e[id].w);
        }
        if (gauss(mat)) { cout << "Disconnected\n"; last=1; }
        else { cout << "Connected\n"; last=0; }
    }
    return 0;
}

關鍵洞察

1. 隨機權值 + 異或 = 線性基表示，將連通性轉化為線性相關性判斷
2. 樹邊權值 = 覆蓋它的非樹邊權值異或，保證任意割集權值異或 = 0
3. 高斯消元在 GF(2) 域上進行，位運算極快
4. 隨機化算法錯誤概率極低（2^-64），工程上可視為確定性

此題是「隨機化 + 線性代數 + 圖論」的巔峰結合，展示了將組合問題代數化的強大威力。