最新要闻

广告

手机

iphone11大小尺寸是多少？苹果iPhone11和iPhone13的区别是什么？

iphone11大小尺寸是多少？苹果iPhone11和iPhone13的区别是什么？

 警方通报辅警执法直播中被撞飞：犯罪嫌疑人已投案

警方通报辅警执法直播中被撞飞：犯罪嫌疑人已投案

家电

  1. 首页
  2. 移动通信
  3. 内容

LGV引理

来源：博客园

LGV引理

定义 \(A\) 是起点集合 \(\{a_1,a_2,...,a_n\}\) 。


【资料图】

\(B\) 是终点集合 \(\{b_1,b_2,...,b_n\}\)。

定义 \(\omega(P)\) 为路径 \(P\) 每一条边权值的乘积，即 ：

\[\omega(P) = \prod_{e \in P}w_e\]

定义 \(e(a,b)\) 表示点 \(a\rightarrow b\) 所有路径 \(P\) 的 \(\omega(P)\) 之和，即：

\[e(a,b) = \sum_{P:a \rightarrow b}\omega(P)\]

定义 \(\sigma\) 为 \(1 \sim n\) 的一个任意全排列，定义 \(P_i\) 代表 \(a_i\rightarrow b_{\sigma_i}\) 一条路径。

设一个从 \(A\) 到 \(B\) 的路径集合 \(L=\{P_1,P_2,P_3,...,P_n\}\) 。

注意当 \(\sigma\) 一定时，路径集合 \(L\) 可能不同( \(a_i\rightarrow b_{\sigma(i)}\) 可能有多条路径)

(集合名称写成 \(L\) 是为了避免后文出现歧义)。

定义 \(t(L)\) 为关于路径集合 \(L\) 的全排列 \(\sigma\) 逆序对个数。

则定义：

\[\omega(L) = \prod_{P \in L}\omega(P)\]

那我们可以知道逆序对是偶数路径条数 \(-\) 逆序对是奇数路径条数答案是：

\[\sum_{L:A\rightarrow B} (-1)^{t(L)}\prod_{i = 1}^n\omega(P_i)\]

\(L\) 是路径均不相交的路径集合。

这个答案如何求呢？

设矩阵：

\[M = \begin{bmatrix}e(a_1,b_1)~~e(a_1,b_2)~...~e(a_1,b_n)\\ e(a_2,b_1)~~e(a_2,b_2)~...~e(a_2,b_n)\\ \vdots~~~~~~~~~~~~~~~\vdots~~~~~~~~~~~~~~~~~~~~\vdots\\ e(a_n,b_1)~~e(a_n,b_2)~...~e(a_n,b_n)\\ \end{bmatrix}\]

其实矩阵行列式就是答案：

\[det(M) = \sum_{L:A\rightarrow B} (-1)^{t(L)}\prod_{P_i \in L}\omega(P_i)\]

如何证明？

先考虑行列式的定义。

\[det(M) = \sum_{\sigma}(-1)^{t(\sigma)}\prod_i^ne(a_i,b_{\sigma(i)})\]

根据上文 \(e(a,b)\) 定义推导一下。

\[ \begin{aligned}&det(M)\\&=\sum_{\sigma}(-1)^{t(\sigma)}\prod_i^n\sum_{P_j:a_i \rightarrow b_{\sigma(i)}}\omega(P_j)\\&=\sum_{L:A\rightarrow B}(-1)^{t(\sigma)}\prod_{P_i \in L}\omega(P_i)\end{aligned} \]\[\]

设\(U\) 为不相交路径组，\(V\) 为相交路径组。

\[\sum_{L:A\rightarrow B}(-1)^{t(\sigma)}\prod_{P_i \in L}\omega(P_i)~~=\sum_{U:A\rightarrow B}(-1)^{t(\sigma)}\prod_{U_i \in U}\omega(U_i) + \sum_{V:A\rightarrow B}(-1)^{t(\sigma)}\prod_{V_i \in V}\omega(V_i)\]

假设一对相交路径：

\[a_i \rightarrow u \rightarrow b_i~~~~~~~~~~~a_j \rightarrow u \rightarrow b_j\]

必定存在一对相交路径：

\[a_i \rightarrow u \rightarrow b_j~~~~~~~~~~a_j \rightarrow u \rightarrow b_i\]

逆序对个数差 \(1\) ，一个为正一个为负抵消。

于是

\[\sum_{V:A\rightarrow B}(-1)^{t(\sigma)}\prod_{V_i \in V}\omega(V_i) = 0\]\[\Rightarrow \sum_{L:A\rightarrow B}(-1)^{t(\sigma)}\prod_{P_i \in L}\omega(P_i)=\sum_{U:A\rightarrow B}(-1)^{t(\sigma)}\prod_{U_i \in U}\omega(U_i)\]

得证

\[det(M) = \sum_{L:A\rightarrow B} (-1)^{t(L)}\prod_{P_i \in L}\omega(P_i)\]

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#define ll long longusing 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<>t;    while(t--){        // qk();        input();        cout<

关键词：