题解：P13757 【MX-X17-T6】Selection

设该二维数组为 $a$。钦定前 $k$ 个数组大于等于后 $n-k$ 个数组，最后乘上 $\begin{pmatrix}n\\k \end{pmatrix}$ 即可。

发现前 $k$ 个数组大于等于后 $n-k$ 个数组的充要条件是对于任意 $1$ 到 $m$ 之间的 $j$，满足 $\min\limits_{i=1}^{k} a_{i,j}$ 比 $\max\limits_{i=k+1}^{n} a_{i,j}$ 大。

发现大于不是很好维护，于是考虑总方案数减去等于的情况。设数组 $b=\min\limits_{i=1}^{k} a_{i,j}$。钦定前 $k$ 个数组中有 $x$ 个数组为 $b$，后 $n-k$ 个数组有 $y$ 个数组也为 $b$，那么剩余的 $n-x-y$ 个数组的每一维是相对独立的。枚举 $\min$ 和 $\max$ 的分界 $i$，贡献为 $(\sum\limits_{i=1}^{v}i^{k-x}(v-i+1)^{n-k-y})^m$。然后再乘上 $\begin{pmatrix}k\\x \end{pmatrix} \begin{pmatrix}n-k\\y \end{pmatrix}$ 以及转移系数 $(-1)^{x+y+1}$。设 $f_{x,y}=\begin{pmatrix}k\\x\end{pmatrix}\begin{pmatrix}n-k\\y\end{pmatrix}(\sum\limits_{i=1}^{v}i^{k-x}(v-i+1)^{n-k-y})^m (-1)^{x+y+1}$，那么答案就是总方案数减去 $\sum\limits_{x=1}^k\sum\limits_{y=1}^{n-k} f_{x,y}$。

考虑如何计算总方案数。注意，如果我们直接把 $(\sum\limits_{i=1}^{v}i^{k}(v-i+1)^{n-k})^m$ 当做总方案数，那么可能会出现某一个维度 $j$ 上存在某个 $\min$ 和 $\max$ 的分界点 $c$，使得 $\min\limits_{i=1}^{k} a_{i,j} \geq c \geq c-1 \geq \max\limits_{i=k+1}^{n} a_{i,j}$，从而被 $c$ 和 $c-1$ 重复计算导致算重的情况。所以这里要使用点边容斥，把每一个这样的 $c$ 减掉，这样是能够做到补充不漏的。总方案数即为 $((\sum\limits_{i=1}^{v}i^{k}(v-i+1)^{n-k})-(\sum\limits_{i=1}^{v-1}i^{k}(v-i)^{n-k}))^m$。

这样，我们做到了 $\Theta(n^2\log m+nv)$。瓶颈在于求 $\sum\limits_{i=1}^vi^{x}(v-i+1)^{y}$ 的形式。设其为 $g_{x,y}$。有：