令$ w(P) $表示路径 $ P$ 的所有边权之积，\(e(u,v)\) 表示所有 \(u\) 到 \(v\) 的路径 \(w(P)\) 之和，令：
\[M= \begin{bmatrix} e(A_1,B_1) \quad e(A_1,B_2) \quad ... \quad e(A_1,B_n) \\ e(A_2,B_1) \quad e(A_2,B_2) \quad ... \quad e(A_2,B_n) \\ ... \\ e(A_n,B_1) \quad e(A_n,B_2) \quad ... \quad e(A_n,B_n) \end{bmatrix} \]\(M\) 的行列式即为所有从 \(A_i\) 到 \(B_i\) 的路径不交的所有方案个数。
感性理解：如果两条路径相交，那么将相交点后的路径交换两条路径仍然相交，但在行列式中逆序对中的奇偶性变化，两者路径相加值为0 。于是之剩下不交的路径。
详细证明见 oiwiki。
关于 $ w(P) $ 的理解：
- 路径计数时此边能/否走即赋值为1/0，即 \(e(u,v)\) 表示所有 \(u\) 到 \(v\) 的路径条数。
- 生成函数？长大后再学习吧！
点击查看代码
#include<bits/stdc++.h>
using namespace std;
#define int long long
inline int rd(){
int f=1,j=0;
char w=getchar();
while(!isdigit(w)){
if(w=='-')f=-1;
w=getchar();
}
while(isdigit(w)){
j=j*10+w-'0';
w=getchar();
}
return f*j;
}
const int N=1000010,M=2000000,K=110;
const int mod=998244353;
int fps[M+10],inv[M+10];
inline int C(int x,int y){return (x<0||y<0||x<y)?0:fps[x]*inv[y]%mod*inv[x-y]%mod;}
inline int pw(int x,int y){
int ansn=1;
while(y){
if(y&1)ansn=ansn*x%mod;
x=x*x%mod,y/=2;
}
return ansn;
}
int n,m,a[K],b[K];
int f[K][K];
void pri(){
for(int i=1;i<=m;i++){
for(int j=1;j<=m;j++)cout<<f[i][j]<<" ";
cout<<"\n";
}
cout<<"\n";
return ;
}
void work(){
n=rd(),m=rd();
for(int i=1;i<=m;i++)a[i]=rd(),b[i]=rd();
for(int i=1;i<=m;i++){
for(int j=1;j<=m;j++){
f[i][j]=(a[i]>b[j])?0:C(n-1+b[j]-a[i],b[j]-a[i]);
// cout<<i<<" "<<j<<":"<<n-1+b[j]-a[i]<<" "<<b[j]-a[i]<<"-"<<C(n-1+b[j]-a[i],b[j]-a[i])<<":"<<f[i][j]<<"\n";
// cout<<f[i][j]<<" ";
}
// cout<<"\n";
}
int k=1;
for(int i=1;i<m;i++){
// cout<<"wk:"<<i<<"\n";
// pri();
int p;
for(p=i;p<=m;p++)if(f[p][i])break;
if(p==m+1){
printf("0\n");
return ;
}
swap(f[p],f[i]),k*=-1;
for(int j=i+1;j<=m;j++){
if(!f[j][i])continue;
p=f[j][i]*pw(f[i][i],mod-2)%mod;
for(int o=i;o<=m;o++)f[j][o]-=f[i][o]*p%mod,f[j][o]=(f[j][o]+mod)%mod;
}
}
for(int i=1;i<=m;i++)k=k*f[i][i]%mod;
printf("%lld\n",abs(k));
return ;
}
signed main(){
fps[0]=inv[0]=1;
for(int i=1;i<=M;i++)fps[i]=fps[i-1]*i%mod;
inv[M]=pw(fps[M],mod-2);
for(int i=M-1;i>=1;i--)inv[i]=inv[i+1]*(i+1)%mod;
int T=rd();
while(T--)work();
return 0;
}