要求恰有 $k$ 个极大的数，考虑钦定 $k$ 个极大的数，剩下的随意选取，记为 $F(k)$ ，那么有 $F(k) = \sum _ {i = k} \binom i k G(i)$ ，二项式反演后就可以得到答案。
考虑如何计算 $F(k)$ 。钦定了 $k$ 个极大数后，对于每个数都有 $3$ 个面受到影响，这是很麻烦的。但是如果我们确定了 $k$ 个数的大小，即按照升序统计答案，那么前面的对后面的没有影响。
任意一个面最多只能有一个极大值，即 $k \le \min (n, m, l)$ 。选择一个坐标 $(a, b, c)$ 后，面 $x = a, y = b, z = c$ 均无法被选择，那么选择 $i$ 个极大值后，可以选择的点有 $(n - i) (m - i) (l - i)$ 个，则共 $\prod _ {i = 0} ^ {k - 1} (n - i) (m - i) (l - i)$ 。注意，我们不仅确定了选择了那些位置，还确定了相对大小顺序。
钦定后，不受到影响的数有 $g (i) = (n - i) (m - i) (l -i)$ 个，受到影响的数有 $G(i) = n m l - g(i)$ 个。在总共的 $nml$ 个数中，我们选择 $G(i)$ 个数作为这些的值，共 $\binom {nml} {G(i)}$ 种。
考虑从小到大一层一层的计算，可以参考 cmd的博客 中图片，从外到内第 $i$ 层有位置 $g(i - 1) - g(i)$ ，可以选的数的个数为 $G(i)$ ，其中最大值是确定的，即从 $G(i) - 1$ 个数中选择 $g(i - 1) - g(i) - 1$ 个，方案数为 $(G(i) - 1) ^ {\underline {g(i - 1) - g(i) - 1}}$ 。发现 $(G(i) - 1) - (g(i - 1) - g(i) - 1) = G(i) + g(i) - g(i - 1) = nml - g(i - 1) = G(i - 1)$ 。 即方案数为 $\frac {(G(i) - 1)!} {G(i - 1)!}$ 。
其他的数 $g(k)$ 随便选，即 $g(k)!$ 。
那么
$$
\begin {aligned}
F(k) & = g(k)!\binom {nml} {G(k)} \prod _ {i = 0} ^ {k - 1} g(i) \prod _ {i = 1} ^ k \frac {(G(i) - 1)!} {G(i - 1)!} \\
& = \frac {(nml)!} {G(k)!} \prod _ {i = 0} ^ {k - 1} g(i) \prod _ {i = 1} ^ k \frac {(G(i) - 1)!} {G(i - 1)!} \\
& = \frac {(nml)!} {G(0)!\prod _ {i = 1} ^ k \frac {G(i)!}{G(i - 1)!}} \prod _ {i = 0} ^ {k - 1} g(i) \prod _ {i = 1} ^ k \frac {(G(i) - 1)!} {G(i - 1)!} \\
& = (nml)!\prod _ {i = 0} ^ {k - 1} g(i)\prod _ {i = 1} ^ k \frac {(G(i) - 1)!} {Gi!}\\
& = (nml)!\prod _ {i = 0} ^ {k - 1} g(i)\prod _ {i = 1} ^ k \frac 1 {Gi}\\
\end {aligned}
$$
最终答案为
$$
\sum _ {i = k} \binom i k (-1) ^ {i - k} \prod _ {j = 0} ^ {k - 1} g(j) \prod _ {j = 1} ^ k \frac 1 {G(i)}
$$
如果线性处理 $G$ 逆元，可以做到 $(T k)$ 。
查看代码
1 |
|