蒙德里安的噩梦 题解

· · 题解

你需要先特判 n\le2 或 m\le2 的情况。

结论1

合法的方案中不存在下图所示的形状：

无论 ① 处的骨牌是横着放还是竖着放都会使得短边相接。

结论2

合法的方案中不存在下图所示的形状：

① 处的骨牌竖着放都会使得短边相接，横着放会形成结论1中的形状。

因为不会有长边拼在一起的连续的三块骨牌，让我们把两块长边拼在了一起形成了 2\times2 的正方形的骨牌称为配对骨牌，把剩下的骨牌称为未配对骨牌。

结论3

如果出现了下图所示的形状：

合法的方案中骨牌一定按下图放置。

首先 ① 处的骨牌一定是横着放的，否则会使得短边相接，于是变成下图的形状。

如果 ② 处的骨牌是横着放置的。

那么 ③ 处的骨牌一定是竖着放的，否则会使得短边相接。

④ 处的骨牌一定是竖着放的，否则会使得形成结论1中的形状。

同理 ⑤ 处的骨牌一定是横着放的，⑥ 处的骨牌一定是竖着放的，⑦ 处的骨牌一定是横着放的，⑧ 处的骨牌一定是竖着放的……骨牌无限向外延伸，方案一定不合法。所以 ② 处的骨牌一定是竖着放置的。对称的位置也同理。

结论4

如果有一组配对骨牌，他们的短边两侧一定是方向不同的骨牌或者边缘。

① 处的骨牌只能这样放，否则会使得短边相接或者形成结论1的形状。对称的位置也同理。

结论5

如果有一个未配对骨牌，他的长边两侧一定是方向不同的配对骨牌或者边缘。

如果 A 是一个未配对骨牌，考虑 ① 处的骨牌怎么放，他不能是竖着放的，不然会和骨牌 A 配对，或者和 A 形成结论3的形状，也会导致 A 配对。所以 ① 处的骨牌一定是横着放的。

其他三个位置的骨牌同理。

结论6

横着的未配对骨牌和竖着的未配对骨牌不会同时出现。

假设我们有一个竖着的未配对骨牌。

① 处的骨牌一定是横着放的，否则会使得短边相接。假设他是靠左放置的。

② 处的骨牌一定是竖着放的，否则会使得短边相接。

骨牌 A 一定是未配对骨牌，否则会形成结论1中的形状。

于是竖着的未配对骨牌会一直向上下延伸直到碰到边缘，可以看作是一条从上边缘到下边缘的路径。横着的未配对骨牌会一直向左右延伸直到碰到边缘，可以看作是一条从左边缘到右边缘的路径。如果两者同时存在一定会在中间相交，这是不可能的。

结论7

一个合法的方案可以被横着或者竖着分成若干层，每一层中有相同数量的未配对骨牌。

我们可以先确定第一层中的所有未配对骨牌的位置，由结论4,5,6不难证明相邻的未配对骨牌之间一定是若干组配对骨牌。然后未配对骨牌向下一层延伸，下一层的未配对骨牌数量一定与上一层相同，下一层的未配对骨牌之间也一定是若干组配对骨牌。便可归纳得到结论。

正解

我们把每一层中的每组配对骨牌或者未配对骨牌看成一个节点，那么每条未配对骨牌的的路径一定是每一层的一个节点走向下一层的上一个或者下一个节点的，并且所有的路径是不相交的。因为 k\ge\frac{3}{2}(n+m-200)，所以一条边缘上的未配对骨牌最多只有 592 个，于是我们可以用 LGV 引理解决这个问题。

（该图对应着结论七中的方案）

如果 n 是层数，m 是每一层的节点数，那么可以使用反射容斥在 O(\frac{n}{m}) 的时间复杂度内求出从第一层的某一个节点到最后一层的某一个节点的方案数，如果 c 是每层的未配对骨牌数，那么总时间复杂度就是 O(\frac{n}{m}c^2+c^3)。因为有 c\le m 所以时间复杂度不超过 O(nc+c^3)，可以通过本题。