不是很难，比较考验熟练程度（可惜还是没法自己做出来 /kk）。
首先，设 \(N=nml\)，并认为 \(n\leqslant m, l\)。
发现直接算比较难算，又看到题面中“恰好”两字，不难想到二项式反演。
我们设 \(f_i\) 为钦定了 \(i\) 个极大的格子，剩下随便填的方案数。则有 \[ ans=\frac{\sum\limits_{i=k}^n\binom{i}{k}(-1)^{i-k}f(i)}{N!} \] 所以我们只需要对 \(i=k\rightarrow n\) 求出 \(f_i\)。
设 \(g_i\) 为选出 \(i\) 个极大点后受到影响（也就是与至少一个极大点的某一维坐标相等）的所有点的数量，\(b_i\) 为选出 \(i\) 个极大点的方案数，\(h_i\) 为给定 \(g_i\) 个数，往 \(g_i\) 个点里填且满足题意的方案数。
那么有 \[ f_i=\binom{N}{g_i}(N-g_i)!b_ih_i \] 即我们先选出 \(g_i\) 个要填的数，然后剩下的数随便填，然后我们钦定格子的方案数为 \(b_i\)，往格子里填数的方案数为 \(h_i\)。
对于 \(g\)，有 \(g_i=N-(n-i)(m-i)(l-i)\)，即用所有数减去三维坐标都不与任何一个点相同的点的个数。
显然 \(b_i=\frac{\prod\limits_{j=0}^{i-1}(n-j)(m-j)(l-j)}{i!}\)，也就是你选第 \(j\) 个数时候的三维坐标的方案数，因为极大点是无编号的所以要除以 \(i!\)，或者可以写成 \(\binom{n}{i}\binom{m}{i}\binom{l}{i}(i!)^2\)。
对于 \(h\)，我们考虑按照极大点上的数的大小从小到大添加极大点和与其关联的点。即我们考虑从 \(h_{i-1}\) 递推出 \(h_i\)。首先由于我们强制从小到大填极大点，所以当前填的极大点上的数一定比任何其它点的数都大的，然后我们考虑新关联的点的填法（注意有的点可能与不止一个极大点某一维坐标相同），具体地，如果我们知道一开始有 \(s\) 个点，这次新增的有关联的点（不包括极大点）的个数为 \(r\)，则有 \[ h_i=i(s+1)^{\overline{r}}h_{i-1} \] 其中 \((s+1)^{\overline{r}}\) 表示 \(s+1\) 的 \(r\) 次上升幂，即 \((s+1)(s+2)\dots (s+r)\)
因为我们这里要填的所有点和之前的点以及这次新增的点（除了极大点）之间都没有大小要求，所以我们可以任意插空，这样插入第一个点有 \(s+1\) 个空，第二个有 \(s+2\) 个，以此类推。然后要乘一个 \(i\) 是因为我们这里固定了大小顺序，需要补上。
我们注意到，其实 \(s=g_{i-1}\)，\(r=g_i-g_{i-1}-1\)，注意有个 \(-1\) 是因为要去掉极大点。这样就有 \[ h_i=i\frac{(g_i-1)!}{g_{i-1}!}h_{i-1} \] 然后我们一路推下去，可以得到 \(h\) 的通项公式 \[ h_i=i!(g_i-1)!\prod\limits_{j=1}^{i-1}\frac{1}{g_j} \] 把 \(b,h\) 带入，则有 \[ f_i=\frac{N!}{g_i!(N-g_i)!}(N-g_i)!\frac{\prod\limits_{j=0}^{i-1}(n-j)(m-j)(l-j)}{i!}i!(g_i-1)!\prod\limits_{j=1}^{i-1}\frac{1}{g_j} \] 为了方便我们在这里就把 \(N!\) 除掉，并且化简可得 \[ f_i=\prod_{j=0}^{i-1}(n-j)(m-j)(l-j)\prod_{j=1}^{i}\frac{1}{g_j} \] 这个式子很好从 \(f_{i-1}\) 递推出来。然后如果对于每个 \(i\) 都用快速幂求出 \(g_i\) 的逆元，总复杂度是 \(O(Tn\log p)\) 的，难以通过，我们考虑先算出来 \(\prod g_i\) 的逆元，然后算一下前缀积和后缀积一乘就可以 \(O(1)\) 求出 \(\frac{1}{g_i}\) 了。
据同机房神仙 @jiqimao 说可以把不等关系转化成一个外向树的拓扑序个数问题，这样可以简化推出 \(h\) 的过程，本质上是一样的。
代码：
1 |
|