题解：P14022 [ICPC 2024 Nanjing R] Bingo
_jimmywang_
·
·
题解
min-max 容斥。先排序，从小到大填进去。
设 A_{1},A_{2},\dots A_{n} 为每一行被填满的时候的最大的值（即最后一个被填进去的那个数）；B_{1},B_{2},\dots,B_{n} 为 每一列被填满的时候的最大的值。那么一种方案的答案就是
\min(\{A_1,A_2,\dots,A_n\}\cup\{B_1,B_2,\dots B_n\})\\=\sum_{S\subset\{A_1,A_2,\dots,A_n\}}\sum_{T\subset\{B_1,B_2,\dots B_n\}}(-1)^{|S|+|T|+1}\max(S\cup T)
你发现这个 \max(S\cup T) 在做的事情就是选定某些特定的行和列，求出这些格子里最后被填进去的数是什么。容易发现这个值只和被考虑到的格子数量有关，而这个格子数量只和 |S|,|T| 有关。因此我们可以改写这个式子为：
\sum_{i=0}^n\sum_{j=0}^m(-1)^{i+j+1}\binom{n}{i}\binom{m}{j}f(im+jn-ij)
这个式子复杂度已经对了，现在唯一的问题是算 $f(t)$。考虑枚举最后一个填进去的数是什么：
$$f(t)=\sum_{i=1}^{nm}a_i\binom{i-1}{t-1}t!(nm-t)!$$
这个式子的意义就是第 $i$ 个数是最有一个填进去的，前 $i-1$ 个数里挑 $t-1$ 填到剩下 $t-1$ 个格子里，这 $t$ 个数和剩下的 $nm-t$ 个数分别可以随便排序，所以乘上阶乘。
这个式子可以差卷积。做完了。