• 欢迎光临~

# LGV 引理

### (LGV) 引理

[M = begin{pmatrix}e(a_1,a_2) 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) \ …… \ e(a_n,b_1) e(a_n,b_2) … e(a_n,b_n) end{pmatrix} ]

(det(M)=sum_{P:A->B} (-1)^{t(P)} prod_{i=1}^n w(P_i))

[det(M) = sum_{r} (-1)^{tau (r)}prod _{i =1}^n e(a_i,b_{r_i}) = sum_{r}(-1)^{tau (r)}prod_{i=1}^n sum_{P:a_i->b_{r_i}} w(P) ]

(sum_r (-1)^{tau (r)}prod_{i=1}^n sum_{P:a_i->b_{r_i}}w(P) = sum_r (-1)^{tau (r)}sum_{P=r}w(P)=sum_{P:A->B}(-1)^{t(P)}prod_{i=1}^n w(P_i))

(U) 为不相交路径组，(V) 为相交路径组，则：

[sum_{P:A->B}(-1)^{t(P)}prod_{i=1}^n w(P_i) = sum_{U:A->B} (-1)^{t(U)}prod_{i=1}^n w(U_i)+sum_{V:A->B}(-1)^{t(V)}prod_{i=1}^n w(V_i) ]

[sum_{V:A->B}(-1)^{t(V)}prod_{i=1}^n w(V_i) = 0 ]

[w(P) = w(P'),t(P)=t(P')±1 ]

### 例题

(CF348D) (Turtles)

(2leq n,mleq 3times 10^3)

(Sol)

(code)

``````#include <bits/stdc++.h>
using namespace std;
const int N = 3e3 + 10, mod = 1e9 + 7;
{
int s = 0, w = 1;
char ch = getchar();
while(ch < '0' || ch > '9') { if(ch == '-') w *= -1; ch = getchar(); }
while(ch >= '0' && ch <= '9') s = s * 10 + ch - '0', ch = getchar();
return s * w;
}
char mp[N][N];
int n, m, dp[N][N];
inline int f(int x1, int y1, int x2, int y2)
{
if(mp[x1][y1] == '#' || mp[x2][y2] == '#') return 0;
memset(dp, 0, sizeof(dp)), dp[x1][y1] = 1;
for(register int i = 1; i <= x2; i++)
for(register int j = 1; j <= y2; j++)
if(mp[i][j] == '.') (dp[i][j] += dp[i - 1][j]) %= mod, (dp[i][j] += dp[i][j - 1]) %= mod;
return dp[x2][y2];
}
int main()
{
for(register int i = 1; i <= n; i++) scanf("%s", mp[i] + 1);
int f11 = f(1, 2, n - 1, m), f12 = f(1, 2, n, m - 1), f21 = f(2, 1, n - 1, m), f22 = f(2, 1, n, m - 1);
int ans = ((1ll * f11 * f22 % mod - 1ll * f21 * f12 % mod) % mod + mod) % mod;
printf("%dn", ans);
return 0;
}
``````

(LuoGu P6657) ([)模板(]) (LGV) 引理

(T) 组数据，每组给出一个 (ntimes n) 的棋盘，棋子从 ((x,y)) 一步只能走到 ((x+1,y))((x,y+1)) ，有 (m) 个棋子，初始时第 (i) 个放在 ((1,a_i))，有 (m) 个终点，第 (i) 个终点是 ((n,b_i)) 。求出有多少种方案，能使每个棋子都能从起点走到终点，且对于所有的棋子它们的路径不交，答案对 (998244353) 取模。

(1leq Tleq 5,2leq nleq 10^6,1leq mleq 100,1leq a_1leq a_2leq … leq a_mleq n,1leq b_1 leq b_2leq … leq b_m leq n)

(Sol)

[e_{a_i,b_j} = begin{Bmatrix}binom{b_j-a_i+n-1}{n-1} b_jgeq a_i \ 0 otherwise end{Bmatrix} ]

(code)

