老早就聽說，一直沒學，今天遇到一個LGV比較裸的題，特地學習一下
選自oi-wiki

定義：

e(u,v)表示u到v這條路徑上所有邊的邊權之積(路徑計數(shù)時，可以將邊權都設為1),很多路徑統(tǒng)計問題就是用到這一點

引理：

答案就是矩陣的行列式(可以用高斯消元來搞)

用法：

在路徑統(tǒng)計問題中，我們會將邊權設為1，e(u,v)常常用于表示從(a,b)走到(c,d)的方案數(shù)，一共要走sum=abs(c-a)+abs(d-b),其中挑選c-a步選擇向下走,即$C_{c?a+d?b}^{c?a}$
對于起點終點的選擇要具體情況具體分析，首先起點和終點不能是重復的，而且和原方案等價，多數(shù)采取平移。

例題：

2019牛客多校Monotonic Matrix
[P6657 【模板】LGV 引理]
hdu5852 Intersection is not allowed!
P7736-[NOI2021]路徑交點
CodeForces 348D Turtles

創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎勵來咯，堅持創(chuàng)作打卡瓜分現(xiàn)金大獎

總結

以上是生活随笔為你收集整理的LGV定理的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。