[CF848D] Shake It!

\(f(i, j)\)：\(S \to T\) 除去 \(S, T\) 有 \(i\) 个点，最大流为 \(j\) 的方案数。

\(g(i, j)\)：\(S \to U \to T\) 除去 \(S, T\) 有 \(i\) 个点，最大流为 \(j\) 的方案数。

\(f\) 向 \(g\) 转移：\(f(a, b) \times f(c, d) \to g(a + c + 1, \min(b, d))\)。

当前 \(a + c + 1\)，DP 计算整一行，枚举 \(a\) 确定 \(c\)，枚举 \(b, d\)。单行计算 \(O(n^3)\)，总共 \(O(n^4)\)。

\(g\) 向 \(f\) 转移需要按顺序转移，否则会算重。

对于同一个 \(g(c, d) = x\)，假设选了 \(k\) 次，相当于 \(k\) 个不区分的小球放入 \(x\) 个有区分的容器，可以不放，可以放多个，贡献为 \(\binom{x+k-1}{k}\)。

因为算 \(g\) 的时候，只需要上一行的 \(f\)。用这一行的 \(g\) 直接去更新这一行以及后面的 \(f\)，此后当前行的 \(f\) 就被确定了。

有效的 \((i, j, k)\) 是 \(O(n^2)\) 的（官解声称是 \(O(n^2\log n)\)），那么这一部分也是 \(O(n^4)\) 的。

\[\sum_{i = 1}^n \sum_{j = 1}^n \lfloor\min(n / i, n / j)\rfloor = \sum_{k = 1}^n \sum_{i = 1}^n \sum_{j = 1}^n [n / i \ge k][n / j \ge k] = \sum_{k=1}^n \lfloor n/k \rfloor^2 = O(n^2) \]

初始 \(f(0, 1) = 1\)。注意 \(f\) 的第二维最大可以是 \(n + 1\)。