定理内容

对于一条路径 $P$，设 $\omega(P)=\prod \limits_{i\in \text{edge of }P}w_i$，其中 $w$ 是边权，$e(x,y)=\sum\limits_{\forall P:x\to y} \omega(P)$。

对于计数问题边权可以设置为 $1$，对于轮廓线 DP 其实边权也可以是一些奇奇怪怪的函数。

有起点集合 $A$ 和终点集合 $B$，那么假设有一个排列 $\sigma$，路径 $P_i$ 就是 $A_i\to B_{\sigma(i)}$。

最后，设 $t(\sigma)$ 为 $\sigma$ 的逆序对数量，LGV 引理证明的就是下面的方阵 $M$ 满足：

$\operatorname{Det}(M)=\sum\limits_{\forall S:A\to B}(-1)^{t(\sigma)}\prod\limits_{i=1}^n \omega(S_i)$

$M=\begin{vmatrix} e(A_1,B_1) & e(A_1,B_2) & \cdots & e(A_1,B_n)\\ e(A_2,B_1) & e(A_1,B_3) & \cdots & e(A_2,B_n)\\ \vdots & \vdots& \ddots &\vdots \\ e(A_n,B_1) & e(A_n,B_2) & \cdots & e(A_n,B_n) \end{vmatrix}$

证明

其中 $S$ 表示表示从 $A$ 到 $B$ 所有的不相交的路径 $P$。

首先考虑行列式的定义，即对于一个 $n\times n$ 的方阵 $A$，其行列式为：

$\operatorname{Det}(M)=\sum\limits_{\forall \sigma}(-1)^{t(\sigma)}\prod\limits_{i=1}^n a_{i,\sigma(i)}$

其中 $\sigma$ 是一个 $1$ 到 $n$ 的排列。

具体到上面的矩阵，显然其行列式为：

$\operatorname{Det}(M)=\sum\limits_{\forall \sigma}(-1)^{t(\sigma)}\prod\limits_{i=1}^n e(A_i,B_{\sigma(i)})$

根据 $e(x,y)$ 的定义，其显然可以转化为：

$\operatorname{Det}(M)=\sum\limits_{\forall \sigma} (-1)^{t(\sigma)}\prod\limits_{i=1}^n \sum\limits_{\forall P:A_i\to B_{\sigma(i)}}\omega(P)$

根据乘法原理，上式的 $\prod\limits_{i=1}^n \sum\limits_{\forall P:A_i\to B_{\sigma(i)}}\omega(P)$ 就相当求解的是在所有的 $\forall i\in[1,n]\cap \mathbb {Z}\mid A_i\to B_{\sigma(i)}$ 的路径中，所有可能的路径的组 $P$ 的 $\sum\limits_{i=1}^n \omega(P_i)$ 的加和。

所以就可以继续化简得到：

$\operatorname{Det}(M)=\sum\limits_{\forall \sigma} (-1)^{t(\sigma)} \sum\limits_{P=\sigma} \omega(P)$

还是根据乘法原理，有可以得到：

$\operatorname{Det}(M)=\sum\limits_{\forall P\color{black}:A\to B} (-1)^{t(\sigma)}\prod\limits_{i=1}^n \omega(P_i)$

观察上式与定理的区别，发现现在仅需证明对于所有有交的路径 $G$ 的贡献均为 $0$ 就可以证明原定里了。

要证明原定理成立，首先需要证明对于一个排列 $\sigma$ 满足交换 $i,j\in[1,n]\cap \mathbb{Z}\wedge i\ne j$ 一定会使 $\sigma$ 逆序对的奇偶性改变。

先证明交换相邻的元素序列的奇偶性会改变，这十分显然因为如果交换 $A_i,A_{i+1}$ 那么因为没有相同的元素所以 $A_i,A_{i+1}$ 之间必定会贡献一个逆序对的变化，而对于 $[1,i)$ 和 $(i+1,n]$ 的贡献都是一样的，所以 $t(\sigma)$ 的奇偶性必然改变。考虑更一般的情况，假设只能交换相邻的元素，交换 $A_i$ 与 $A_j$ 的贡献就是交换 $A_i,A_j-1$ 的贡献 $+2$（一开始把 $A_j$ 换到 $A_{j-1}$ 最后再换回来）。

