首先是考虑按行列建一个二分图出来，然后一个合法解一定使得这张二分图的最大流等于 \(\sum\limits_{i=1}^mb_i\) 。
考虑最大流-最小割定理，发现就是求所有使得整张图的最小割等于 \(\sum\limits_{i=1}^mb_i\) 的方案数。
考虑假设给出了一组 \(a_i\) 怎么判断是否合法，由于最小割一定能取到 \(\sum\limits_{i=1}^mb_i\) ，那么我们只需要看有没有其它方案花费小于这个值即可。
假设强制断掉 \(i\) 条源点到行的边， \(j\) 条列到汇点的边，那么剩下的点不连通一定会割掉 \((n-i)*(m-j)\) 条中间的边，由于是求最小割因此应当取前 i 小的 a 和前 j 小的 b 来割掉。
那么把 \(a,b\) 排序，记 \(sa,sb\) 为其前缀和，那么这张图合法的条件就是 \(\min\limits_{i,j\ge0}\{sa_i+sb_j+(n-i)*(m-j)\}\ge\sum\limits_{i=1}^mb_i\) 。
然后就设 \(f_{i,j,k}\) 表示当前选了前 i 小的 a 边，所有 a 边的长度不超过 j ，且和为 k 的方案数，对于每个 i 我们预处理出最小的 i 条 a 边的长度和最小值来限制转移就行了。
code
原文：https://www.cnblogs.com/ldxcaicai/p/12497009.html