2020-2021:teams:i_dont_know_png:potassium:lgv_lemma
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 | |||
|
2020-2021:teams:i_dont_know_png:potassium:lgv_lemma [2020/05/15 17:44] potassium |
2020-2021:teams:i_dont_know_png:potassium:lgv_lemma [2020/05/22 20:09] (当前版本) potassium fix typos |
||
|---|---|---|---|
| 行 3: | 行 3: | ||
| 更完整的定义见[[https://oi-wiki.org/graph/lgv/|OI-wiki]]，这里给出一个应用较多的狭义定义（即 $\omega(P)=1$ 的情况）。 | 更完整的定义见[[https://oi-wiki.org/graph/lgv/|OI-wiki]]，这里给出一个应用较多的狭义定义（即 $\omega(P)=1$ 的情况）。 | ||
| - | 设起始点集合为 $A=\{a_1,a_2,...,a_n\}$ ，终止点集合为 $B=\{b_1,b_2,...,b_n\}$ ，在一个起止点有唯一确定排列路径集的 DAG 上， $A\rightarrow B$ 的不相交路径集 $S$ 的个数可以用行列式 $\det(M)$ 表示，其中矩阵 $M$ 为 | + | 设起始点集合为 $A=\{a_1,a_2,\ldots,a_n\}$ ，终止点集合为 $B=\{b_1,b_2,\ldots,b_n\}$ ，在一个起止点有唯一确定排列路径集的 DAG 上， $A\rightarrow B$ 的不相交路径集 $S$ 的个数可以用行列式 $\det(M)$ 表示，其中矩阵 $M$ 为 |
| $${\begin{pmatrix}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{pmatrix}}$$ | $${\begin{pmatrix}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{pmatrix}}$$ | ||
| 行 27: | 行 27: | ||
| ===== 应用 ===== | ===== 应用 ===== | ||
| - | 由于单纯容斥求和的复杂度是指数级，而求行列式可以用高斯消元 $\mathcal{O}(n^3)$ 算出，因此可以使用此引理快速计算从起点集合到终点集合不相交路径个数。 | + | 由于单纯容斥求和的复杂度是指数级，而求行列式可以用高斯消元 $O(n^3)$ 算出，因此可以使用此引理快速计算从起点集合到终点集合不相交路径个数。 |
| 模板题：[[http://acm.hdu.edu.cn/showproblem.php?pid=5852|HDU5852]] | 模板题：[[http://acm.hdu.edu.cn/showproblem.php?pid=5852|HDU5852]] | ||
2020-2021/teams/i_dont_know_png/potassium/lgv_lemma.1589535857.txt.gz · 最后更改: 2020/05/15 17:44 由 potassium
