题解：双色染色

思路

合法染色的边界可按蓝色连通区域在某一分界线两侧的单调轮廓分类。固定分界位置后， 每条单调轮廓等价于一个允许横、纵移动的格路径，其数量可用组合数表示。还需把横向 分类与纵向分类相加，并减去被两种分类同时计算的情形。

做法

子任务 1：枚举染色

当 $nm\le20$ 时，用一个二进制数表示染色。逐行统计蓝色连续段数，逐列统计黄色 连续段数，仅当它们都恰为一时计数。

子任务 2：直接组合求和

记 $C(a,b)=\binom ab$。固定列分界 $x$ 后，四段单调边界依次产生四层求和：

$$A_i=\sum_{t=0}^i C(x-1+t,t),$$ $$B_i=\sum_{t=1}^i A_{t-1}C(n-t+x-1,n-t),$$ $$D_i=\sum_{t=1}^i B_tC(m-x-1+t,t),$$ $$E_i=\sum_{t=1}^i D_{t-1}C(m-x-1+n-t,n-t).$$

对所有 $x$ 累加 $E_n$，再交换 $n,m$ 计算另一方向。直接展开每个前缀和可通过 $n,m\le80$。

满分算法：滚动前缀和

上述四个式子的右端都是前缀和。对固定 $x$，从小到大扫描 $i$，即可让每层从前一项 $O(1)$ 转移，总复杂度降为 $O(nm)$。

两种方向同时计数的重叠项为

$$\sum_{i=1}^{n-1}\sum_{j=1}^{m-1} C(i-1+j,j)C(n-i+j-1,n-i) C(n-i-1+m-j,m-j)C(i+m-j-1,i).$$

用两方向之和减去重叠，再乘以关于上下次序的因子 $2$，即得答案。组合数使用阶乘和 逆阶乘在 $O(1)$ 时间计算。

复杂度

• 子任务 1：$O(2^{nm}nm)$ 时间，$O(1)$ 额外空间。
• 子任务 2：$O(nm(n+m))$ 时间，$O((n+m)^2)$ 空间。
• 满分算法：$O(nm)$ 时间，$O(n+m)$ 空间。

正确性证明

引理 1

固定一个方向和分界位置后，四层组合求和恰好计算该方向的全部合法单调边界。

证明。 每段边界是坐标单调格路径，选择横纵步的位置给出相应组合数。四段的端点 按顺序连接，逐层枚举连接点正对应 $A,B,D,E$ 四个求和；每个边界有唯一连接点组， 故不重不漏。证毕。

引理 2

横向分类与纵向分类的交集恰为重叠公式枚举的染色。

证明。 同时具有两种分界描述时，存在唯一内部交点 $(i,j)$。其四侧边界独立为四条 单调路径，方案数正是公式中的四个组合数之积；枚举所有内部交点覆盖且仅覆盖交集。 证毕。

定理

满分算法输出合法染色总数。

证明。 由引理 1，两次 part 分别计算两个方向的分类；由引理 2，减去重叠后得到 两方向并集。每个无向轮廓有上下两种次序，乘二后与全部合法染色一一对应。因此输出 正确。证毕。