CF1933G Turtle Magic: Royal Turtle Shell Pattern

乌龟 Alice 正在设计一个幸运饼干盒，她希望将洛书理论融入其中。 这个盒子可以看作一个 $n \times m$ 的网格（$n, m \ge 5$），行编号为 $1, 2, \dots, n$，列编号为 $1, 2, \dots, m$。每个格子可以为空，或者放有一种形状的幸运饼干：圆形或方形。第 $a$ 行第 $b$ 列的格子记作 $(a, b)$。 初始时，整个网格都是空的。接下来，Alice 会对幸运饼干盒进行 $q$ 次操作。第 $i$ 次操作（$1 \le i \le q$）如下：指定一个当前为空的格子 $(r_i, c_i)$ 和一种形状（圆形或方形），然后在该格子放入指定形状的幸运饼干。注意，操作后 $(r_i, c_i)$ 这个格子不再为空。 在所有操作之前以及每次操作后，Alice 都想知道：在所有剩余空格中放置幸运饼干的方案数，使得满足以下条件： 任意三个连续的格子（横向、纵向、两条对角线方向）中，不能全是同一种形状的幸运饼干。形式化地说： - 不存在某个 $(i, j)$ 满足 $1 \le i \le n, 1 \le j \le m-2$，使得 $(i, j), (i, j+1), (i, j+2)$ 这三个格子都放有同一种形状的幸运饼干。 - 不存在某个 $(i, j)$ 满足 $1 \le i \le n-2, 1 \le j \le m$，使得 $(i, j), (i+1, j), (i+2, j)$ 这三个格子都放有同一种形状的幸运饼干。 - 不存在某个 $(i, j)$ 满足 $1 \le i \le n-2, 1 \le j \le m-2$，使得 $(i, j), (i+1, j+1), (i+2, j+2)$ 这三个格子都放有同一种形状的幸运饼干。 - 不存在某个 $(i, j)$ 满足 $1 \le i \le n-2, 1 \le j \le m-2$，使得 $(i, j+2), (i+1, j+1), (i+2, j)$ 这三个格子都放有同一种形状的幸运饼干。 你需要输出所有答案对 $998\,244\,353$ 取模的结果。注意，如果在某些操作后，已经放置的幸运饼干本身就不满足条件，则应输出 $0$。

输入的第一行包含一个整数 $t$（$1 \le t \le 10^3$），表示测试用例的数量。 每个测试用例的第一行包含三个整数 $n, m, q$（$5 \le n, m \le 10^9, 0 \le q \le \min(n \times m, 10^5)$）。 接下来的 $q$ 行，每行包含两个整数 $r_i, c_i$ 和一个字符串 $\text{shape}_i$（$1 \le r_i \le n, 1 \le c_i \le m$，$\text{shape}_i=$ "circle" 或 "square"），表示一次操作。保证 $(r_i, c_i)$ 这个格子初始为空，即每个 $(r_i, c_i)$ 在所有操作中最多出现一次。 所有测试用例中 $q$ 的总和不超过 $10^5$。

对于每个测试用例，输出 $q+1$ 行。第一行输出未进行任何操作前的答案。第 $i$ 行（$2 \le i \le q+1$）输出前 $i-1$ 次操作后的答案。所有答案均需对 $998\,244\,353$ 取模。

在第二个样例中，在 $(1,1)$、$(1,2)$ 和 $(1,3)$ 这三个格子都放上圆形幸运饼干后，条件已经不满足，因此应输出 $0$。 由 ChatGPT 4.1 翻译