P5400 [CTS2019] 随机立方体
首先看到恰好非常不爽，考虑利用二项式反演转化为至少。令 \(f(i)\) 表示钦定有 \(i\) 个极大值的方案数，则答案为：
\[\frac{1}{(nml)!}\sum_{i} (-1)^{i-k}\binom{i}{k} f(i)
\]
下文为了方便，记 \(S=nml\)。现在我们的问题是怎么求 \(f(i)\)。首先我们先选出 \(i\) 个极大点，并且钦定好他们的大小顺序，这个的方案数是 \(n^{\underline i}m^{\underline i}l^{\underline i}\)，然后接下来会发现我们极大点会对一些点产生限制，而没有限制的点总共有 \((n-i)(m-i)(l-i)\) 个，我们给他们随便赋值即可，方案数为 \((nml)^{\underline{(n-i)(m-i)(l-i)}}\)。
现在的问题在于我们要求出对于极大点以及他们限制的点填数字的方案数。此时我们的难点在于每个最大值的限制是有交的，不好统计。我们考虑对于每个点，只考虑限制它的最小的极大点，这样的话每个极大点的限制就两两不交，且我们可以算出每个极大点的限制点数。如下图所示：
* * 3 *
* 2 * *
* * * *
* * * 1
这三个点分别是极大值点，我们现在来看每个点被哪个点限制：
3 2 3 1
2 2 2 1
* 2 3 1
1 1 1 1
平移一下可以得到：
* 3 2 1
3 3 2 1
2 2 2 1
1 1 1 1
那么实际上我们是可以轻松算出第 \(i\) 大的极大值对应限制的点数的。设 \(g(i)=(n-i)(m-i)(l-i)\)，那么第 \(i\) 小的极大点限制的点数就是 \(g(i-1)-g(i)\)，而此时我们前面已经填过了一些数，剩下的还有 \(g(0)-g(i)\) 个，而当前的极大点固定要填剩下的数中的最大值，所以方案数实际上是 \((g(0)-g(i)-1)^{\underline{g(i-1)-g(i)-1}}\)。
于是我们可以得出，对于选 \(i\) 个极大点的方案数为：
\[\begin{aligned}
&\prod_{j=1}^i(g(0)-g(j)-1)^{\underline{g(j-1)-g(j)-1}}\\
=&\prod_{j=1}^i \frac{(g(0)-g(j)-1)!}{(g(0)-g(j-1))!}\\
=&(g(0)-g(i)-1)! \prod_{j=1}^{i-1} \frac{1}{g(0)-g(j)}
\end{aligned}
\]
于是可以得出：
\[\begin{aligned}
f(i)&=n^{\underline i}m^{\underline i}l^{\underline i}(nml)^{\underline{(n-i)(m-i)(l-i)}}(g(0)-g(i)-1)! \prod_{j=1}^{i-1} \frac{1}{g(0)-g(j)}\\
&=n^{\underline i}m^{\underline i}l^{\underline i}\frac{g(0)!}{(g(0)-g(i))!}(g(0)-g(i)-1)! \prod_{j=1}^{i-1} \frac{1}{g(0)-g(j)}\\
&=n^{\underline i}m^{\underline i}l^{\underline i}g(0)!\prod_{j=1}^{i} \frac{1}{g(0)-g(j)}\\
\end{aligned}
\]
所以最终答案就是：
\[\begin{aligned}
&\frac{1}{(nml)!}\sum_{i} (-1)^{i-k}\binom{i}{k} f(i)\\
=&\frac{1}{(nml)!}\sum_{i} (-1)^{i-k}\binom{i}{k} n^{\underline i}m^{\underline i}l^{\underline i}g(0)!\prod_{j=1}^{i} \frac{1}{g(0)-g(j)}\\
=&\sum_{i} (-1)^{i-k}\binom{i}{k} n^{\underline i}m^{\underline i}l^{\underline i}\prod_{j=1}^{i} \frac{1}{g(0)-g(j)}\\
\end{aligned}
\]
预处理出 \(g(0)-g(j)\) 的逆元前缀积即可单次 \(O(n)\) 计算，而处理逆元可以用经典方法做到 \(O(n)\)，总复杂度 \(O(Tn)\)，可以通过。
