给定一张 dag，其中前 \(k\) 个点是关键点，其余的点是非关键点，保证关键点之间没有边。
记 \(f[l,r]\) 表示，做从 \([1,k]\) 到 \([l,r]\) 的点的最大流的流量，对每个 \(i\) 计算，有多少个 \(l,r\) 满足 \(f[l,r]=i\)。
\(k \le 50,n\le 10^5,m\le 10^6\)
做最大流的过程其实类似寻找不交路径。
判断是否存在一个满流，我们可以使用 LGV 引理解决。
给边随机赋权然后算出带符号带权不交路径数，如果答案不为 0 就能认为有解。
也就是说，令 \(v_i\) 表示点 \(i\) 到点 \([1,k]\) 的路径数组成的向量，如果 \(v_l,\cdots,v_r\) 线性无关，就可以认为到 \([l,r]\) 是满流的。
做前缀线性基就行了。总复杂度 \(O(nk^2+mk)\)。
标签：满流,10,le,路径,问题,经典,LGV,关键点 From： https://www.cnblogs.com/havzriu/p/17132700.html