P8114 [Cnoi2021]六边形战士 解题报告

P8114 [Cnoi2021]六边形战士 解题报告：

题意

给定一个三条边分别有 \(a,b,c\) 个六边形的六边形网络，求网络上所有边组成的二分图的完美匹配数量。

\(1\leqslant a,b,c\leqslant 10^6\)。

分析

非人力可及的巨大神仙题，膜拜 bzy。

考虑将匹配按照朝向分成三类：平、朝上、朝下，将三种匹配按照类型染上不同的颜色，然后考察其对应的三角形网络：

（图来自 Solara570-在二维世界中解决看似立体的平面问题）

可以证明染色方法可以与平面的立方体凸堆叠一一对应。

考察高度 \(v\) 与高度 \(v+1\) 的分界线，将这 \(c\) 条分界线画出来，可以发现路径 \(i\) 可以与路径 \(i+1\) 重叠，但是不能越过。

（图，以及下面的图都来自官方题解）

将第 \(i\) 条路径向右上平移 \(i-1\) 格，可以得到一个新的网格，可以发现此时已经转化成 LGV 能解决的问题了，直接列出矩阵，求行列式即可做到立方复杂度了。

列出矩阵，容易发现每个出发点到每个结束点的距离都是 \(a+b\)，且第 \(i\) 个出发点和第 \(j\) 个到达点的横向距离为 \(a+(x-y)\)：

\[ans=\det(M)\\M=\begin{bmatrix}{a+b\choose a}&{a+b\choose a-1}&\cdots&{a+b\choose a+1-c}\\{a+b\choose a+1}&{a+b\choose a}&\cdots&{a+b\choose a+2-c}\\\vdots&\vdots&\ddots&\vdots\\{a+b\choose a+c-1}&{a+b\choose c-2}&\cdots&{a+b\choose a}\end{bmatrix} \]

然后开始推式子：

\[\det(M)=\det(M')\times\prod_{i=1}^c\frac{(a+b)!}{(a+c-i))!(b+i-1)!}\\M_{i,j}'=\prod_{k=j+1}^c(a+k-i)\prod_{k=2}^j(b+i-k+1) \]

根据题面提供的公式，我们考虑将 \(M'\) 的元素向其转换：

\[\det(\prod_{k=2}^j(x_i+a_k)\prod_{k=j+1}^m(x_i+b_k))_{i,j=1}^n=\prod_{1\leqslant i

下面是一些 dirty work：

\[\det(M') \]