这题反映出来的就是菜吧
当时就是没想出来。
我们可以想到的一点就是,路径的这个交点个数,其实就是逆序对个数。于是我们考虑 \(K = 2\) 的情况,就是这一层边的临接矩阵的 \(\text{Det}\)。
我们考虑一个事情就是假如一层的奇数答案是 \(f_i\),偶数是 \(g_i\),那么就有 \((g_i-f_i)\times(g_{i+1}-f_{i+1})\) 就是答案。也就是两个答案相乘就得到了两层的答案。
然后我们就解决了 \(n[i]=n[1]\) 的情况了。
结合一个很牛的东西就是 \(|A\times B|=|A|\times |B|\)。
我们考虑每次直接把矩阵相乘,随后的逆序对个数其实和每次分开算的奇偶性是一样的,我们只要最后算出来 \(a_{x,y}\) 表示把这个 \((1,x)\) 点跑到 \((k,y)\) 的路径条数的数量,然后求 \(Det\) 即可。
#include <bits/stdc++.h> const int N = 105, P = 205; using std::cin; using std::cout; const int mod = 998244353; inline int Mod(int x) { if (x >= mod) { return x - mod; } else if (x < 0) { return x + mod; } else { return x; } } int T, n[N], m[N]; inline int ksm(int x, int y) { int res = 1; for ( ; y; y /= 2, x = 1LL * x * x % mod) { if (y & 1) { res = 1LL * res * x % mod; } } return res; } struct Matrix { int row, col, vals[P][P]; int* operator [] (int x) { return vals[x]; } void init(int SZ) { for (int i = 1; i <= SZ; ++i) { vals[i][i] = 1; } } Matrix(int R = 0, int C = 0) { memset(vals, 0, sizeof vals); row = R; col = C; } Matrix operator * (Matrix &a) { Matrix res; for (int i = 1; i <= row; ++i) { for (int k = 1; k <= col; ++k) { for (int j = 1; j <= a.col; ++j) { res[i][j] = Mod(res[i][j] + 1LL * vals[i][k] * a[k][j]); } } } res.row = row; res.col = a.col; return res; } }; void print(Matrix &a) { cout << a.row << ' ' << a.col << '\n'; for (int i = 1; i <= a.row; ++i) { for (int j = 1; j <= a.col; ++j) { cout << a[i][j] << " \n"[j == a.col]; } } } int Det(Matrix a) { int res = 1, kk = 0; for (int i = 1; i <= a.col; ++i) { int pos; for (pos = i; pos <= a.col; ++pos) { if (a[pos][i]) { break; } } if (pos == a.col + 1) { return 0; } kk ^= (pos != i); std::swap(a.vals[pos], a.vals[i]); int inv = ksm(a[i][i], mod - 2); for (int j = i + 1; j <= a.col; ++j) { int l = 1LL * a[j][i] * inv % mod; for (int k = i; k <= a.col; ++k) { a[j][k] = Mod(a[j][k] - 1LL * l * a[i][k] % mod); } } res = 1LL * res * a[i][i] % mod; } return kk ? Mod(-res) : res; } void solve() { int K; cin >> K; for (int i = 1; i <= K; ++i) { cin >> n[i]; } for (int i = 1; i < K; ++i) { cin >> m[i]; } Matrix ans(n[1], n[1]); ans.init(n[1]); //print(ans); for (int i = 1; i < K; ++i) { Matrix g(n[i], n[i + 1]); for (int j = 1, u, v; j <= m[i]; ++j) { cin >> u >> v; g[u][v] = 1; } ans = ans * g; // print(ans); } cout << Det(ans) << '\n'; } int main() { freopen("xpath.in", "r", stdin); freopen("xpath.out", "w", stdout); std::ios::sync_with_stdio(0); cin.tie(0); cin >> T; while (T--) { solve(); } return 0; }