「BJWC2018」Cross sum

zhoujinchong2004 @ 2025-10-17 22:14:53

问题数学建模

问题本质

这是一个异或方程组求解问题，附加全局唯一性约束。

数学形式化

给定：

$n \times m$ 的棋盘
若干异或约束：$x_{i_1} \oplus x_{i_2} \oplus \cdots \oplus x_{i_k} = c$
全局约束：所有 $x_i$ 互不相同，且 $x_i \in [1, 2^{60}-1]$

求：一组满足所有约束的解，或判定无解。

核心算法思想

关键观察 1：图论建模

将异或方程组转化为图上的约束传播问题。

建模方式：

节点：每个线索对应一个节点
边：每个空格对应一条边，连接其关联的两个线索节点
边权：空格的值

异或约束：每个节点的所有边权的异或和 = 线索值

关键观察 2：基环树结构

根据连通性，图可以分为两类边：

树边：连接不同连通分量的边
环边：连接同一连通分量的边

核心性质：

树边的权值可以通过 DFS 唯一确定
环边需要满足相容性条件（否则无解）

关键观察 3：随机化构造

由于数字范围极大（ $2^{60}$ ），而空格数量有限（ $\le 40000$ ），随机赋值几乎必然不重复。

概率分析：

$$P(\text{碰撞}) = \frac{n^2}{2^{60}} \approx \frac{40000^2}{10^{18}} \approx 10^{-9} $$

算法流程详解

阶段 1：建图

1.1 节点编号

为每个线索分配唯一节点编号：

int cnt = 0;  // 节点计数器

// 遍历所有格子
for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= m; j++) {
        // 纵向线索（左下角）
        if (tp[i][j] == 1 || tp[i][j] == 3) {
            a[++cnt] = v1[i][j];  // 存储线索值
            
            // 找到所有下方的空格
            int p = i + 1;
            while (tp[p][j] == 4) {
                L[p][j] = cnt;  // 标记空格(p,j)属于线索cnt
                p++;
            }
        }
        
        // 横向线索（右上角）同理
        if (tp[i][j] == 2 || tp[i][j] == 3) {
            a[++cnt] = v2[i][j];
            int p = j + 1;
            while (tp[i][p] == 4) {
                R[i][p] = cnt;
                p++;
            }
        }
    }
}

数据结构说明：

cnt：线索节点总数
L[i][j]：空格 $(i,j)$ 对应的纵向线索编号
R[i][j]：空格 $(i,j)$ 对应的横向线索编号
a[i]：线索 $i$ 的目标异或和

1.2 并查集判断连通性

// 并查集初始化
for (int i = 1; i <= cnt; i++)
    f[i] = i;

// 路径压缩查找
int find(int x) {
    return x == f[x] ? x : f[x] = find(f[x]);
}

优化技巧：使用异或判断是否相等

int find(int x) {
    return x ^ f[x] ? f[x] = find(f[x]) : x;
}

1.3 边的分类

for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= m; j++) {
        if (tp[i][j] == 4) {  // 空格
            nd[i][j] = ++tmp;
            val[tmp] = random_value();  // 随机赋初值
            
            if (L[i][j] && R[i][j]) {
                // 情况1：空格连接两个线索
                if (find(L[i][j]) != find(R[i][j])) {
                    // 树边：连接不同连通分量
                    ADD(L[i][j], R[i][j], nd[i][j]);
                    f[find(L[i][j])] = find(R[i][j]);
                } else {
                    // 环边：连接同一连通分量
                    a[L[i][j]] ^= val[tmp];
                    a[R[i][j]] ^= val[tmp];
                }
            } else if (L[i][j]) {
                // 情况2：只属于纵向线索（叶子边）
                g[L[i][j]].push_back(tmp);
            } else if (R[i][j]) {
                // 情况3：只属于横向线索（叶子边）
                g[R[i][j]].push_back(tmp);
            }
        }
    }
}

图的存储：链式前向星

struct Edge {
    int to, next, edge_id;
};

void add_edge(int u, int v, int eid) {
    to[++tot] = v;
    nx[tot] = head[u];
    id[tot] = eid;
    head[u] = tot;
}

void ADD(int u, int v, int eid) {
    add_edge(u, v, eid);  // 正向边
    add_edge(v, u, eid);  // 反向边（无向图）
}

