官方题解（中文整理）

基于 Nelson Huang 的官方题解整理。

一维情况下，合法行长什么样

先只看一行或一列。设其中每个格子都是 \(+1\) 或 \(-1\)，并要求任意连续子段和都在 \([-1,2]\) 内。

可以先得到三个简单结论：

• 不可能出现两个连续的 -，否则子段和会是 \(-2\)
• 不可能出现三个连续的 +，否则子段和会是 \(3\)
• 一行中至多出现一次相邻的 ++

第三点是关键。如果某一行里出现了两处 ++，那么取它们之间的整段，和一定会达到 \(3\)。

因此，一条合法的行（列）一定是“交替排列”，只不过允许在某个位置出现唯一一次 ++。这次 ++ 会让后面的奇偶性交替整体翻转。

从 ++ 推出“链”

现在回到二维网格。

如果某一行中在某个位置出现了 ++，那么根据列也必须合法，可以推出下一行中与之相邻的若干格子都会被强制确定。继续往下推，会形成一条沿着对角线延伸的结构，官方把它称为一条 ++ 链。

这条链只能沿一个方向延伸：

• 要么整体向左下延伸
• 要么整体向右下延伸

如果两种方向的链同时出现，就会在某些行或列里制造出多次 ++，从而违反一维合法性。

因此，我们可以先只考虑一种方向，例如“向左下”，另一种方向只需把整张图左右翻转后重复计算即可。

固定方向后，网格由对角线决定

在固定了链的方向后，可以证明：每条左下-右上的对角线（也就是格子满足 \(r+c\) 相同的那一类）上的值都相同。

如果完全没有链，那么这些对角线的值会严格交替：

\(+,-,+,-,\dots\)

而每出现一条链，就相当于在某个对角线位置把这个交替序列的奇偶性“翻转”一次。

于是，一个网格可以看成由下面三部分决定：

• 第一条对角线的值
• 最后一条对角线的值
• 链的位置

链的位置最多只有两条

把一条链的位置定义为：那一对 ++ 中“右边那个 +”所在的对角线编号。

若前一条链的位置是 \(d\)，那么后一条链的位置至少要到：

• \(d + \max(R,C) - 1\)，如果 \(\max(R,C)\) 是偶数
• \(d + \max(R,C)\)，如果 \(\max(R,C)\) 是奇数

并且之后也只能每隔两条对角线尝试一次。

特别地，当 \(d > \min(R,C)\) 时，后面就不可能再放新的链了。由此可知，一张网格里至多只有两条链。

把记忆限制投影到对角线上

每个被记住的格子都会给某一条对角线赋予一个确定符号。

首先要检查：

• 同一条对角线上的已知格子是否互相矛盾

如果矛盾，答案直接为 \(0\)。

接着枚举第一条和最后一条对角线的符号（最多 \(4\) 种情况）。在某个固定枚举下，我们就得到若干“值已知的对角线”。

考虑这些已知对角线中相邻的两条，编号分别为 \(L<R\)。

这两条对角线之间会发生什么

如果按纯交替模式从 \(L\) 走到 \(R\)，两端符号正好能对上，那么这段中：

• 要么没有链
• 要么恰好有两条链

如果纯交替对不上，那么这段中必须恰好有一条链。

于是，每一对相邻已知对角线都可以被归类为：

• “必须有 1 条链”
• “只能有 0 条或 2 条链”

如果“必须有 1 条链”的区间超过两个，那么整张图至少需要三条链，答案就是 \(0\)。

分类计数

设“必须有 1 条链”的区间个数为 \(cnt\)。

情况 1：\(cnt=0\)

这时有两种可能：

• 整张图没有链
• 两条链都落在同一个相邻已知对角线区间内

对于后一种情况，枚举左边那条链的位置，再根据上面的最小间隔公式计算右边那条链能放在哪些位置上即可。

情况 2：\(cnt=1\)

唯一那个区间里必须放一条链，其余地方都不能再有链。于是只需要统计这条链在该区间内有多少个合法位置。

情况 3：\(cnt=2\)

两个区间里各必须放一条链。枚举左边区间中的链位置，再检查右边区间中有多少个位置既满足本区间的奇偶性要求，又满足与左边那条链的最小间隔要求。

两个方向都要算

前面只处理了“链向左下延伸”的情况。

把所有记忆点的列坐标做一次镜像变换后，同样的方法还能统计“链向右下延伸”的情况。

需要注意：

• 没有链的纯交替网格会在两个方向里都被数到，所以只在其中一个方向里计入这类情况即可
• 当 \(R=C=2\) 时，全 + 的网格会被重复统计，需要单独减去一次

复杂度

每组测试只需要：

• 扫一遍已知格子
• 扫一遍对角线
• 对极少数区间做线性枚举

总复杂度为：

\(O(R + C + X)\)

可以通过全部数据。