AT_agc060_b [AGC060B] Unique XOR Path

有一个 $N$ 行 $M$ 列的网格。你需要在网格的每个格子中填写一个整数，要求每个整数在 $0$ 到 $2^K-1$ 之间，并且满足以下条件： - 从左上角出发，每次只能向右或向下移动到相邻的格子，最终到达右下角。我们考虑所有这样的路径。对于一条路径，如果经过的所有格子（包括起点和终点）中的整数的 $\mathrm{XOR}$ 总和为 $0$，则称这条路径为**好路径**。 - 恰好只有一条好路径，并且这条路径正好是由字符串 $S$ 所表示的路径。字符串 $S$ 表示的路径是：对于每个 $i$（$1 \leq i \leq N+M-2$），第 $i$ 次移动时，如果 $S$ 的第 $i$ 个字符是 `R`，则向右移动；如果是 `D`，则向下移动。 请判断是否存在一种整数填写方案，使得上述条件成立。 每个输入文件包含 $T$ 个测试用例。 位运算 $\mathrm{XOR}$ 的定义如下：对于非负整数 $A, B$，它们的按位 $\mathrm{XOR}$（记作 $A \oplus B$）的每一位，如果 $A$ 和 $B$ 在该位上只有一个为 $1$，则结果为 $1$，否则为 $0$。 例如，$3 \oplus 5 = 6$（二进制表示为：$011 \oplus 101 = 110$）。 一般地，$k$ 个非负整数 $p_1, p_2, p_3, \dots, p_k$ 的按位 $\mathrm{XOR}$ 定义为 $(\dots((p_1 \oplus p_2) \oplus p_3) \oplus \dots \oplus p_k)$，并且可以证明其结果与顺序无关。

输入通过标准输入给出，格式如下： > $T$ > $case_1$ > $case_2$ > $\vdots$ > $case_T$ 每个测试用例格式如下： > $N$ $M$ $K$ $S$

对于每个测试用例，如果存在满足条件的整数填写方案，输出 `Yes`，否则输出 `No`。输出中的字母大小写均可。

### 数据范围 - $1 \leq T \leq 100$ - $2 \leq N, M \leq 30$ - $1 \leq K \leq 30$ - $S$ 是一个恰好包含 $N-1$ 个 `D` 和 $M-1$ 个 `R` 的字符串 - 输入的所有数均为整数 ### 样例解释 1 例如对于第 1 个测试用例，可以构造如下的网格： ``` 11 00 ``` 由 ChatGPT 4.1 翻译