P8114 [Cnoi2021] 六边形战士

传送

非常好玩的题！

首先你大概率看过一些“无字证明”，其中很经典的是这个：

证明：用若干个边长为 \(1\)，顶角为 \(60\) 度的菱形拼成一个边长为 \(n\) 的正六边形，三个方向的菱形个数一定相等。

这是一个经典的无字证明，虽然前置的说明要费很大功夫，不过你不关心这个。你只要知道一种拼法可以对应一种三维空间中的方块摆放方式就好了。

而这个结论和题有什么关系呢？如果你看过一些小视频或者论文什么的，就会发现，这张匹配的图怎么和定理的一种证明方式这么像！

（当然没看过也没关系）于是你可以把每一种匹配对应成一种菱形的拼法，再对应到方块的摆放方式。由此你得到了经过转化后的题意：

在一个长 \(a\) 宽 \(b\) 高 \(c\) 的盒子内放置若干个边长为 \(1\) 的正方体，且每个正方体下方，后方，左方均没有空位，求放置的方案数。

此时你发现高度 \(\ge\) 一个值的区块是联通的，于是你想到了分高度考虑。具体地，将我们的摆放方式一层一层剖开，并在边缘处划线，俯视图就像这样：

然后就变成了一个左下到右上的计数问题，于是你通过将路径向左上方平移一格的方式将其分离，变成一个可以直接行列式做的结论题，并得到答案就是：

\[\begin{vmatrix} \binom{a+b}{a} & \binom{a+b}{a-1} & \cdots&\binom{a+b}{a-c+1}\\ \binom{a+b}{a+1}&\binom{a+b}{a}&\cdots&{a+b\choose a+2-c}\\ \vdots&\vdots&\ddots&\vdots\\ \binom{a+b}{a+c-1}&\binom{a+b}{a+c-2}&\cdots&\binom{a+b}{a} \end{vmatrix} \]

此时你写出了高斯消元求行列式的 \(O(n^3)\) 做法，并获得了 \(70\) 分！

但是你并不满足于此，于是你开始推式子，设我们要求的行列式为 \(A\)。我们发现 \(A\) 的每一列都有大量的公因式，所以我们把它提出来：

\[\det(A)=(-1)^{\frac{c(c+1)}{2}} \det(A')\prod_{i=1}^{c}\frac{(a+b)!}{(a+c-i)!(b+i-1)!} \]

其中 \(A'_{i,j}=\prod_{k=j+1}^{c}(a+k-i)\prod_{k=2}^{j}(k-b-1-i)\)。

然后这个东西怎么化呢？你又阅读了一遍题面，发现出题人给了你一个公式：

Krattenthaler's formula
\(\displaystyle\det\left(\prod\limits_{k=2}^j(x_i+a_k)\prod\limits_{k=j+1}^n(x_i+b_k)\right)_{i,j=1}^{n}=\prod\limits_{1\le i<j\le n}{(x_i-x_j)}\prod\limits_{2<i\le j\le n}(a_i-b_j)\)。

你发现这个式子的格式和 \(A'\) 的格式刚好契合！于是你得到了 \(\det(A')\)。

\(\det(A')=\prod_{1\le i<j<c}(j-i)\prod_{2\le i\le j\le c}(a+b+j-i-1)\)

\[\begin{aligned} \det(A)&=(-1)^{\frac{c(c+1)}{2}}\prod_{1\le i<j<c}(j-i)\prod_{2\le i\le j\le c}(a+b+j-i-1)\prod_{i=1}^{c}\frac{(a+b)!}{(a+c-i)!(b+i-1)!}\\ &=\prod_{i=1}^{c-1}i!\prod_{i=1}^{c-1}(a+b+i)^{\underline{i}}\prod_{i=1}^{c}\frac{(a+b)!}{(a+c-i)!(b+i-1)!}\\ &=\prod_{i=1}^{c-1}i!\prod_{i=1}^{c-1}\frac{(a+b+i)!}{(a+b)!}\prod_{i=1}^{c}(a+b)!\prod_{i=1}^{c}\frac{1}{(a+c-i)!(b+i-1)!}\\ &=(a+b)!\prod_{i=1}^{c-1}i!\prod_{i=1}^{c-1}(a+b+i)!\frac{\prod_{i=0}^{a-1}i!\prod_{i=0}^{b-1}i!}{\prod_{i=0}^{a+c-1}i!\prod_{i=0}^{b+c-1}i!}\\ &=\frac{\prod_{i=0}^{a-1}i!\prod_{i=0}^{b-1}i!\prod_{i=0}^{c-1}i!\prod_{i=0}^{a+b+c-1}i!}{\prod_{i=0}^{a+b-1}i!\prod_{i=0}^{b+c-1}i!\prod_{i=0}^{c+a-1}i!} \end{aligned} \]

你发现这个式子可以线性时间内计算！于是这道题就做完了。

另附一个相关的视频：link