一、题意重述

在一个 $n \times m$ 的网格中（$n, m \ge 5$），每个格子可以放圆形（circle）或方形（square）的饼干。要求满足：

任意连续三个格子（水平、垂直、两个对角线方向）不能出现相同形状。

初始全空。进行 $q$ 次操作，每次在一个当前为空的格子中放入指定形状的饼干。
在每次操作前后，输出在剩余空位中填满饼干的合法方案数，对 $998244353$ 取模。
如果已放置的饼干已经违反条件，输出 $0$。

---

二、核心观察

关键结论

当 $n, m \ge 5$ 时，整个网格只有 $8$ 种全局合法的填充模式。

也就是说，无论网格多大，合法的完整填充方案数最多为 $8$。
因此，初始答案就是 $8$。

---

三、证明思路（对应题解中的三个 Claim）

Claim 1

在不靠边角的任意 $2 \times 2$ 子网格中，必须恰好有 $2$ 个圆形和 $2$ 个方形。

• 反证法：假设有 $3$ 个或 $4$ 个相同形状。
• 通过推导，必然会构造出三个连续相同形状（水平/垂直/对角线），违反条件。

Claim 2

在不靠边角的任意 $3 \times 3$ 子网格中，至少存在一个 $2 \times 2$ 子网格属于以下四种“好模式”之一。

好模式定义：

• 反证法：假设 $3 \times 3$ 中没有任何 $2 \times 2$ 是好模式。
• 则任意相邻格子形状不同（棋盘染色模式）。
• 这会推导出主对角线或副对角线出现三个相同形状，违反条件。

最终推导

• 由 Claim 2，一定存在一个“好”的 $2 \times 2$ 子网格。
• 该 $2 \times 2$ 可以唯一地向整个网格扩展（类似平铺）。
• 四种好模式，每种可以向右平移一列，或向下平移一行，得到 $4 \times 2 = 8$ 种全局模式。

---

四、8 种模式的具体表示

对于 $n \times m$ 的网格，记 $a_{i,j} = 1$ 表示格子 $(i, j)$ 放圆形，$0$ 表示放方形。
$8$ 种模式如下：

1. $a_{i,j} = 1 \iff i + \lceil \frac{j}{2} \rceil$ 为奇数

2. $a_{i,j} = 1 \iff i + \lceil \frac{j}{2} \rceil$ 为偶数

3. $a_{i,j} = 1 \iff i + \lfloor \frac{j}{2} \rfloor$ 为奇数

4. $a_{i,j} = 1 \iff i + \lfloor \frac{j}{2} \rfloor$ 为偶数

5. $a_{i,j} = 1 \iff j + \lceil \frac{i}{2} \rceil$ 为奇数

6. $a_{i,j} = 1 \iff j + \lceil \frac{i}{2} \rceil$ 为偶数

7. $a_{i,j} = 1 \iff j + \lfloor \frac{i}{2} \rfloor$ 为奇数

8. $a_{i,j} = 1 \iff j + \lfloor \frac{i}{2} \rfloor$ 为偶数

---

五、算法实现

思路

• 维护一个长度为 $8$ 的布尔数组 $b$，$b[k]$ 表示第 $k$ 种模式当前是否仍然可能。
• 初始全为 $\text{true}$，答案为 $8$。
• 每次操作 $(r, c, \text{shape})$：
  • 对每一种模式 $k$，检查该模式下 $(r, c)$ 的预期形状是否与给定的 $\text{shape}$ 一致。
  • 如果不一致，则 $b[k] = \text{false}$。
  • 如果某个 $b[k]$ 已经是 $\text{false}$，不需要再检查。
• 答案 = $\sum b[k]$。
• 如果答案为 $0$，后续操作保持 $0$。

判断方法（标程写法）

对于模式 0, 1（第一组）：

• 计算 $x = (r + \lceil \frac{c}{2} \rceil) \bmod 2$
• 如果 $x = 1$：模式 0 要求圆形，模式 1 要求方形
• 如果 $x = 0$：模式 0 要求方形，模式 1 要求圆形

其他组类似，对应不同的公式：

• 模式 2, 3：$r + \lfloor \frac{c}{2} \rfloor$
• 模式 4, 5：$c + \lceil \frac{r}{2} \rceil$
• 模式 6, 7：$c + \lfloor \frac{r}{2} \rfloor$

---

六、代码解析（对应给定标程）

void solve(int tc) { 
  int n, m, q;
  cin >> n >> m >> q;
  bool b[8] = {1, 1, 1, 1, 1, 1, 1, 1};
  int ans = 8;
  cout << ans << '\n';
  while(q--) {
    int r, c;
    string shape;
    cin >> r >> c >> shape;
    
    // 第 0、1 种模式
    if((r + (c+1) / 2) % 2) {
      b[0] &= (shape == "circle");
      b[1] &= (shape == "square");
    } else {
      b[0] &= (shape == "square");
      b[1] &= (shape == "circle");
    }
    
    // 第 2、3 种模式
    if((r + c / 2) % 2) {
      b[2] &= (shape == "circle");
      b[3] &= (shape == "square");
    } else {
      b[2] &= (shape == "square");
      b[3] &= (shape == "circle");
    }
    
    // 第 4、5 种模式
    if((c + (r+1) / 2) % 2) {
      b[4] &= (shape == "circle");
      b[5] &= (shape == "square");
    } else {
      b[4] &= (shape == "square");
      b[5] &= (shape == "circle");
    }
    
    // 第 6、7 种模式
    if((c + r / 2) % 2) {
      b[6] &= (shape == "circle");
      b[7] &= (shape == "square");
    } else {
      b[6] &= (shape == "square");
      b[7] &= (shape == "circle");
    }
    
    ans = 0;
    for(int i = 0; i < 8; i++) ans += b[i];
    cout << ans << '\n';
  }
}

---

七、复杂度分析

• 每个操作：$O(1)$
• 总复杂度：$O(\sum q)$
• 空间：$O(1)$

---

八、扩展讨论

原题解最后提到：可以尝试解决 $1 \le \min(n, m) \le 4$ 的情况。
此时上述 $8$ 种模式不一定能覆盖所有合法方案，因为边角区域的约束变弱，会有更多模式。
这是一个有趣的扩展方向，但本题核心已充分展示。

---

九、总结

要点	说明
核心观察	大网格只有 $8$ 种全局合法模式
证明方法	通过 $2\times 2$ 和 $3\times 3$ 子网格推导
实现方式	维护 $8$ 种模式的可行性，每次操作排除不匹配的模式
时间复杂度	$O(\sum q)$
初始答案	$8$

这道题属于 思维 > 代码 的典型 CF 题，一旦想到 $8$ 种模式，就非常简单；否则很难入手。