HDU 5852 Intersection is not allowed! ( 2016多校9、不相交路径的方案、LGV定理、行列式计算 )

小程序：扫一扫查出行
【扫一扫了解最新限行尾号】
复制小程序

题目链接

题意 : 给定方格中第一行的各个起点、再给定最后一行与起点相对应的终点、问你从这些起点出发到各自的终点、不相交的路径有多少条、移动方向只能向下或向右

分析 :

首先对于多起点和多终点的不相交路径、有一个LGV定理

实际上就是 n^2 构造矩阵、再计算其行列式

矩阵的构造方法可以看看这个 ==> Click here

那么接下来就是确定各自路径的方案数了

这是一个经典问题

这里需要求解组合数、用预处理阶乘逆元的方法即可求出

#include<bits/stdc++.h>#define LL long longusing namespace std;;;LL Fac_inv[Comb_Maxn];LL Fac[Comb_Maxn];inline void Comb_init(){ Fac_inv[] = Fac[] = ; Fac_inv[] = ; ; i<Comb_Maxn; i++) Fac[i] = Fac[i-] * (LL)i % mod; ; i<Comb_Maxn; i++) Fac_inv[i] = (LL)(mod - mod / i) * Fac_inv[mod % i] % mod; ; i<Comb_Maxn; i++) Fac_inv[i] = Fac_inv[i-] * Fac_inv[i] % mod;}LL Comb(int n, int m){ return Fac[n] * Fac_inv[m] % mod * Fac_inv[n-m] % mod; }const int maxm = 1e2;LL Mat[maxm+][maxm+];int turn,n;void gcd(LL a,LL b,LL &d,LL &x,LL &y){ ,y=; else{ ++turn; gcd(b,a%b,d,y,x); y-=x*(a/b); }}LL det(LL n){ LL tmp1[maxm+],tmp2[maxm+]; LL ans=; ;i<=n;++i){ ;j<=n;++j){ ){ LL A=Mat[i][i],B=Mat[j][i],d,x,y; turn=; gcd(A,B,d,x,y); ;k<=n;++k) tmp1[k]=Mat[i][k],tmp2[k]=Mat[j][k]; ;k<=n;++k) Mat[i][k]=(x*tmp1[k]+y*tmp2[k])%mod; A/=d,B/=d; ) x=B,y=-A,ans=-ans%mod;else x=-B,y=A; ;k<=n;++k) Mat[j][k]=(x*tmp1[k]+y*tmp2[k])%mod; } } ans=ans*Mat[i][i]%mod; } ) ans+=mod; return ans;}int A[maxm], B[maxm];int main(void){ Comb_init(); int nCase; scanf("%d", &nCase); while(nCase--){ int n, k; scanf("%d %d", &n, &k); ; i<=k; i++) scanf("%d", &A[i]); ; i<=k; i++) scanf("%d", &B[i]); ; i<=k; i++){ ; j<=k; j++){ int a, b; a = n-+B[j]-A[i]; b = n-; ; || b < ) Mat[i][j] = ; else Mat[i][j] = Comb(a, b); } } printf("%lld\n", det(k) % mod); } ;}