我们可以一直将距离不断缩小直到 $j=i+1$，因为我们已经证明了交换 $A_i,A_{i+1}$ 会改变奇偶性所以要自然可以证明一个排列任意交换两个元素其逆序对的奇偶性偶会改变。

回到 LGV 引理的证明。

对于一个有交点的路径 $A_i\to B_i,A_j\to B_j$，假设其第一次相交于 $u$，也就是其路径形如 $A_i\to u\to B_i$ 和 $A_j\to u\to B_j$。这时候如果交换 $\sigma(i)$ 和 $\sigma(j)$ 那么就会发现另外一条相交的路径 $A_i\to u\to B_j$ 和 $A_j\to u\to B_i$。

显然两条路径 $P,P'$ 满足 $\omega(P)=\omega(P')$ 且因为上面的关于奇偶性的证明，有 $(-1)^{t(\sigma)}+(-1)^{t(\sigma')}$。

所以自然有结论：

$\sum\limits_{\forall G:A\to B} (-1)^{t(\sigma)}\prod \limits_{i=1}^n \omega(G_i)=0$

也就得到了：

$\operatorname{Det}(M)=\sum\limits_{\forall S:A\to B}(-1)^{t(\sigma)}\prod\limits_{i=1}^n \omega(S_i)$

本题的求解

因为这个题目保证 $1\leq a_1\leq a_2\leq \dots\leq a_m\leq n$，$1\leq b_1\leq b_2\leq \dots\leq b_m\leq n$，所以如果起点与终点并不是一一对应的，那么就一定会出现交点，也就是说有贡献的 $\sigma$ 都满足 $\sigma(i)=i$。

对于 $e(A_i,B_j)$ 使用组合数求解，直接输出 $\operatorname{Det}(M)$ 就可以了，时间复杂度 $O(n^3)$。

#include<iostream>
#define int long long 
using namespace std;
const int N=5e6+5,M=505,mod=998244353;
int ksm(int a,int b){
	int ans=1;
	while(b){
		if(b&1){
			ans=ans*a%mod;
		}
		b>>=1;
		a=a*a%mod;
	}
	return ans;
}
int n,m,a[M],b[M],inv[N],jc[N],f[M][M];
int C(int n,int m){
	if(n<m){
		return 0;
	}
	return jc[n]*inv[m]%mod*inv[n-m]%mod;
}
void solve(){
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		cin>>a[i]>>b[i];
	}
	for(int i=1;i<=m;i++){
		for(int j=1;j<=m;j++){
			f[i][j]=C(b[j]-a[i]+n-1,n-1);
		}
	}
	int flag=1;
	for(int i=1;i<=m;i++){
		for(int j=i+1;j<=m;j++){
			while(f[i][i]){
				int s=f[j][i]/f[i][i];
				for(int k=i;k<=m;k++){
					f[j][k]=(f[j][k]-s*f[i][k]+mod)%mod;
				}
				flag++;
				swap(f[i],f[j]);
			}
			flag++;
			swap(f[i],f[j]);
		}
	}
	int ans=1;
	for(int i=1;i<=m;i++){
		ans=(ans*f[i][i])%mod;
	}
	cout<<(ans*(flag%2?1:-1)+mod)%mod<<'\n';
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	jc[0]=1;
	for(int i=1;i<N;i++){
		jc[i]=jc[i-1]*i%mod;
	}
	inv[N-1]=ksm(jc[N-1],mod-2);
	for(int i=N-1;i>=1;i--){
		inv[i-1]=inv[i]*i%mod;
	}
	int T;cin>>T;
	while(T--) solve();
	return 0;
}