P6657-[模板]LGV 引理

正题

题目链接:https://www.luogu.com.cn/problem/P6657

---

题目大意

给出(n imes n)的棋盘，(m)个起点第(i)个为((1,a_i))，对应(m)个终点第(i)个为((n,b_i))。

求有多少条选出(m)条四联通路径的方案使得没有路径有交点。

(2leq nleq 10^6,1leq mleq 100,1leq Tleq 5)

---

解题思路

既然是引理我直接上证明了，设矩阵(A)中(A_{x,y})为第(x)个起点走到第(y)个起点的所有路径权值乘积和（这题里面为(1)）。

然后答案就是（所有方案的路径权值乘积）这个矩阵的行列式。

具体证明是容斥但是我不会。

时间复杂度(O(n+Tm^3))

---

code

#include<cstdio>
#include<cstring>
#include<algorithm>
#define ll long long
using namespace std;
const ll N=2e6+10,P=998244353;
ll T,n,m,fac[N],inv[N],b[110],c[110],a[110][110];
ll C(ll n,ll m)
{return fac[n]*inv[m]%P*inv[n-m]%P;}
ll Path(ll x,ll y){
	if(b[x]>c[y])return 0;
	return C(c[y]-b[x]+n-1,n-1);
}
ll power(ll x,ll b){
	ll ans=1;
	while(b){
		if(b&1)ans=ans*x%P;
		x=x*x%P;b>>=1;
	}
	return ans;
}
ll dec(ll n){
	ll ans=1,f=1;
	for(ll i=1;i<=n;i++){
		for(ll j=i;j<=n;j++){
			if(a[j][i]){
				if(j!=i)swap(a[i],a[j]),f=-f;
				break;
			}
		}
		ans=ans*a[i][i]%P;
		ll inv=power(a[i][i],P-2);
		for(ll j=i;j<=n;j++)a[i][j]=a[i][j]*inv%P;
		for(ll j=i+1;j<=n;j++){
			ll rate=P-a[j][i];
			for(ll k=i;k<=n;k++)
				(a[j][k]+=rate*a[i][k]%P)%=P;
		}
	}
	return ans;
}
signed main()
{
	scanf("%lld",&T);inv[1]=1;
	for(ll i=2;i<N;i++)inv[i]=P-inv[P%i]*(P/i)%P;
	fac[0]=inv[0]=1;
	for(ll i=1;i<N;i++)
		fac[i]=fac[i-1]*i%P,inv[i]=inv[i-1]*inv[i]%P;
	while(T--){
		scanf("%lld%lld",&n,&m);
		for(ll i=1;i<=m;i++)
			scanf("%lld%lld",&b[i],&c[i]);
		for(ll i=1;i<=m;i++)
			for(ll j=1;j<=m;j++)a[i][j]=Path(i,j);
		printf("%lld
",dec(m));
	}
	return 0;
}