LGV 引理

2023-02-24 12:10:55 来源：博客园

$\text{Conclusion}$

~~显然只需要这个~~

$\text{LGV}$ 引理

只适用于有向无环图

(资料图片)

定义 $\omega(P)$ 表示 $P$ 这条路径上所有边权的乘积$e(u,v)$ 表示 $u$ 到 $v$ 每一条路径 $P$ 的 $\omega(P)$ 之和

起点集合 $A$ 与终点集合 $B$ 大小一样一组不相交路径 $S$：$S_i$ 表示一条从 $A_i$ 到 $B_{p_i}$ 的路径，满足 $S_i$ 和 $S_j(i!=j)$ 没有公共交点$\tau(p)$ 表示排列 $p$ 的逆序对

考虑矩阵 $M$

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

有定理

\[\det(M)=\sum_{S:A\to B}{(-1)^{\tau(S)}\prod_{i=1}^{n}\omega(S_i)}\]

其中 $\sum_{S:A\to B}$ 表示每一组不相交的路径

然后就是做题理解了

$P6657$ 【模板】LGV 引理注意到网格图中 $a_i,b_i$ 递增，那么满足不相交的路径组的只能是 $a_i\rightarrow b_i$排列 $S$ 只能是 $(1,2,...,n)$，所以直接行列式就是答案

$\text{Code}$

#include #define IN inlineusing namespace std;typedef long long LL;const int P = 998244353, N = 2e6 + 5;int a[105], b[105], c[105][105], fac[N], ifac[N], m, n;IN int C(int n, int m){return (LL)fac[n] * ifac[n - m] % P * ifac[m] % P;}IN int fpow(int x, int y){int s = 1; for(; y; y >>= 1, x = (LL)x * x % P) if (y & 1) s = (LL)s * x % P; return s;}IN int Det() {int ct = 0, res = 1;for(int i = 1; i <= m; i++) {int z = 0;for(int j = i; j <= m; j++) if (c[j][i]) z = j;if (!z) return 0;if (z ^ i) {for(int j = 1; j <= m; j++) swap(c[i][j], c[z][j]);ct ^= 1;}int inv = fpow(c[i][i], P - 2);for(int j = i + 1; j <= m; j++) {int d = (LL)c[j][i] * inv % P;for(int k = i; k <= m; k++) c[j][k] = (c[j][k] - (LL)c[i][k] * d % P) % P;}res = (LL)res * c[i][i] % P;}return (ct ? (P - res) % P : (res + P) % P);}int main() {fac[0] = fac[1] = ifac[0] = ifac[1] = 1;for(int i = 2; i <= N - 5; i++) fac[i] = (LL)fac[i - 1] * i % P, ifac[i] = (LL)ifac[P % i] * (P - P / i) % P;for(int i = 2; i <= N - 5; i++) ifac[i] = (LL)ifac[i] * ifac[i - 1] % P;int t; scanf("%d", &t);for(; t; --t) {scanf("%d%d", &n, &m);for(int i = 1; i <= m; i++) scanf("%d%d", &a[i], &b[i]);for(int i = 1; i <= m; i++)for(int j = 1; j <= m; j++)c[i][j] = (a[i] > b[j] ? 0 : C(b[j] - a[i] + n - 1, n - 1));printf("%d\n", Det());}}

$P7736$ [NOI2021] 路径交点考虑 $K=2$，行列式即答案$K>2$ 发现行列式相乘即为答案原因：记 $f_i,g_i$ 表示矩阵 $i$ 偶排列和奇排列的答案，那么行列式相乘 $(f_i-g_i)(f_{i+1}-g_{i+1})=f_ig_i+g_ig_{i+1}-f_ig_{i+1}-f_{i+1}g_i$ 恰好为答案

于是就有 $75$ 分了行列式有结论 $|A||B|=|AB|$即两矩阵行列式的积为两矩阵积的行列式这样就没了另一种考虑是把邻接矩阵乘起来，直接应用 $LGV$ 引理便是对的了

$\text{Code}$

#include  #define IN inlineusing namespace std;typedef long long LL;const int N = 205, P = 998244353;int ctn[N], ctm[N];IN void Add(int &x, int y){if ((x += y) >= P) x -= P;}IN int fpow(int x, int y){int s = 1; for(; y; y >>= 1, x = (LL)x * x % P) if (y & 1) s = (LL)s * x % P; return s;}struct Matrix {    int n, m, a[N][N];    IN Matrix(int _n = 0, int _m = 0) {        n = _n, m = _m;        for(int i = 0; i <= n; i++)            for(int j = 0; j <= m; j++) a[i][j] = 0;    }    IN Matrix operator * (const Matrix &b) {        Matrix c(n, b.m);        for(int i = 1; i <= n; i++)            for(int k = 1; k <= m; k++)                for(int j = 1; j <= b.m; j++)                    Add(c.a[i][j], a[i][k] * b.a[k][j] % P);        return c;    }    IN int Det() {        int fl = 0, res = 1;        for(int i = 1; i <= n; i++) {            int t = 0;            for(int j = i; j <= n; j++) if (a[j][i]) {t = j; break;}            if (!t) return 0;            if (t ^ i) {                for(int j = 1; j <= n; j++) swap(a[i][j], a[t][j]);                fl ^= 1;            }            int inv = fpow(a[i][i], P - 2);            for(int j = i + 1; j <= n; j++) {                t = (LL)inv * a[j][i] % P;                for(int k = i; k <= n; k++) a[j][k] = ((LL)a[j][k] - (LL)a[i][k] * t % P + P) % P;            }            res = (LL)res * a[i][i] % P;        }        return (fl ? P - res : res);    }}ret, A;int main() {    int t; scanf("%d", &t);    for(; t; --t) {        int K; scanf("%d", &K);        for(int i = 1; i <= K; i++) scanf("%d", &ctn[i]);        for(int i = 1; i < K; i++) scanf("%d", &ctm[i]);        for(int i = 1; i < K; i++) {            A = Matrix(ctn[i], ctn[i + 1]);            for(int j = 1, u, v; j <= ctm[i]; j++) scanf("%d%d", &u, &v), ++A.a[u][v];            if (i == 1) ret = A; else ret = ret * A;        }        printf("%d\n", ret.Det());    }}

关键词：邻接矩阵

LGV 引理

\(\text{Conclusion}\)

\(\text{LGV}\) 引理