P6657-[模闆]LGV 引理

正題

題目連結:https://www.luogu.com.cn/problem/P6657

題目大意

給出\(n\times n\)的棋盤，\(m\)個起點第\(i\)個為\((1,a_i)\)，對應\(m\)個終點第\(i\)個為\((n,b_i)\)。

求有多少條選出\(m\)條四聯通路徑的方案使得沒有路徑有交點。

\(2\leq n\leq 10^6,1\leq m\leq 100,1\leq T\leq 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\n",dec(m));
	}
	return 0;
}