题解：网格洒水器覆盖与动态规划计数

问题分析

本题要求在 $N \times N$ 的网格中放置两种洒水器：

• 甜玉米洒水器：安装在 $(I,J)$ 时，覆盖所有满足 $I \le i$ 且 $j \le J$ 的格子（左下区域）
• 紫苜蓿洒水器：安装在 $(I,J)$ 时，覆盖所有满足 $i \le I$ 且 $J \le j$ 的格子（右上区域）

要求每个格子恰好被一种洒水器覆盖，且每个格子最多放置一个洒水器。有些格子被奶牛占据（W），不能放置洒水器。

关键观察

1. 覆盖区域的性质
   两种洒水器的覆盖区域形成互补关系。考虑从左上到右下的划分：

   • 甜玉米洒水器主要覆盖左下区域
   • 紫苜蓿洒水器主要覆盖右上区域 实际上，存在一条从左上到右下的分界线，使得：
   • 分界线左下方的格子由甜玉米洒水器覆盖
   • 分界线上方的格子由紫苜蓿洒水器覆盖

2. 分界线的特征
   由于每个格子只能被一种洒水器覆盖，分界线必须是单调向右下方向的路径：

   • 从左边或上边进入，从右边或下边离开
   • 不能有"凹"形状，否则会出现双重覆盖或未覆盖的区域

3. 洒水器的位置
   洒水器只能放置在分界线的"拐角"处：

   • 甜玉米洒水器放置在分界线右转的位置
   • 紫苜蓿洒水器放置在分界线左转的位置
   • 实际上，洒水器放置位置与分界线的形状一一对应

算法框架

状态设计

设 $f[i][j]$ 表示处理到第 $j$ 列时，分界线当前在第 $i$ 行的方案数（$i$ 从 $0$ 到 $n$，$0$ 表示分界线在当前列上方）。

转移方程

考虑从第 $j-1$ 列到第 $j$ 列的转移：

• 如果分界线下降（$i$ 增加）：对应放置甜玉米洒水器
• 如果分界线上升（$i$ 减少）：对应放置紫苜蓿洒水器
• 如果分界线不变：对应不放置洒水器

障碍处理

• 如果 $(i,j)$ 是 W，则不能在该位置放置洒水器
• 如果分界线经过的位置有 W，则相应的转移不可行

优化实现

1. 降维优化：使用滚动数组，只保留当前列和前一列的状态
2. 前缀和优化：使用前缀和加速转移
3. 幂次预处理：预处理 $2^{cnt}$，其中 $cnt$ 是可放置位置的数量，用于计算基础方案数

核心代码逻辑

// 初始化
int v = ksm(2, cnt); // 2^cnt，所有可放置位置的子集数
for (int i = 0; i < n; i++)
    if (str[i+1][1] != 'W')
        f[i] = mul(v, iv); // 除以2，考虑第一列的特殊性

// 逐列转移
for (int t = 2; t <= n; t++) {
    memcpy(g, f, sizeof(f)); // g保存上一列的状态
    int s = 0; // 前缀和
    
    for (int i = n; ~i; i--) {
        // 当前格子可放置洒水器时的转移
        if (str[i+1][t] != 'W' && (t != n || str[i][t] != 'W'))
            Add(f[i], s);
        
        // 更新前缀和
        if (str[i][t-1] != 'W')
            Add(s, mul(pv, g[i])); // pv = 1/4
    }
}

// 统计答案
int res = 0;
for (int i = 0; i <= n; i++)
    if (str[i][n] != 'W')
        Add(res, mul(f[i], (i == 0) ? 1 : iv)); // 最后一列的特殊处理

复杂度分析

• 时间复杂度：$O(N^2)$
  • 外层循环 $N$ 列
  • 内层循环 $N$ 行
• 空间复杂度：$O(N)$（使用滚动数组）

对于 $N \le 2000$ 的数据范围完全可行。

总结

本题是一道基于几何划分的动态规划计数问题，主要考察：

1. 几何直观：将洒水器覆盖问题转化为网格分界线问题
2. 状态设计：设计合理的状态表示分界线位置
3. 转移优化：使用前缀和加速动态规划转移
4. 模运算处理：在模意义下进行计数和幂次计算

算法的巧妙之处在于：

• 通过分界线将二维覆盖问题化为一维路径计数问题
• 利用洒水器放置位置与分界线形状的一一对应关系
• 使用简洁的动态规划状态和高效的转移方法

这种"将覆盖问题转化为边界路径问题"的思路在组合计数中非常常见，本题通过洒水器的特殊覆盖方式，给出了一个优美的应用实例。