LGV引理
定义 (A) 是起点集合 ({a_1,a_2,...,a_n}) 。
(B) 是终点集合 ({b_1,b_2,...,b_n})。
定义 (omega(P)) 为路径 (P) 每一条边权值的乘积，即 ：
定义 (e(a,b)) 表示点 (arightarrow b) 所有路径 (P) 的 (omega(P)) 之和，即：
定义 (sigma) 为 (1 sim n) 的一个任意全排列，定义 (P_i) 代表 (a_irightarrow b_{sigma_i}) 一条路径。
设一个从 (A) 到 (B) 的路径集合 (L={P_1,P_2,P_3,...,P_n}) 。
注意当 (sigma) 一定时，路径集合 (L) 可能不同( (a_irightarrow b_{sigma(i)}) 可能有多条路径)
(集合名称写成 (L) 是为了避免后文出现歧义)。
定义 (t(L)) 为关于路径集合 (L) 的全排列 (sigma) 逆序对个数。
则定义：
那我们可以知道逆序对是偶数路径条数 (-) 逆序对是奇数路径条数答案是：
(L) 是路径均不相交的路径集合。
这个答案如何求呢？
设矩阵：
其实矩阵行列式就是答案：
如何证明？
先考虑行列式的定义。
根据上文 (e(a,b)) 定义推导一下。
设 
(U) 为不相交路径组，(V) 为相交路径组。
假设一对相交路径：
必定存在一对相交路径：
逆序对个数差 (1) ，一个为正一个为负抵消。
于是
得证
P6657 【模板】LGV 引理 题解
题意描述
(n times n) 棋盘，(m) 个棋子，第 (i) 个棋子一开始放在 ((a_i,1)) ，最终要走到 ((b_i,n))。问有多少种方案，路径不能相交，求方案数。
保证 (1≤a_1≤a_2≤⋯≤a_m≤n，1≤b_1≤b_2≤⋯≤b_m≤n)。
题解
看到不相交，一眼 LGV ，我们看到保证部分，就可以知道他求的是逆序对数量为 0 的路径条数。并且有逆序对数量的路径条数一定为 0 ，就直接套模板了。
特别的，算 (e(a_i,b_j)) 可以通过 (binom {n - 1 + b_j - a_i} {n - 1})。
原理是有 (n-1) 条竖着走，有 (b_j - a_i) 条横着走，求一下组合数就可以了。
代码
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 2e6 + 10, M = 110,mod = 998244353;
int t, n, m, a[M], b[M];
ll pr[N], inv[N], s[M][M];
ll mpow(ll x, ll k)
{
ll ans = 1;
while(k)
{
if(k & 1) ans = ans * x % mod;
x = x * x % mod;
k >>= 1;
}
return ans;
}
void pre()
{
pr[0] = 1;
for(int i = 1; i <= N - 10; ++i)
pr[i] = pr[i - 1] * i % mod;
inv[N - 10] = mpow(pr[N - 10], mod - 2);
for(int i = N - 11; i >= 0; --i)
inv[i] = inv[i + 1] * (i + 1) % mod;
}
inline ll C(int a,int b)
{
if(a < b) return 0;
return pr[a] * inv[b] % mod * inv[a - b] % mod;
}
void input(){
cin>>n>>m;
for(int i = 1; i <= m; ++i)
cin>>a[i]>>b[i];
for(int i = 1; i <= m; ++i){
for(int j = 1; j <= m; ++j){
s[i][j] = C(n - 1 + b[j] - a[i],n - 1);
// cout<<s[i][j]<<' ';
}
// cout<<'n';
}
}
ll op(){
ll w = 1;
for(int i = 1; i <= m; ++i){
for(int j = i + 1; j <= m; ++j){
while(s[i][i]){
ll d = s[j][i] / s[i][i];
for(int k = i; k <= m; ++k){
s[j][k] = (s[j][k] - s[i][k] * d % mod + mod) % mod;
}
swap(s[i], s[j]);
w = -w;
}
swap(s[i], s[j]);
w = -w;
}
}
w = (w + mod) % mod;
for(int i = 1; i <= m; ++i){
w = w * s[i][i] % mod;
}
return w;
}
int main(){
pre();
cin>>t;
while(t--){
// qk();
input();
cout<<op()<<'n';
}
return 0;
}
文章来源: 博客园
- 还没有人评论，欢迎说说您的想法！
客服
