题解：P10698 [SNCPC2024] 最大流

考虑 LGV 引理，由于 LGV 的条件是点不交，将边拆成点，每个点所有入边向所有出边连边。

建 $k$ 个虚点，向 $1$ 的所有出边连边。给每条边赋一个随机权值 $w_{i,j}$，设 $A_{i,j}$ 表示第 $j$ 个虚点到第 $i$ 条边的路径权值乘积和。设 $x$ 的入边集合即为 $S$，出边集合为 $T$，对于所有 $i\in T$，$A_i=\sum w_{j,i}A_j$。$x$ 的答案为 $S$ 中 $i$ 的 $A_i$ 组成的矩阵的秩。

但是这样如果出度入度都很大就会爆炸。考虑将 $S$ 中的向量求出一组线性基 $B$，那么每个 $A_j$ 都可以表示为若干个 $B_x$ 的和，独立的随机数的和仍然是随机数，因此直接令 $A_i=\sum w_{j,i}B_j$ 即可。

实现时维护每个点入边向量的线性基即可。

复杂度 $O((n+m)k^2)$。