思路与算法

令p0=0，pi为前i个未知位的异或。询问[i,j]得到p(i-1) xor pj，视为连接前缀顶点i-1与j的一条边。若全部前缀顶点在同一连通分量，沿边可推导所有pi与p0的关系，进而求每个未知位。构造N+1个点的完全图，用Prim求最小生成树权和。

正确性说明

一个连通分量内部只能知道前缀变量间的相对异或；若还有不含p0的分量，可把其中所有前缀同时翻转而不改变已询问答案，因此不能唯一确定全部数。反之连通即可确定。最优方案可去掉环边而仍连通，非负代价下最小费用等于MST。

复杂度

读入三角矩阵并对称补全O(N²)，Prim每轮扫描O(N)，总O(N²)时间；矩阵O(N²)、距离和标记O(N)空间，初始化也计入。

易错点

原变量N个，前缀点N+1个；区间[i,j]连接i-1和j。允许0代价，答案可能达到2×10^12，须64位。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n;
    cin >> n;
    ++n;
    vector<vector<long long>> a(n, vector<long long>(n));
    for (int i = 1; i < n; i++)
        for (int j = i; j < n; j++) {
            cin >> a[i - 1][j];
            a[j][i - 1] = a[i - 1][j];
        }
    vector<long long> d(n, LLONG_MAX);
    vector<int> vis(n);
    d[0] = 0;
    long long ans = 0;
    for (int k = 0; k < n; k++) {
        int u = -1;
        for (int i = 0; i < n; i++)
            if (!vis[i] && (u < 0 || d[i] < d[u]))
                u = i;
        vis[u] = 1;
        ans += d[u];
        for (int i = 0; i < n; i++)
            if (!vis[i])
                d[i] = min(d[i], a[u][i]);
    }
    cout << ans << '\n';
}