题解 P6750 【『MdOI R3』Pekka Bridge Spam】

JohnVictor · 2020-08-11 22:11:55 · 题解

放上官方题解，自认为这题还是不错的，主要是对于结构的观察而不是推式子。

性质 1

将这个图分成 nm 个 2 \times 2 个正方形，那么每个正方形中恰好有一个 1 \times 2。

证明：称 S 为所有被 1 \times 2 覆盖的格子的集合，那么 |S|=2mn。每个这样的 2 \times 2 中至多有两个格子属于 S。

然而所有 4mn 个格子中，恰好有一半的格子属于 S。所以每个 2 \times 2 中恰好 2 个，构成一个 1 \times 2。

从左上角的格子开始依次考虑，可以证明这些就是所有的攻城锤。

根据这个性质，称一个上述的分割中的 2 \times 2 的方格为 上，下，左，右 之一，取决于 1 \times 2 在它中的位置。

性质 2

一个 上 的方格的上方的方格也是 上 的，右边是 上 或者 右，左边是 上 或者 左。其他四种方格类似。

证明显然。

那么，结合以上两条性质，这个图大概是长这样的：

注意到，如果现在就要推式子等方法计算的话，这个生成函数肯定是二元的形式，难以计算，可以用矩阵做到 \Theta(n^6 \log m) 的复杂度，不详细说明。

这一步需要极高的技巧，相当于因式分解了那个难以刻画的二元生成函数。

用两条路径刻画这个图，一条从左上到右下，一条从左下到右上：

那么分成的四块就恰好是 上，下，左，右。

现在这题变成：左上走到右下，每次向右或者向下，有些地方不能走，求方法数。

不能走是因为有 k 个指定的位置，那么这些会限制这条路径。

当然，现在还没有明确说明哪些地方不能走，这里说清楚，下面的例子主要考虑左上到右下的路径。

限制就是，所有 下 的方格和所有 左 的方格和剩下两种方格被这条路径分成两半，也就是，如果把下和左看成 1，其余看成 2，那么这条路径将 1 与 2 分成两个部分。

现在让这个方格表左下为 (0,0)，右上为 (m,n)。如果一个 1 类方格的左下角为 (p,q)，那么这条路径不能经过任何 x\le p 并且 y \le q 的点，对于 2 类方格类似。下面的图表明了一种可能的能走与不能走的位置。

这里，红色的点表示不能走的点，绿色的线是一条合法的路径，黄色的线把能走到的地方分成了几个矩形。

矩形未必要有长与宽（可以为 0），可能用 s\times t 的点阵（ s,t \ge 1）来形容更加合适，下面 点阵 和 矩形 都代表这个意思。

这些矩形是有特殊要求的，不难发现不能走的地方构成了两个简单多边形，这两个多边形的边有水平的和竖直的，用竖直的边分割这个网格图得到了图中所示的矩形，后面的方法会说明为什么要这么分，可以通过上面的图更好的理解这些矩形是怎么刻画出来的。

当然，刻画这些矩形需要将所有放好的块排序并且利用单调栈维护，细节比较多，这里不细说。

考虑最基本的 dp 以及一个没有限制的图，令 dp[i][j] 为到 (i,j) 的合法路径数，那么 dp[i][j]=dp[i][j-1]+dp[i-1][j]。

这个式子可以化成 dp[i][j]=\sum_{k=1}^jdp[i-1][k]，也就是一个前缀和的形式。

注意到，如果按照上面的方式将合法区域划分为矩形，那么每个长为 t 的点阵就相当于做 t-1 次前缀和。

我们用到生成函数的知识，如果假设第 i 列（横坐标为 i 的所有点）从上到下的 dp[i][j](0 \le j \le n) 构成生成函数 F_i(x)=\sum dp[i][j]x^j，其中 0 \le i \le m，我们有递推式：