``````#include <bits/stdc++.h>
#define int long long
using namespace std;
const int M = 1e2 + 10, N = 2e6 + 10, lim = 2e6, mod = 998244353;
{
int s = 0, w = 1;
char ch = getchar();
while(ch < '0' || ch > '9') { if(ch == '-') w *= -1; ch = getchar(); }
while(ch >= '0' && ch <= '9') s = s * 10 + ch - '0', ch = getchar();
return s * w;
}
int T, n, m;
int x[M], y[M], e[M][M];
int fac[N], inv[N];
inline int power(int x, int k)
{
int res = 1;
while(k){
if(k & 1) res =  res * x % mod;
x = x * x % mod, k >>= 1;
}
return res;
}
inline void initial()
{
fac[0] = inv[0] = 1;
for(register int i = 1; i <= lim; i++) fac[i] = fac[i - 1] * i % mod;
inv[lim] = power(fac[lim], mod - 2);
for(register int i = lim - 1; i >= 1; i--) inv[i] = inv[i + 1] * (i + 1) % mod;
}
inline int C(int x, int y) { return x < y ? 0 : fac[x] * inv[y] % mod * inv[x - y] % mod; }
inline int det()
{
int res = 1, f = 1;
for(register int j = 1; j <= m; j++){
for(register int i = j; i <= m; i++){
if(!e[i][j]) continue;
if(i != j) swap(e[i], e[j]), f *= -1; //行列式交换
break;
}
if(!e[j][j]) return 0;
res = res * e[j][j] % mod;
int tem = power(e[j][j], mod - 2);
for(register int k = j; k <= m; k++) e[j][k] = e[j][k] * tem % mod;
for(register int i = j + 1; i <= m; i++)
for(register int k = j, t = e[i][j]; k <= m; k++)
e[i][k] = ((e[i][k] - t * e[j][k] % mod) % mod + mod) % mod;
}
return (res * f + mod) % mod;
}
signed main()
{
initial();
while(T--){
for(register int i = 1; i <= m; i++) x[i] = read(), y[i] = read();
for(register int i = 1; i <= m; i++)
for(register int j = 1; j <= m; j++) e[i][j] = (x[i] <= y[j]) ? C(y[j] - x[i] + n - 1, n - 1) : 0;
printf("%dn", det());
}
return 0;
}
``````

(LuoGu P7736) ([NOI2021]) 路径交点

(T) 组数据，每组给出 (k) 层点，第 (i) 层点有 (n_i) 个，其中 (n_1=n_k,n_1leq n_ileq 2n_1)。第 (i(1leq i<k)) 层的点仅会向第 (i + 1) 层的点连 (m_i) 条有向边，第 (k) 层点不向任何点连边。对于两条路径 (P,Q)，设它们在第 (j) 层的连边为 ((P_j,P_{j+1}),(Q_j,Q_{j+1}))，则称这两个路径在第 (j) 层有交点，当且仅当：

[(P_j - Q_j)(P_{j+1}-Q_{j+1})<0 ]

(2leq k,n_1leq 100,1leq Tleq 5)

(Sol)

[det(M) = sum_{r} (-1)^{tau (r)}prod _{i =1}^n e(a_i,b_{r_i}) ]

(code)

``````#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 3e2 + 10, mod = 998244353;
{
int s = 0, w = 1;
char ch = getchar();
while(ch < '0' || ch > '9') { if(ch == '-') w *= -1; ch = getchar(); }
while(ch >= '0' && ch <= '9') s = s * 10 + ch - '0', ch = getchar();
return s * w;
}
struct Matrix{
int n, m, a[N][N];
Matrix operator * (const Matrix &x){
Matrix res; res.n = n; res.m = x.m;
for(register int i = 1; i <= n; i++){
for(register int j = 1; j <= x.m; j++){
for(register int k = 1; k <= m; k++) add = (add + a[i][k] * x.a[k][j] % mod) % mod;
}
}
return res;
}
inline void clear(int x, int y){
n = x, m = y;
for(register int i = 1; i <= n; i++)
for(register int j = 1; j <= m; j++) a[i][j] = 0;
}
}A, B;
inline int power(int x, int k)
{
int res = 1;
while(k){
if(k & 1) res = res * x % mod;
x = x * x % mod, k >>= 1;
}
return res;
}
int T, n[N], m[N], e[N][N];
inline int det(int m)
{
int res = 1, f = 1;
for(register int i = 1; i <= m; i++)
for(register int j = 1; j <= m; j++) e[i][j] = A.a[i][j];
for(register int j = 1; j <= m; j++){
for(register int i = j; i <= m; i++){
if(!e[i][j]) continue;
if(i != j) swap(e[i], e[j]), f *= -1; //行列式交换
break;
}
if(!e[j][j]) return 0;
res = res * e[j][j] % mod;
int tem = power(e[j][j], mod - 2);
for(register int k = j; k <= m; k++) e[j][k] = e[j][k] * tem % mod;
for(register int i = j + 1; i <= m; i++)
for(register int k = j, t = e[i][j]; k <= m; k++)
e[i][k] = ((e[i][k] - t * e[j][k] % mod) % mod + mod) % mod;
}
return (res * f + mod) % mod;
}
signed main()
{
while(T--){
for(register int i = 1; i <= k; i++) n[i] = read();
for(register int i = 1; i < k; i++) m[i] = read();
A.clear(n[1], n[2]);
for(register int i = 1, x, y; i <= m[1]; i++)
for(register int i = 2; i < k; i++){
B.clear(n[i], n[i + 1]);
for(register int j = 1, x, y; j <= m[i]; j++)