Solution

讲个笑话：昨天有个关系很好的同学问我如何证明 $\det(AB) = \det(A)\det(B)$，$A,B \in \mathbb R^{n \times n}$。当时脑抽，直接暴力展开借鉴 $\rm LGV$ 引理的证明。

其中有一个恒等式：考虑置换 $p_1$ 和 $p_2$，定义 $p_1$ 作用在 $p_2$ 上的结果为 $p_1 \circ p_2$。则：

$$(-1)^{\tau(p_1) + \tau(p_2)} = (-1)^{\tau(p_1 \circ p_2)}$$

证明：提供一个很唐的想法。考虑枚举 $i$ 和 $j$（$i < j$）。$p_{2,i}$ 和 $p_{2,j}$ 在最终的 $p_1 \circ p_2$ 中能产生逆序对，当且仅当 $[p_{2,i} < p_{2,j}] \oplus [p_{1,i}^{-1} < p_{1,j}^{-1}] =1$。在 $(-1)$ 的幂次中，我们可以直接改为加法。而显然 $\tau(p_1^{-1}) = \tau(p_1)$，得证。

所以本题中，所有置换的逆序对之和的奇偶性等于他们作用在一起中逆序对个数的奇偶性。

那么这是 $\rm LGV$ 引理的模板。

不得不说，$\rm NOI 2021$ 的 $\rm Day 1$ 确实有点。不过这是我开上帝视角的结论：毕竟 $\rm LGV$ 引理是在这一场考试之后才大范围普及的，让我这种低水平算法竞赛选手都了解过。

#include<bits/stdc++.h>
#define int long long
#define ffor(i,a,b) for(int i=(a);i<=(b);i++)
#define roff(i,a,b) for(int i=(a);i>=(b);i--)
using namespace std;
const int MAXN=200+10,MOD=998244353; 
int T,n,len[MAXN],m[MAXN],dp[MAXN][MAXN][MAXN],f[MAXN][MAXN];
vector<int> G[MAXN][MAXN];
int qpow(int base,int p) {
	int ans=1;
	while(p) {
		if(p&1) ans=ans*base%MOD;
		base=base*base%MOD,p>>=1;
	}
	return ans;
}
int det(void) {
	int mul=1; int n=len[1];
	ffor(i,1,n) {
		if(!f[i][i]) ffor(j,i+1,n) if(f[j][i]) {swap(f[j],f[i]),mul=-mul;break;}
		if(!f[i][i]) return 0;
		int inv=qpow(f[i][i],MOD-2);
		ffor(j,i+1,n) {
			int mul=inv*f[j][i]%MOD;
			ffor(k,i,n) f[j][k]=(f[j][k]-mul*f[i][k])%MOD;
		}
	}
	ffor(i,1,n) mul=mul*f[i][i]%MOD;
	return (mul%MOD+MOD)%MOD;
}
signed main() {
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>T;
	while(T--) {
		cin>>n;
		ffor(i,1,n) cin>>len[i];
		ffor(i,1,n) ffor(j,1,len[i]) G[i][j].clear();
		memset(dp,0,sizeof(dp));
		ffor(i,1,n-1) cin>>m[i];
		ffor(i,1,n-1) {
			ffor(j,1,m[i]) {
				int u,v;
				cin>>u>>v;
				G[i][u].push_back(v);	
			}
		}
		ffor(i,1,len[n]) ffor(j,1,len[n]) dp[n][j][i]=(i==j);
		roff(i,n-1,1) ffor(k,1,len[i]) for(auto nxt:G[i][k]) ffor(des,1,len[n]) dp[i][k][des]=(dp[i][k][des]+dp[i+1][nxt][des])%MOD;
		ffor(i,1,len[1]) ffor(j,1,len[1]) f[i][j]=dp[1][i][j];
//		cout<<'\n';
//		ffor(i,1,len[1]) {
//			ffor(j,1,len[1]) cout<<f[i][j]<<' ';
//			cout<<'\n';	
//		}
		cout<<det()<<'\n';
	}
	return 0;
}