阶段 2：随机化构造

#include <random>
mt19937_64 rng(114514);  // 64位梅森旋转随机数生成器

// 为每个空格随机赋值
val[tmp] = rng() % ((1LL << 60) - 1) + 1;

为什么随机化可行？

数字空间巨大： $2^{60} \approx 10^{18}$
需求数量有限：最多 $200 \times 200 = 40000$ 个数字
碰撞概率极低：根据生日悖论，碰撞概率 $\approx \frac{n^2}{2N} \approx 10^{-9}$

阶段 3：DFS 求解树边

3.1 算法核心思想

关键性质：在树结构中，从叶子到根可以唯一确定所有边权。

递归策略：

先处理所有叶子边（只属于该节点的边）
递归处理子树
根据子树的剩余异或和确定树边权值
更新当前节点的剩余异或和

3.2 DFS 实现

void dfs(int u, bool is_root) {
    vis[u] = true;
    
    // 步骤1：处理叶子边
    // 叶子边的权值已经随机赋值，先累加到异或和中
    for (int leaf_edge_id : g[u]) {
        a[u] ^= val[leaf_edge_id];
    }
    
    // 步骤2：遍历所有树边，递归处理子树
    for (int i = head[u]; i; i = nx[i]) {
        int v = to[i];
        if (!vis[v]) {
            // 递归处理子树
            dfs(v, false);
            
            // 步骤3：确定边权
            // 子树处理完后，a[v] 是子树的剩余异或和
            // 这个剩余值必须等于连接边的权值
            val[id[i]] = a[v];
            
            // 步骤4：更新当前节点
            a[u] ^= a[v];  // 减去该边的贡献
            a[v] = 0;      // 子树方程已满足
        }
    }
    
    // 步骤5：根节点的调整
    // 如果是根节点且有叶子边，调整第一个叶子边
    if (is_root && g[u].size()) {
        val[g[u][0]] ^= a[u];
        a[u] = 0;
    }
}

数学原理：

设节点 $u$ 的线索值为 $c$ ，所有相关边为 $e_1, e_2, \ldots, e_k$ ，则：

$$\text{val}(e_1) \oplus \text{val}(e_2) \oplus \cdots \oplus \text{val}(e_k) = c $$

DFS 过程中：

$$a[u] = c \oplus \bigoplus_{i=1}^{k} \text{val}(e_i) $$

初始： $a[u] = c$
每处理一条边 $e_i$ ，执行 $a[u] \gets a[u] \oplus \text{val}(e_i)$
最终： $a[u] = 0$ （方程满足）

阶段 4：可行性检查

4.1 检查异或约束

// 检查所有线索的异或和是否为0
for (int i = 1; i <= cnt; i++) {
    if (a[i] != 0) {
        puts("-1");  // 存在未满足的约束
        return;
    }
}

含义：

$a[i] = 0$ ：线索 $i$ 的异或方程满足
$a[i] \neq 0$ ：存在矛盾，无解

4.2 检查唯一性约束

map<ull, bool> used;

for (int i = 1; i <= tmp; i++) {
    if (val[i] == 0 || used.count(val[i])) {
        puts("-1");  // 数字为0或重复
        return;
    }
    used[val[i]] = true;
}

优化：使用 unordered_map 可以降低复杂度到 $O(1)$

📐 数学理论基础

定理 1：异或线性空间

命题：异或方程组的解空间是 $\text{GF}(2)^{60}$ 的一个线性子空间。

证明要点：

异或运算满足交换律和结合律
$(a \oplus b) \oplus c = a \oplus (b \oplus c)$
$a \oplus a = 0$ ， $a \oplus 0 = a$

因此异或方程组等价于 $\text{GF}(2)$ 上的线性方程组。

定理 2：树边的唯一性

命题：在树结构中，给定叶子边的权值后，所有树边的权值唯一确定。

证明：对树进行后序遍历，设节点 $u$ 有子树 $v_1, v_2, \ldots, v_k$ ，则：

\text{edge}(u, v_i) = \text{xor\_sum}(v_i)

由于异或的唯一性，每条边的权值唯一确定。□

定理 3：环边的相容性

命题：环边必须满足环上所有约束的相容性，否则无解。

