Luogu P8594

Luogu P8594 Solution

【形式化题意】

你有 \(1\times x\)（\(x\) 为任意正整数）的矩形各无穷多个和一个 \(2\times n\) 的网格，请求出恰好选择其中 \(k\) 个矩形（可以选择相同的矩形）不重不漏地铺满整个网格的方案数。矩形可以旋转。

\(n\leq 2\times 10^7,k\leq 5000\)

【解答】

评价：一道很不错的组合计数题，要运用许多技巧才能解决。

因为 \(k\leq 5000\)，所以我们可以尝试用 \(O(k^2)\) 的算法来解决这个问题。

首先确定我们要计算什么，定义状态是在有 \(i\) 个 \(1\times 2\) 的长方形竖着的，且将整个长条分成了 \(j\) 段的情况下的种类数。（并且，我们强制要求这 \(j\) 段中的每一段都是由横着的长方形填充的）

感性理解一下，这个是 \(i=3,j=3\) 的其中一种情况。而这些 \(2\times2, 1\times 2,4\times 2\) 的子矩阵都应该由横着的长方形来填充。

计算出这个子问题的答案，我们要分步解决。

问题一、这 \(i\) 个 \(1\times2\) 的竖着的长方形怎么放（确定这 \(i\) 个竖着的位置）

我们使用插空法。 设当前已经放好了这 \(i\) 个竖着的长方形，那么就是这 \(j\) 个段去选 \(i+1\) 个空（两端的空是允许使用的），所以这个问题就迎刃而解了。

那么显然是 \(\begin{pmatrix} i+1\\ j \end{pmatrix}\) 种。（\(i+1\ge j\)）

问题二、这 \(j\) 段的每一段怎么分配，也就是说每一段有多少列。

我们使用 插板法。 现在剩下了 \(n-i\) 列没有分配（\(n\) 列减去已经使用的竖着的 \(i\) 个），要分给 \(j\) 段，每一段不能为空。那么它就是有 \(n-i-1\) 个空，要插入 \(j-1\) 个板子。（因为不能为空，所以两端的空不能使用。）

那么就是 \(\begin{pmatrix} n-i-1\\ j-1 \end{pmatrix}\) 种。（\(n-i\ge j\)）

问题三、这 \(j\) 段的内部怎么分配

引理：对于一个 \(2\times n\) 的长方形，若有 \(x\) 个 \(1\times l\) 的长方形来填充，并且不允许竖着放，则有 \(\begin{pmatrix} 2n-2\\ x-2 \end{pmatrix}\) 种。

对于这个引理的解释：显然我们也可以用插板法。你可以看成 \(1\times (2\times n)\) 的长方形，因为他分成了两列，所以我们可以认为正中间的那个空天然地就放了一块板子。

于是，还剩下 \(2n-2\) 个空，还有 \(x-2\) 块板子要放（原有 \(2n-1\) 个空与 \(x-1\) 个板子，两个都确定了一个中间的）。

回到问题三原本的问题，我们不能一个一个地去考虑，要整体去考虑。（其实这就是范德蒙德卷积的思想。）

一共有 \(j\) 个段，设第 \(p\) 段要有 \(c_p\) 个横着的长方形来填充，其为 \(2\times d_p\) 的长方形，那么答案就是：

\(\sum_{c,d}\prod_{p=1}^{j}\begin{pmatrix} 2d_l-2\\c_l-2\end{pmatrix}\)

这样来求时间复杂度直接就爆了。但是我们要运用整体的思想。 一共有 \(\sum (2c_p-2)\) 个空，一共要插入 \(\sum (d_p-2)\) 块板子。答案就是
\(\begin{pmatrix} \sum (2c_p-2)\\ \sum (d_p-2) \end{pmatrix}\)

显然我们可以直接化简 \(\sum (2c_p-2)\) 和 \(\sum (d_p-2)\)，其分别为 \(2n-2i-2j\) 和 \(k-i-2j\)。（\(k\) 就是原题面里的，\(i\) 表示用了 \(i\) 个 \(1\times 2\) 的竖着的）

于是问题三的答案就是 \(\begin{pmatrix} 2n-2i-2j\\ k-i-2j \end{pmatrix}\)。实际上，这些在做的是在运用范德蒙德卷积。

对于范德蒙德卷积，这里就不做解释了。

【统计答案】

有了问题一，二，三的计算公式，我们可以直接推导出在有 \(i\) 个 \(1\times 2\) 的长方形竖着的，且将整个长条分成了 \(j\) 段的情况下的种类数，就是三个问题的公式相乘。

给定 \(i,j\)，其种类数为 \(\begin{pmatrix} 2n-2i-2j\\ k-i-2j \end{pmatrix}\begin{pmatrix} n-i-1\\ j-1 \end{pmatrix}\begin{pmatrix} i+1\\ j \end{pmatrix}\)。

直接去枚举 \(i\) 和 \(j\) 就可以了，因此，所有的答案是：

\(\sum_{i=0}^{k}\sum_{j=0}^{k}\begin{pmatrix} 2n-2i-2j\\ k-i-2j \end{pmatrix}\begin{pmatrix} n-i-1\\ j-1 \end{pmatrix}\begin{pmatrix} i+1\\ j \end{pmatrix}\)。

【代码细节】

由于 \(n\leq 2\times 10^7\)，所以要线性预处理逆元。这样可以 \(O(1)\) 求组合数。

这题卡空间，阶乘和逆元数组不要用 long long。

具体代码就不贴了，不难。