先不考虑 $a_{R,C}=V$ 的限制,考虑原问题,我们要找到 $k-1$ 条值域轮廓线(起点 $(n,0)$ 终点 $(0,m)$),使相互不越过。将第 $i$ 条向下、右平移 $i-1$ 格,变成了路径不交问题,可以 LGV 引理处理。
考虑 $a_{R,C}=V$ 的限制,其实是 $(R+V-2,C+V-2)$ 这个位置 可以放数,并且上侧折线数恰好 $V-1$ 条。那么枚举这条 $y=c-x$ 线上所有点(作为中转点),如果在上侧就多一个 $x$,最后某个起点到某个终点的方案是 $a+bx$ 的形式。只要插值就可以了。
时间复杂度 $O(k^2(n+m+k)+k^4)$。 提交记录:Submission #97792 - QOJ.ac。