证明：设环上有节点 $u_1, u_2, \ldots, u_k$ ，边为 $e_1, e_2, \ldots, e_k$ 。

环的约束：

$$\bigoplus_{i=1}^{k} c_i = \bigoplus_{i=1}^{k} \text{val}(e_i) $$

如果环边随机赋值后不满足此条件，则整个方程组无解。□

复杂度分析

时间复杂度

建图： $O(nm)$
- 遍历所有格子，建立映射关系
并查集： $O(nm \cdot \alpha(nm))$
- 路径压缩后，单次操作接近 $O(1)$
DFS： $O(\text{节点数} + \text{边数}) = O(nm)$
- 每个节点和边各访问一次
去重检查： $O(nm \log nm)$
- 使用 map 插入和查询

总时间复杂度： $O(nm \log nm)$

空间复杂度

图的存储： $O(nm)$
并查集： $O(nm)$
哈希表： $O(nm)$

总空间复杂度： $O(nm)$

算法优化技巧

优化 1：路径压缩的异或技巧

// 标准路径压缩
int find(int x) {
    return x == f[x] ? x : f[x] = find(f[x]);
}

// 异或优化版本
int find(int x) {
    return x ^ f[x] ? f[x] = find(f[x]) : x;
}

原理：x ^ f[x] 当且仅当 x != f[x] 时为真（假设 x, f[x] > 0）

优化 2：链式前向星存图

// 数组模拟链表，避免动态分配
int head[M], to[M], nx[M], id[M], tot;

void add_edge(int u, int v, int eid) {
    to[++tot] = v;
    nx[tot] = head[u];
    id[tot] = eid;
    head[u] = tot;
}

优势：

访问连续内存，缓存友好
避免动态分配开销

优化 3：快速清零

// 方法1：memset（慢）
memset(array, 0, sizeof(array));

// 方法2：只清零使用过的部分（快）
for (int i = 1; i <= cnt; i++) {
    a[i] = 0;
}

代码框架

int main() {
    int T;
    scanf("%d", &T);
    
    while (T--) {
        // 1. 读入数据
        read_input();
        
        // 2. 建图（节点编号 + 边分类）
        build_graph();
        
        // 3. 随机化初始构造
        random_initialize();
        
        // 4. DFS 求解树边
        for (int i = 1; i <= cnt; i++) {
            if (!vis[i]) {
                dfs(i, true);
            }
        }
        
        // 5. 可行性检查
        if (!check_feasibility()) {
            puts("-1");
        } else {
            output_solution();
        }
        
        // 6. 清理数据
        clear();
    }
    
    return 0;
}

关键数据结构总结

数组映射

数组	含义	范围
`tp[i][j]`	格子类型	0-4
`L[i][j]`	空格的纵向线索编号	1-cnt
`R[i][j]`	空格的横向线索编号	1-cnt
`nd[i][j]`	空格的边编号	1-tmp
`a[i]`	线索的剩余异或和	0- $2^{60}$
`val[i]`	边的权值（空格的值）	1- $2^{60}$

图的存储

// 链式前向星
int head[M];   // 节点的第一条边
int to[M];     // 边的终点
int nx[M];     // 下一条边
int id[M];     // 边的编号

// 邻接表（叶子边）
vector<int> g[M];  // g[u] 存储节点u的所有叶子边

易错点提醒

错误 1：忘记处理环边

//  错误：没有更新环边的异或和
if (find(L[i][j]) == find(R[i][j])) {
    // 环边，需要检查相容性
}

//  正确：更新异或和
if (find(L[i][j]) == find(R[i][j])) {
    a[L[i][j]] ^= val[tmp];
    a[R[i][j]] ^= val[tmp];
}

错误 2：DFS 时未标记访问

//  错误：可能重复访问
void dfs(int u) {
    // 忘记标记
    for (边) dfs(v);
}

// 正确
void dfs(int u) {
    vis[u] = true;  // 必须先标记
    for (边) if (!vis[v]) dfs(v);
}

错误 3：根节点的特殊处理

// 根节点如果还有剩余异或和，需要调整叶子边
if (is_root && g[u].size()) {
    val[g[u][0]] ^= a[u];
    a[u] = 0;
}

1 条题解