【随记】用 OI 法解化学方程式配平
JXR_Kalcium
·
·
算法·理论
前言
随便在网上翻到这样一个东西。
配平以下化学方程式。
\mathrm{KMnO_4+FeSO_4+H_2SO_4~\rule[0.3em]{1em}{}~Fe_2(SO_4)_3+MnSO_4+K_2SO_4+H_2O}
看上去十分不可做，因此考虑是否可使用 OI 方法求通解，所以就有了这篇文章。
物理课上随便想的喵喵喵。
题目大意
给定一个如下的化学方程式，有 n+1 种反应物 X_{0\sim n} 和 m 种生成物 X_{n+1\sim m}，下面你需要给其配平（即求出所有 a_i 的值，必须为正整数）。
a_0X_0+a_1X_1+\cdots+a_nX_n~\rule[0.3em]{1em}{}~a_{n+1}X_{n+1}+a_{n+2}X_{n+2}+\cdots+a_{n+m}X_{n+m}
所有 X 以一个 (n+m+1)k 的矩阵 c 给出，其中 k 表示所有 X 中的元素总种数，c_{i,j} 表示一个 X_i 分子中第 j 种元素有 c_{i,j} 个原子。数据范围满足 n+m\le 500。
解题思路
首先不妨令 a_0=1，最后再将所有 a_i 通分，这样就把正整数规约为了分数，并且可以把所有 c_{0,j} 作为常数项。
根据质量守恒定律，不难想到对于每种元素 j 都能构成一个方程。
c_{0,j}+\sum_{i=1}^n c_{i,j}a_i=\sum_{i=n+1}^{n+m} c_{i,j}a_i
方程化为
-c_{1,j}a_1-c_{2,j}a_2-\cdots-c_{n,j}a_n+c_{n+1,j}a_{n+1}+\cdots+c_{n+m,j}a_{n+m}=c_{0,j}
于是可以把所有 c_{i,j}~(1\le i\le n) 取反，就形成了一个普通的 n+m 元方程，这 k 个方程就构成了一个 n+m 元线性方程组。
\left\{\begin{aligned}
&c_{1,1}a_1+c_{2,1}a_2+\cdots+c_{n+m,1}a_{n+m}=c_{0,1},\\
&c_{1,2}a_1+c_{2,2}a_2+\cdots+c_{n+m,2}a_{n+m}=c_{0,2},\\
&\cdots\\
&c_{1,k}a_1+c_{2,k}a_2+\cdots+c_{n+m,k}a_{n+m}=c_{0,k}
\end{aligned}\right.
直接高斯消元求解即可。此时求得的 a_i 都是分数的形式，所以所有 a_i 乘上 \mathrm{lcm}(a_{1\sim n}) 即可，理论时间复杂度 O\left[(n+m)^3\right]。
下面以前言中的题目为例。依题意得
c=\begin{bmatrix}
0&4&0&1&1&0&(\mathrm{KMnO_4})\\
0&-4&-1&0&0&-1&(\mathrm{FeSO_4})\\
-2&-4&-1&0&0&0&(\mathrm{H_2SO_4})\\
0&12&3&0&0&2&[\mathrm{Fe_2(SO_4)_3}]\\
0&4&1&0&1&0&(\mathrm{MnSO_4})\\
0&4&1&2&0&0&(\mathrm{K_2SO_4})\\
2&1&0&0&0&0&(\mathrm{H_2O})\\
(\mathrm{H})&(\mathrm{O})&(\mathrm{S})&(\mathrm{K})&(\mathrm{Mn})&(\mathrm{Fe})
\end{bmatrix}
高斯消元得
a=\left\{1,5,4,\frac{5}{2},1,\frac{1}{2},4\right\}
通分得
a=\left\{2,10,8,5,2,1,8\right\}
所以最终的方程式为
\mathrm{2KMnO_4+10FeSO_4+8H_2SO_4\xlongequal{}5Fe_2(SO_4)_3+2MnSO_4+K_2SO_4+8H_2O}
::::success[AC 代码]
懒得写了（）反正大力高斯消元加一个分数类应该就能很好实现了，期待有人写出来 std 发我。
::::
::::info[课后作业]
配平以下化学方程式。
\mathrm{H_2+Ca(CN)_2+NaAlF_4+FeSO_4+MgSiO_3+KI+H_3PO_4+PbCrO_4+BrCl+CF_2Cl_2+SO_2~\rule[0.3em]{1em}{}~PbBr_2+CrCl_3+MgCO_3+KAl(OH)_4+Fe(SCN)_3+PI_3+Na_2SiO_3+CaF_2+H_2O}
::::