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 翻译