LGV引理

求有向无环图上不相交路径数。

设起点为 $A _ i$ ，终点为 $B _ i$ ，$x \to y$ 的方案数为 $e(x, y)$ 。

那么答案为
$$
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}
$$