P12839 [蓝桥杯 2025 国 B] 涂格子
题目描述
小蓝正在玩一个涂格子的游戏。他有一个大小为 $n \times m$ 的矩阵，他要给这个矩阵中的每个格子都涂上黑色或白色。小蓝希望最终涂完的格子像国际象棋棋盘一样整齐。具体来说，他希望每一个同色连通块都是矩形，且与上下左右四个异色的矩形相邻（如果存在的话）。下图中第一行的两个涂色方案是合法的，第二行的两个涂色方案是不合法的。
同时小蓝希望 $k$ 个格子具有特定的颜色。其中第 $i$ 个格子位置是 $(x_i, y_i)$，具有特定的颜色 $c_i$。你需要帮助他求出符合要求的合法涂色方案有多少种。因为方案数可能很大，请对 $998244353$ 取模后输出。
输入格式
输入第一行包含三个正整数 $n, m, k$，含义如问题描述所述。
接下来 $k$ 行，每行三个正整数 $x_i, y_i, c_i$，表示格子 $(x_i, y_i)$ 必须被涂成颜色 $c_i$。**注意 $x_i, y_i$ 可能重复出现。**
输出格式
输出共一个整数，表示答案。
说明/提示
**【评测用例规模与约定】**
对于 $20\%$ 的评测用例，$n \times m \leq 20$。
对于 $50\%$ 的评测用例，$n, m, k \leq 5000$。
另存在 $30\%$ 的评测用例，$c_i = 0$。
另存在 $10\%$ 的评测用例，$k = 0$。
对于 $100\%$ 的评测用例，$1 \leq n, m \leq 10^9$，$1 \leq k \leq 3 \times 10^5$，$1 \leq x_i \leq n$，$1 \leq y_i \leq m$，$c_i \in \{0, 1\}$。