专栏文章

【随记】用 OI 法解化学方程式配平

JJXR_Kalcium
算法·理论参与者 8已保存评论 8

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
8 条
当前快照
1 份
快照标识符
@mie5x36u
此快照首次捕获于
2025/11/25 13:56
3 个月前
此快照最后确认于
2025/12/01 20:32
3 个月前
查看原文

前言

随便在网上翻到这样一个东西。
配平以下化学方程式。
KMnO4+FeSO4+H2SO4  Fe2(SO4)3+MnSO4+K2SO4+H2O\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+1n+1 种反应物 X0∼nX_{0\sim n} 和 mm 种生成物 Xn+1∼mX_{n+1\sim m}，下面你需要给其配平（即求出所有 aia_i 的值，必须为正整数）。
a0X0+a1X1+⋯+anXn  an+1Xn+1+an+2Xn+2+⋯+an+mXn+ma_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}
所有 XX 以一个 (n+m+1)k(n+m+1)k 的矩阵 cc 给出，其中 kk 表示所有 XX 中的元素总种数，ci,jc_{i,j} 表示一个 XiX_i 分子中第 jj 种元素有 ci,jc_{i,j} 个原子。数据范围满足 n+m≤500n+m\le 500。

解题思路

首先不妨令 a0=1a_0=1，最后再将所有 aia_i 通分，这样就把正整数规约为了分数，并且可以把所有 c0,jc_{0,j} 作为常数项。
根据质量守恒定律，不难想到对于每种元素 jj 都能构成一个方程。
c0,j+∑i=1nci,jai=∑i=n+1n+mci,jaic_{0,j}+\sum_{i=1}^n c_{i,j}a_i=\sum_{i=n+1}^{n+m} c_{i,j}a_i
方程化为
−c1,ja1−c2,ja2−⋯−cn,jan+cn+1,jan+1+⋯+cn+m,jan+m=c0,j-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}
于是可以把所有 ci,j (1≤i≤n)c_{i,j}~(1\le i\le n) 取反，就形成了一个普通的 n+mn+m 元方程，这 kk 个方程就构成了一个 n+mn+m 元线性方程组。
{c1,1a1+c2,1a2+⋯+cn+m,1an+m=c0,1,c1,2a1+c2,2a2+⋯+cn+m,2an+m=c0,2,⋯c1,ka1+c2,ka2+⋯+cn+m,kan+m=c0,k\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.
直接高斯消元求解即可。此时求得的 aia_i 都是分数的形式，所以所有 aia_i 乘上 lcm(a1∼n)\mathrm{lcm}(a_{1\sim n}) 即可，理论时间复杂度 O[(n+m)3]O\left[(n+m)^3\right]。
下面以前言中的题目为例。依题意得
c=[040110(KMnO4)0−4−100−1(FeSO4)−2−4−1000(H2SO4)0123002[Fe2(SO4)3]041010(MnSO4)041200(K2SO4)210000(H2O)(H)(O)(S)(K)(Mn)(Fe)]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={1,5,4,52,1,12,4}a=\left\{1,5,4,\frac{5}{2},1,\frac{1}{2},4\right\}
通分得
a={2,10,8,5,2,1,8}a=\left\{2,10,8,5,2,1,8\right\}
所以最终的方程式为
2KMnO4+10FeSO4+8H2SO4=5Fe2(SO4)3+2MnSO4+K2SO4+8H2O\mathrm{2KMnO_4+10FeSO_4+8H_2SO_4\xlongequal{}5Fe_2(SO_4)_3+2MnSO_4+K_2SO_4+8H_2O}
AC 代码
懒得写了（）反正大力高斯消元加一个分数类应该就能很好实现了，期待有人写出来 std 发我。
课后作业
配平以下化学方程式。
H2+Ca(CN)2+NaAlF4+FeSO4+MgSiO3+KI+H3PO4+PbCrO4+BrCl+CF2Cl2+SO2  PbBr2+CrCl3+MgCO3+KAl(OH)4+Fe(SCN)3+PI3+Na2SiO3+CaF2+H2O\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}

评论

共 8 条评论，欢迎与作者交流。

正在加载评论...