[洛谷P5400][CTS2019]随机立方体

这个题感觉有点神仙。
我们可以先考虑方案数,最后再除掉$(nml)!$
首先原问题不太好直接考虑,容斥之后显然更容易一点,我们可以对于每一个i求出至少i个极大数的方案数,然后再$O(n)$容斥出答案。
那么考虑如果k个元素的位置和大小固定且均为极大值,怎么统计方案数。我们不妨令其从小到大排序,依次值为$x_1,x_2,x_3,..,x_k$,那么可以考虑每次取出最小的,将其影响的几个面删去,然后再考虑剩余的元素。由于删第i个元素时影响到的位置个数是固定且等价的,我们不妨设其为$s_i$($s_i=(n-i+1)(m-i+1)(l-i+1)-(n-i)(m-i)(l-i)$)。
设$t_i=\displaystyle\sum_{j=1}^i s_j$
那么此时方案为:
$\displaystyle\prod_{i=1}^k \binom{x_i-t_{i-1}-1}{t_i-t_{i-1}-1}(t_i-t_{i-1}-1)!$
如果只确定值的话只需要再枚举位置即可,第i个元素做的时候要乘上$(n-i+1)(m-i+1)(l-i+1)$
那么我们可以直接dp这个的东西,考虑从小到大枚举$x_i$,$f(i,j)$表示取到第i个元素,此时$x_i=j$的方案数。
这个dp可以用前缀和优化到$O(nml\min(n,m,l))$
然后神仙的地方就来了,这个dp手模一下会发现$f(i,j)=\frac{(j-1)^{\underline{t_i-1}}\prod_{k=1}^i (n-k+1)(m-k+1)(l-k+1)}{\prod_{k=1}^{i-1} t_k}$
证明的话就是数学归纳法。
那么我们不妨令答案中最大的$x_i$为$nml$(因为这个一定是极大的)。可以得到答案式子:
$\frac{1}{(nml)!} \displaystyle\sum_{j=k}^{min(n,m,l)} \frac{(nml-1)^{\underline{t_j-1}}\prod_{k=1}^j (n-k+1)(m-k+1)(l-k+1)}{\prod_{k=1}^{j-1} t_k} (nml-t_j)! \binom{j-1}{k-1} (-1)^{j-k}$
$=\frac{1}{nml} \displaystyle\sum_{j=k}^{min(n,m,l)} \frac{\prod_{k=1}^j (n-k+1)(m-k+1)(l-k+1)}{\prod_{k=1}^{j-1} t_k} \binom{j-1}{k-1} (-1)^{j-k}$
暴力即可,至于逆元可以统一预处理。时间复杂度$O(Tn+\lg MOD)$
代码:

Tagged with:

发表评论