1700AC
jun头吉吉
·
·
个人记录
\Large \rm [AGC039F]\ Min\ Product\ Sum
这玩意当年是一个提高组模拟题/jy
首先考虑给了每行的最小值 \{x_i\} 和每列的最小值 \{y_i\} 怎么做，考虑把 x 和 y 扔到一个序列里面排序，然后从小往大取，假设现在取到了 t 然后之前已经有 i 行 j 列，那么如果 t 是行，那么贡献就是 t^{m-j} 否则是 t^{n-i}。
然后考虑对这个序列 \rm dp，记 f_{t,i,j} 表示处理完了 \le t 的所有数，已经有 i 行 j 列。但是这样无法保证每一行和列的最小值恰好就是我们 \rm dp 得到的东西。
再考虑一个容斥，钦定 c 行 d 列是大于我们的钦定的值，其它的是大于等于，容斥系数为 (-1)^{c+d}，那么这样容斥一波得到的结果就是我们希望的每行列的最小值恰好是我们钦定的结果了。然后我们就可以列出转移方程了：
\begin{aligned}
&f[t][i+a][j]\leftarrow \binom{n-i}{a}\times t^{a(m-j)}\times (k-t+1)^{aj}\times g[i][j]\\
&f[t][i][j+a]\leftarrow \binom{m-j}{a}\times t^{a(n-i)}\times (k-t+1)^{ai}\times g[i][j]\\
&f[t][i+a][j]\leftarrow \binom{n-i}{a}\times t^{a(m-j)}\times (k-t)^{aj}\times (-1)^a\times g[i][j]\\
&f[t][i][j+a]\leftarrow \binom{m-j}{a}\times t^{a(n-i)}\times (k-t)^{ai}\times (-1)^a\times g[i][j]
\end{aligned}
然后直接做就可以了，反正时限是 6s。