题目理解

在 $N \times N$ 的网格中，某些格子有草（标记为 G）。我们需要计算所有满足以下条件的非空子集数量：

1. 全为草地：子集中的所有格子必须都是 G。
2. 四连通：子集中的任意两个格子可以通过上下左右相邻的路径连接（路径上的格子也必须在子集中）。
3. 行连续性：如果同一行的两个格子被选中，那么它们之间的所有格子也必须被选中。
4. 列连续性：如果同一列的两个格子被选中，那么它们之间的所有格子也必须被选中。

这些条件意味着：平衡子集是由若干行组成的，每行选择的是一个连续区间，并且这些区间的左右端点随行变化必须是单调的（左端点不向右移动，右端点不向左移动）。

---

关键观察

1. 平衡子集的结构特性

• 平衡子集可以看作一个凸形区域：在水平方向每行是连续的，在垂直方向左右边界单调变化。
• 条件3和4实际上要求：如果 (x₁,y) 和 (x₂,y) 被选中，那么 x₁ 到 x₂ 之间所有 (x,y) 都被选中（垂直方向连续）。
• 结合四连通性，平衡子集必须是一个在行和列上都连续的凸区域。

2. 动态规划思路

我们可以逐行考虑，定义状态表示当前行的选择情况以及与上一行的连接关系。

定义状态：
dp[i][l][r][a][b] 表示：

• 当前处理到第 i 行
• 本行选择的列区间为 [l, r]（全部为 G）
• 状态 a 表示左边界是否扩展：0 表示左边界与上一行相同，1 表示左边界比上一行更左
• 状态 b 表示右边界是否扩展：0 表示右边界与上一行相同，1 表示右边界比上一行更右

---

算法设计

1. 状态转移

对于第 i 行的区间 [l, r]（必须全为 G），考虑与上一行的连接情况：

情况1：左右边界均未扩展（a=0, b=0）

• 上一行也必须选择相同的区间 [l, r]
• 转移：dp[i][l][r][0][0] = 1 + sum(dp[i-1][l][r][*][*])
  （+1 表示从这一行开始新的子集）

情况2：左边界未扩展，右边界扩展（a=0, b=1）

• 上一行左边界为 l，右边界小于 r
• 转移：从上一行区间 [l, r']（r' < r）转移过来

情况3：左边界扩展，右边界未扩展（a=1, b=0）

• 上一行左边界大于 l，右边界为 r
• 转移：从上一行区间 [l', r]（l' > l）转移过来

情况4：左右边界均扩展（a=1, b=1）

• 上一行左边界大于 l，右边界小于 r
• 转移：从上一行区间 [l', r']（l' > l, r' < r）转移过来

2. 前缀和优化

直接枚举上一行的区间会导致 $O(N^5)$ 复杂度，不可接受。我们需要用二维前缀和优化：

定义 sum[i][x][y][a][b] 为第 i 行中，行区间在 [1, x]，列区间在 [1, y] 的所有 dp 值之和。

通过二维前缀和，可以在 $O(1)$ 时间内计算任意矩形区域的 dp 值之和：

// 计算行区间[x1,x2]，列区间[y1,y2]，状态(l,r)的dp值之和
long long sm(int i, int x1, int x2, int y1, int y2, int l, int r) {
    return ((sum[i][x2][y2][l][r] - sum[i][x1-1][y2][l][r]) % mod 
            - sum[i][x2][y1-1][l][r] + sum[i][x1-1][y1-1][l][r] + mod) % mod;
}

3. 转移公式

利用前缀和，转移可以写成：

// 情况1：左右边界均未扩展
dp[i][l][r][0][0] = 1 + sm(i-1, l, r, l, r, 0, 0);

// 情况2：左边界未扩展，右边界扩展
dp[i][l][r][0][1] = (sm(i-1, l, r, r+1, n, 0, 0) + sm(i-1, l, r, r, n, 0, 1)) % mod;

// 情况3：左边界扩展，右边界未扩展  
dp[i][l][r][1][0] = (sm(i-1, 1, l-1, l, r, 0, 0) + sm(i-1, 1, l, l, r, 1, 0)) % mod;

// 情况4：左右边界均扩展
dp[i][l][r][1][1] = ((sm(i-1, 1, l, r, n, 1, 1) + sm(i-1, 1, l-1, r+1, n, 0, 0)) % mod +
                     (sm(i-1, 1, l-1, r, n, 0, 1) + sm(i-1, 1, l, r+1, n, 1, 0)) % mod) % mod;

4. 算法流程

1. 读入网格，逐行处理
2. 对于每一行，枚举所有可能的列区间 [l, r]
3. 检查该区间是否全为 G
4. 如果是，计算四种状态的 dp 值
5. 更新前缀和数组
6. 累加所有 dp 值到答案中

---

算法正确性

1. 状态设计的完备性

• 状态 [a][b] 准确描述了当前行区间与上一行区间的位置关系
• 四种情况覆盖了所有可能的连接方式
• 保证了左右边界的单调性（不向右收缩）

2. 连通性保证

• 通过要求当前行与上一行区间有重叠，保证了垂直方向的连通性
• 每行内部的区间连续，保证了水平方向的连通性

3. 不重不漏

• 每个平衡子集对应唯一的行区间序列
• 状态转移确保每个子集只被计数一次

---

复杂度分析

时间复杂度

• 对于每行 $O(N^2)$ 个区间
• 每个区间计算4种状态，每种状态 $O(1)$ 转移
• 更新前缀和：$O(N^2)$
• 总时间复杂度：$O(N^3)$，其中 $N \leq 150$，可以接受

空间复杂度

• dp 数组：$O(N^3)$（使用滚动数组可优化为 $O(N^2)$）
• 前缀和数组：$O(N^3)$
• 对于 $N=150$，内存需求在合理范围内

---

代码实现要点

1. 滚动数组优化

由于只用到上一行的信息，可以使用滚动数组减少空间使用。

2. 模运算处理

注意负数取模的处理，确保结果在 $[0, mod-1]$ 范围内。

3. 边界条件

• 第一行没有上一行，所有状态初始化为1（单独作为一个子集）
• 区间必须全为 G 才有效

4. 前缀和更新

按照二维前缀和的标准方式更新：

sum[i][x][y][a][b] = sum[i][x-1][y][a][b] + sum[i][x][y-1][a][b] 
                   - sum[i][x-1][y-1][a][b] + dp[i][x][y][a][b];

---

关键点：

1. 将平衡子集理解为行连续区间的序列
2. 用 [a][b] 状态记录边界扩展情况
3. 使用二维前缀和优化区间查询
4. 注意模运算和边界条件处理

---

算法标签

• 动态规划
• 区间DP
• 前缀和
• 几何性质分析

---

总结

本题通过巧妙的动态规划状态设计，将复杂的几何条件转化为可计算的形式。核心在于理解平衡子集的结构特性：每行连续且左右边界单调变化。利用二维前缀和优化转移，将复杂度降低到 $O(N^3)$，适合 $N \leq 150$ 的数据范围。这个解法充分利用了问题的特殊结构，通过状态设计将连通性和凸性条件融入转移方程中，是区间DP与几何结合的典型例子。