更多 CSP 认证考试题目题解可以前往：CSP-CCF 认证考试真题题解

原题链接： 202403-3 化学方程式配平

时间限制： 1.0 秒 空间限制： 512 MiB

近日来，西西艾弗岛化学研究中心的研究员们向岛上的初中学生开展了化学科普活动。在活动中发现，初学化学的同学们十分苦恼于正确配平化学方程式。 而还有一些同学，则提出了一些稀奇古怪的方程式，让研究员们帮忙配平。在配平之前，研究员们需要先判断这个方程式是否能够配平。

一个化学方程式，也叫化学反应方程式，是用化学式表示化学反应的式子。其等号左右两侧分别列举了化学反应的全部反应物和生成物。 每种物质都用其化学式表示。一个物质的化学式，列举了构成该物质的各元素的原子数目。例如，水的化学式是 H 2 O \text{H}_2\text{O} H2​O，表示水分子中含有两个氢原子和一个氧原子。 化学方程式中每种物质的化学式前面都有一个系数，表示参与反应或生成的物质的相对数目比例。例如，方程式 2 H 2 + O 2 = 2 H 2 O 2\text{H}_2 + \text{O}_2 = 2\text{H}_2\text{O} 2H2​+O2​=2H2​O 表示二分子氢气和一分子氧气反应生成二分子水。 我们称一个化学方程式是配平的，是指该方程式中的反应物和生成物中，各元素原子总数目相等。例如上述方程式中，左侧氢原子、氧原子的总数目分别为 4 4 4 和 2 2 2，右侧氢原子、氧原子的总数目分别为 4 4 4 和 2 2 2，因此该方程式是配平的。

为了配平一个化学方程式，我们可以令方程式中各物质的系数为未知数，然后针对涉及的每一种元素，列出关于系数的方程，形成一个齐次线性方程组。然后求解这个方程组，得到各物质的系数。这样，我们就把化学方程式配平的问题，转化为了求解齐次线性方程组的问题。 如果方程组没有非零解，那么这个方程式是不可以配平的。反之，如果方程组有非零解，我们就可能得到一个配平的方程式。当然，最终得到的方程式仍然需要结合化学知识进行检验，对此我们不再进一步考虑，仅考虑非零解的存在。

例如要配平化学方程式： Al 2 ( S O 4 ) 3 + N H 3 ⋅ H 2 O → Al ( OH ) 3 + ( N H 4 ) 2 S O 4 \text{Al}_2(\text{S}\text{O}_4)_3 + \text{N}\text{H}_3\cdot\text{H}_2\text{O} \rightarrow \text{Al}(\text{O}\text{H})_3 + (\text{N}\text{H}_4)_2\text{S}\text{O}_4 Al2​(SO4​)3​+NH3​⋅H2​O→Al(OH)3​+(NH4​)2​SO4​

首先假定所有物质在方程的同一侧，即不考虑哪个是反应物，哪个是生成物，分别设这些物质的系数为 x 1 , x 2 , x 3 , x 4 x_1, x_2, x_3, x_4 x1​,x2​,x3​,x4​，则可以针对出现的各个元素，列出如下的方程组： 2 x 1 + 0 x 2 + x 3 + 0 x 4 = 0 Al 3 x 1 + 0 x 2 + 0 x 3 + x 4 = 0 S 12 x 1 + x 2 + 3 x 3 + 4 x 4 = 0 O 0 x 1 + x 2 + 0 x 3 + 2 x 4 = 0 N 0 x 1 + 5 x 2 + 3 x 3 + 8 x 4 = 0 H  \begin{align} 2x_1 + 0x_2 + x_3 + 0x_4 &= 0 && \text{Al} \\ 3x_1 + 0x_2 + 0x_3 + x_4 &= 0 && \text{S} \\ 12x_1 + x_2 + 3x_3 + 4x_4 &=0 && \text{O} \\ 0x_1 + x_2 + 0x_3 + 2x_4 &=0 && \text{N} \\ 0x_1 + 5x_2 + 3x_3 + 8x_4 &=0 && \text{H} \ \end{align} 2x1​+0x2​+x3​+0x4​3x1​+0x2​+0x3​+x4​12x1​+x2​+3x3​+4x4​0x1​+x2​+0x3​+2x4​0x1​+5x2​+3x3​+8x4​​=0=0=0=0=0​​AlSONH ​​ 用矩阵的形式表示为：

