重修 LGV
OI wiki
一般用于不相交路径计数。
发现好像例题不多。
P6657 【模板】LGV 引理
有一个 \(n\times n\) 的棋盘，左下角为 \((1,1)\)，右上角为 \((n,n)\)，若一个棋子在点 \((x,y)\)，那么走一步只能走到 \((x+1,y)\) 或 \((x,y+1)\)。
现在有 \(m\) 个棋子，第 \(i\) 个棋子一开始放在 \((a_i,1)\)，最终要走到 \((b_i,n)\)。问有多少种方案，使得每个棋子都能从起点走到终点，且对于所有棋子，走过路径上的点互不相交。输出方案数 \(\bmod\ 998244353\) 的值。
两种方案不同当且仅当存在至少一个棋子所经过的点不同。
就是模板题。
发现只有 \(a_i\to b_i\) 一一对应才有可能，所以直接行列式求值即为答案。
点击查看代码
//We'll be counting stars.
#include
using namespace std;
#define IOS ios::sync_with_stdio(false)
#define fir first
#define sec second
#define mkp make_pair
#define pb emplace_back
#define mem(x,y) memset(x,y,sizeof(x))
#define For(i,j,k) for(int i=j;i<=k;i++)
#define Rof(i,j,k) for(int i=j;i>=k;i--)
#define Fe(x,y) for(int x=head[y];x;x=e[x].nxt)
#define ckmx(a,b) a=max(a,b)
#define ckmn(a,b) a=min(a,b)
#define fin(s) freopen(s,"r",stdin)
#define fout(s) freopen(s,"w",stdout)
#define file(s) fin(s".in");fout(s".out")
#define ll long long
const ll mod=998244353;
inline ll pw(ll x,ll y){ll r=1;while(y){if(y&1)r=r*x%mod;x=x*x%mod;y>>=1;}return r;}
inline void mad(ll &a,ll b){a=(a+b)%mod;while(a<0)a+=mod;}
inline void mmu(ll &a,ll b){a=(a*b)%mod;while(a<0)a+=mod;}
#define inv(a) pw(a,mod-2)
#define int long long
#define N 2000010
#define M 103
int f[N],ivf[N];
void init(){
f[0]=1;
For(i,1,N-1) f[i]=f[i-1]*i%mod;
ivf[N-1]=inv(f[N-1]);
Rof(i,N-1,1) ivf[i-1]=ivf[i]*i%mod;
}
inline int C(int x,int y){
return f[x]*ivf[y]%mod*ivf[x-y]%mod;
}
int a[M][M],n,m,A[M],B[M];
bool flag;
inline void swa(int x,int y){
flag^=1;
For(i,1,m) swap(a[i][x],a[i][y]);
}
int Det(){//行列式求值模板 P7112
flag=0;
int tmp=0;
For(i,1,m) For(j,i+1,m){
while(a[i][j]){
tmp=a[i][i]/a[i][j];
For(k,1,m) mad(a[k][i],-a[k][j]*tmp);
swa(i,j);
}
}
int ans=1;
For(i,1,m) mmu(ans,a[i][i]);
return flag?(mod-ans)%mod:ans;
}
void work(){
cin>>n>>m;
For(i,1,m) cin>>A[i]>>B[i];
For(i,1,m) For(j,1,m) a[i][j]=(A[i]<=B[j]?C(n-1+B[j]-A[i],n-1):0);
cout<>T;
while(T--)work();
return 0;}
CF348D Turtles
有一个 \(n\times m\) 的棋盘，其中某些格子可走，某些格子不可走。有两只海龟只能向下或向右走，求海龟从 \((1,1)\) 到 \((n,m)\) 路径不相交（除起点终点）的方案数取模之后的结果。
\(2\le n,m\le 3000\)
相当于一只从 \((2,1)\) 走到 \((n,m-1)\)，另一只 \((1,2)\) 走到 \((n-1,m)\)，反过来的话必定交叉。
所以我们
求完行列式即为答案（\(f\) 的值 \(O(nm)\) DP 求）。