思路与算法

只关心路径条数奇偶，每层k个点的奇偶向量用k位mask表示。对每个中间k×k矩阵预计算所有mask乘原矩阵和转置矩阵的结果，利用最低位递推异或得到。DP存每种奇偶向量的取反选择数，两种选择分别转移，即使矩阵等于转置也要加两次。最后与末层连边点积为偶数的状态求和。

正确性说明

模2路径计数满足线性变换；mask完全刻画此前所有路径数中与后续有关的信息。每个相邻层有独立的两种操作方案，DP按方案逐次分类，合并同mask只相加不会损失后续区别。末向量点积就是源汇路径奇偶，筛偶数得到所求。

复杂度

每矩阵读入O(k²)，映射预处理O(2^k)，DP O(2^k)，清空数组也同阶；总O(m(k²+2^k))时间、O(2^k+k²)空间。

易错点

可取反的矩阵数为m-3，不包括第一和最后连边。两种取反即便边集合相同仍是不同操作方案。空路径数0也属于偶数。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
const int MOD = 998244353;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int m, k;
    cin >> m >> k;
    int first = 0, last = 0;
    for (int j = 0, x; j < k; j++) {
        cin >> x;
        first |= x << j;
    }
    int S = 1 << k;
    vector<int> dp(S), nxt(S), a(S), b(S);
    dp[first] = 1;
    for (int level = 0; level < m - 3; level++) {
        vector<int> row(k), col(k);
        for (int i = 0; i < k; i++)
            for (int j = 0, x; j < k; j++) {
                cin >> x;
                row[i] |= x << j;
                col[j] |= x << i;
            }
        a[0] = b[0] = 0;
        for (int mask = 1; mask < S; mask++) {
            int z = __builtin_ctz((unsigned)mask), old = mask & (mask - 1);
            a[mask] = a[old] ^ row[z];
            b[mask] = b[old] ^ col[z];
        }
        fill(nxt.begin(), nxt.end(), 0);
        for (int mask = 0; mask < S; mask++) {
            nxt[a[mask]] = (nxt[a[mask]] + dp[mask]) % MOD;
            nxt[b[mask]] = (nxt[b[mask]] + dp[mask]) % MOD;
        }
        dp.swap(nxt);
    }
    for (int j = 0, x; j < k; j++) {
        cin >> x;
        last |= x << j;
    }
    int ans = 0;
    for (int mask = 0; mask < S; mask++)
        if (!(__builtin_popcount((unsigned)(mask & last)) & 1))
            ans = (ans + dp[mask]) % MOD;
    cout << ans << '\n';
}