( 2 0 1 0 3 0 0 1 12 1 3 4 0 1 0 2 0 5 3 8 ) ⋅ ( x 1 x 2 x 3 x 4 ) = 0 \begin{pmatrix} 2 & 0 & 1 & 0 \\ 3 & 0 & 0 & 1 \\ 12 & 1 & 3 & 4 \\ 0 & 1 & 0 & 2 \\ 0 & 5 & 3 & 8 \end{pmatrix} \cdot \begin{pmatrix} x_1 \\ x_2 \\ x_3 \\ x_4 \end{pmatrix} = \mathbf{0} ​231200​00115​10303​01428​ ​⋅ ​x1​x2​x3​x4​​ ​=0

对系数矩阵实施高斯消元，得到系数矩阵的一个行阶梯形式：

( 2 0 1 0 0 1 − 3 4 0 0 − 3 2 1 0 0 0 0 0 0 0 0 ) \begin{pmatrix} 2 & 0 & 1 & 0 \\ 0 & 1 & -3 & 4 \\ 0 & 0 & -{3\over2} & 1 \\ 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \\ \end{pmatrix} ​20000​01000​1−3−23​00​04100​ ​

由此可见，系数矩阵的秩为 3。根据线性代数的知识，我们知道，齐次线性方程组 A X = 0 \mathbf{A}\mathbf{X} = \mathbf{0} AX=0 的解空间的维数等于其未知数个数减去系数矩阵的秩 rank A \text{rank} \mathbf A rankA。而要让方程式配平，即要求方程组存在非零解， 那么就需要让解空间的维数大于 0 0 0，即系数矩阵的秩小于未知数个数。因此，我们可以通过判断系数矩阵的秩是否小于未知数个数，来判断方程式是否可以配平。如果可以配平，则可以通过解的符号来判断反应物和生成物的位置。

本题中，我们将给出一些化学方程式，请你按照上述方法判断它们是否可以配平。为了便于程序处理，我们用到的化学式，会被化简为只包含小写字母和数字的字符串，不包含括号。 其中连续的字母表示一种元素，随后的数字表示原子个数。原子个数为 1 时不省略数字；一个化学式中包含的元素不重复。例如，上述方程式中的化学式可以化简为 al2s3o12、n1h5o1、al1o3h3、n2h8s1o4。

从标准输入读入数据。

输入的第一行包含一个正整数 n n n，表示需要判断的化学方程式的个数。

接下来的 n n n 行，每行描述了一个需要被配平的化学方程式。包含空格分隔的一个正整数和全部涉及物质的化学式。其中，正整数 m m m 表示方程式中的物质；随后的 m m m 个字符串，依次给出方程式中的反应物的化学式和生成物的化学式。

输出到标准输出。

输出包含 n n n 行，每行包含字母 Y 或 N，表示按题设方法，所给待配平化学方程式能否配平。

输入中给出了 5 个待配平的化学方程式，其中各方程式的配平情况为：

对于 20% 的数据，每个方程中物质的个数不超过 2 2 2，每个方程中涉及的全部元素不超过 2 2 2 种；

对于 60% 的数据，每个方程中物质的个数不超过 3 3 3，每个方程中涉及的全部元素不超过 3 3 3 种；

对于 100% 的数据，每个方程中物质的个数不超过 40 40 40，每个方程中涉及的全部元素不超过 40 40 40 种；且有 1 ≤ n ≤ 10 1 \leq n \leq 10 1≤n≤10，且化学式中各元素的原子个数不超过 50 50 50。

对矩阵进行高斯消元的一种方法是：

对系数矩阵高斯消元后，不全为 0 的行的数目即为系数矩阵的秩。

评测环境仅提供各语言的标准库，特别地，不提供任何线性代数库。

先将每个物质的各个元素拆分开来。可以观察到每个物质的化学式中，都是按照元素和对应元素的个数的排列顺序，而元素都是英文字母，元素个数都是数字。

这样子可以先将元素与元素之间区分开来（即如果当前位为数字，下一位为字母，那么这两位之间必定是元素的分界线），然后再将元素名称和元素个数区分开来（对于区分好的元素，如果当前位为字母，下一位为数字，那么这两位之间必定是元素和个数的分界线）。

对于每个元素，可以使用 std::map 来为其设定编号（在系数矩阵中的行数，即对应题目中的第几个方程）。对于第 i i i 个物质中，元素编号为 j j j 的元素，将其个数存储在系数矩阵的第 j j j 行第 i i i 列。

系数矩阵构造完后，使用高斯消元的方法来求解行列式的秩，高斯消元的具体过程在提示中已经给出。

求出系数矩阵的秩后，判断秩 rank 和未知数个数（所涉及物质的数量）m 的关系，如果 rank < m，则化学方程式可以配平，输出 Y；否则，化学方程式无法配平，输出 N。

时间复杂度： O ( n ⋅ 4 0 3 ) \mathcal{O}(n\cdot 40^3) O(n⋅403)。