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\) 為相交路徑組，
假設一對相交路徑：
\[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<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;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/555387.html
標籤：其他
上一篇：SX130芯片的LoRa網關吞吐量是SX127芯片的多少倍？
下一篇：返回列表