题目理解

我们有一个由 $n$ 个模 $p$ 线性方程组成的系统，每个方程形如 $a_i x_u + b_i x_v \equiv c_i \pmod{p}$，涉及两个变量 $x_u$ 和 $x_v$。需要求解所有变量 $x_1, x_2, \dots, x_n$ 的值。

关键观察：由于有 $n$ 个方程和 $n$ 个变量，且所有无序数对 $(u,v)$ 互不相同，这个方程组对应的图是一个基环树（每个连通分量恰好包含一个环）。

问题转化

将问题转化为图论模型：

• 每个变量 $x_i$ 对应图中的一个节点
• 每个方程 $a_i x_u + b_i x_v \equiv c_i \pmod{p}$ 对应连接节点 $u$ 和 $v$ 的一条无向边

由于图的边数等于节点数，且保证解唯一，这个图必然是一个基环树森林。

算法思路

1. 识别环结构

使用拓扑排序来识别基环树中的环：

void toposort() {
    queue<int> q;
    // 计算每个节点的度数
    for (int i = 1; i <= tot; i++) in[e[i].to]++;
    // 将度数为1的节点入队（叶子节点）
    for (int i = 1; i <= n; i++) if (in[i] == 1) q.push(i);
    
    while (!q.empty()) {
        int x = q.front(); q.pop();
        // 遍历邻接边，减少邻居的度数
        erg(x, i) {
            int v = e[i].to;
            in[v]--;
            if (in[v] == 1) q.push(v);
        }
    }
    // 剩余度数为2的节点构成环
    for (int i = 1; i <= n; i++) cir[i] = (in[i] == 2);
}

2. 环上方程求解

对于环上的节点，我们收集环上的方程，形成循环方程组：

a₁x₁ + b₁x₂ ≡ c₁ (mod p)
a₂x₂ + b₂x₃ ≡ c₂ (mod p)
...
aₙxₙ + bₙx₁ ≡ cₙ (mod p)

使用特殊的高斯消元法求解：

void Gauss(int n) {
    // 前向消元：将矩阵化为上三角形式
    for (int i = 1; i < n - 1; i++) {
        int w = QPow(m[i][0], p - 2);  // 计算逆元
        for (int j = 0; j < 3; j++) m[i][j] = 1ll * m[i][j] * w % p;
        
        // 更新最后一行
        for (int j = 2, w = m[n][0]; j < 3; j++)
            m[n][j] = (m[n][j] - 1ll * m[i][j] * w % p + p) % p;
        m[n][0] = (p - 1ll * m[i][1] * m[n][0] % p) % p;
    }
    
    // 处理最后两行并回代求解
    // ... (详细过程见完整代码)
}

3. 树部分传播求解

已知环上变量的值后，对于树部分（非环节点），通过DFS从环向外传播求解：

void Dfs2(int x, int fa) {
    erg(x, i) {
        int v = e[i].to;
        if (v == fa || cir[v]) continue;
        // 已知x，解方程 a*x + b*y = c 求y
        ans[v] = 1ll * (e[i].c - 1ll * ans[x] * e[i].a % p + p) 
                 * QPow(e[i].b, p - 2) % p;
        Dfs2(v, x);
    }
}

关键技巧

1. 模逆元计算

使用快速幂和费马小定理在质数模 $p$ 下求逆元：

int QPow(int x, int k) {
    int ret = 1;
    for (int i = 0; k; i++, x = 1ll * x * x % p)
        if (k & (1 << i))
            k -= (1 << i), ret = 1ll * ret * x % p;
    return ret;
}

2. 环上DFS收集方程

void Dfs1(int x, int pre) {
    r[++siz] = x;  // 记录环上节点顺序
    vis[x] = 1;
    erg(x, i) {
        int v = e[i].to;
        if (!cir[v] || e[i].num == pre) continue;
        // 存储方程：a*x + b*y = c
        m[siz][0] = e[i].a, m[siz][1] = e[i].b, m[siz][2] = e[i].c;
        if (!vis[v]) Dfs1(v, e[i].num);
    }
}

算法流程

1. 输入建图：读取 $n$ 个方程，建立无向图
2. 拓扑排序：识别图中的环结构
3. 环上求解：对每个环建立方程组并求解
4. 树部分传播：从环上的解出发，求解树部分变量
5. 输出结果：输出所有变量的解

时间复杂度

• 拓扑排序：$O(n)$
• 环上高斯消元：每个环 $O(k)$，总 $O(n)$
• 树部分DFS：$O(n)$
• 总体复杂度：$O(n)$

算法标签

• 基环树 (Pseudotree)
• 拓扑排序
• 高斯消元
• 深度优先搜索
• 模运算与逆元

总结

该算法充分利用了基环树的结构特性，通过分治思想将复杂问题分解为可处理的子问题：

1. 使用拓扑排序识别环结构
2. 对环上的特殊线性方程组设计高效消元算法
3. 通过DFS从已知解传播求解未知变量

这种方法避免了直接求解大型线性方程组的复杂度，实现了线性时间复杂度的求解，能够高效处理 $n \leq 10^5$ 的大规模数据。