题目解法：行列式与路径计数

问题分析

题目要求计算偶数交点方案数与奇数交点方案数的差值，这等价于计算所有方案的交点数奇偶性的代数和（偶数 +1，奇数 -1）。

关键转化

1. 交点数的奇偶性与路径排列的逆序对奇偶性相关

2. 在分层有向无环图中，$n_1$ 条不相交路径的方案可以看作一个置换：第 $i$ 个起点对应第 $p_i$ 个终点

3. 根据 Lindström–Gessel–Viennot 引理，这种不相交路径组的方案数对应矩阵行列式：

其中 $M_{i,j}$ 表示从起点 $i$ 到终点 $j$ 的路径数量

算法步骤

1.动态规划计算路径数量

• 初始化：dp[i][i] = 1（第 1 层起点到自身）

• 逐层转移：对于每个层间转移，更新从每个起点到下一层各点的路径数

• 最终得到矩阵 $A$，其中 $A[i][j]$ 表示从起点 $i$ 到终点 $j$ 的总路径数

2.计算行列式

• 使用高斯消元法计算矩阵行列式 $\det(A)$

• 模 $998244353$ 运算，使用费马小定理求逆元

复杂度分析

• 动态规划：$O(k \cdot n_1^2 \cdot \text{平均度数})$，最坏 $O(100 \cdot 100^2 \cdot 200) \approx 2\times 10^8$，但实际数据较稀疏

• 行列式计算：$O(n_1^3) = O(100^3) = 10^6$

• 总复杂度可接受

代码亮点

1. 模运算优化：使用费马小定理快速计算逆元

2. 内存优化：只维护当前层和下一层的 DP 数组

3. 行列式计算：支持模意义下的高斯消元

AC代码

#include <bits/stdc++.h>
using namespace std;

const int MOD = 998244353;

long long mod_pow(long long a, long long e = MOD - 2) {
    long long r = 1;

    while (e) {
        if (e & 1)
            r = r * a % MOD;

        a = a * a % MOD;
        e >>= 1;
    }

    return r;
}

/* determinant of a square matrix modulo MOD (Gaussian elimination) */
int determinant(vector<vector<int>> a) {
    int n = (int)a.size();
    long long det = 1;
    int sign = 1;                 // +1 or -1 (mod MOD)

    for (int col = 0; col < n; ++col) {
        int pivot = -1;

        for (int row = col; row < n; ++row) {
            if (a[row][col]) {
                pivot = row;
                break;
            }
        }

        if (pivot == -1)
            return 0;               // singular

        if (pivot != col) {
            swap(a[pivot], a[col]);
            sign = MOD - sign;                    // multiply by -1
        }

        int piv = a[col][col];
        det = det * piv % MOD;
        long long inv_piv = mod_pow(piv);

        // eliminate rows below
        for (int row = col + 1; row < n; ++row) {
            if (a[row][col] == 0)
                continue;

            long long factor = a[row][col] * inv_piv % MOD;

            for (int c = col; c < n; ++c) {
                a[row][c] = (a[row][c] - factor * a[col][c]) % MOD;

                if (a[row][c] < 0)
                    a[row][c] += MOD;
            }
        }
    }

    det = det * sign % MOD;

    if (det < 0)
        det += MOD;

    return (int)det;
}

int main() {
    //freopen("xpath.in", "r", stdin);
    //freopen("xpath.out", "w", stdout);
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;

    if (!(cin >> T))
        return 0;

    while (T--) {
        int k;
        cin >> k;
        vector<int> n(k);

        for (int i = 0; i < k; ++i)
            cin >> n[i];

        vector<int> m(k - 1);

        for (int i = 0; i < k - 1; ++i)
            cin >> m[i];

        // adjacency lists for each layer transition
        vector<vector<vector<int>>> adj(k - 1);

        for (int layer = 0; layer < k - 1; ++layer) {
            adj[layer].assign(n[layer], vector<int>());

            for (int e = 0; e < m[layer]; ++e) {
                int u, v;
                cin >> u >> v;
                --u;
                --v;
                adj[layer][u].push_back(v);
            }
        }

        int nSources = n[0];                // = n
        int maxN = *max_element(n.begin(), n.end());   // ≤ 200

        // dp[i][v] : number of paths from source i to vertex v of current layer
        vector<vector<int>> dp(nSources, vector<int>(maxN, 0));
        vector<vector<int>> dp_next(nSources, vector<int>(maxN, 0));

        // initialise layer 1
        for (int i = 0; i < nSources; ++i)
            dp[i][i] = 1;

        // process layers
        for (int layer = 0; layer < k - 1; ++layer) {
            int curN = n[layer];
            int nxtN = n[layer + 1];

            // clear dp_next for the needed columns
            for (int i = 0; i < nSources; ++i)
                fill(dp_next[i].begin(), dp_next[i].begin() + nxtN, 0);

            // transition
            for (int u = 0; u < curN; ++u) {
                const vector<int> &vs = adj[layer][u];

                if (vs.empty())
                    continue;

                for (int src = 0; src < nSources; ++src) {
                    int val = dp[src][u];

                    if (val == 0)
                        continue;

                    for (int v : vs) {
                        int &ref = dp_next[src][v];
                        ref += val;

                        if (ref >= MOD)
                            ref -= MOD;
                    }
                }
            }

            dp.swap(dp_next);
        }

        // build matrix A (size n × n)
        vector<vector<int>> A(nSources, vector<int>(nSources, 0));

        for (int i = 0; i < nSources; ++i)
            for (int j = 0; j < nSources; ++j)
                A[i][j] = dp[i][j];          // dp already modulo MOD

        int ans = determinant(A);
        cout << ans << '\n';
    }

    return 0;
}