化学方程式配平

题意: 同上

思路: 高斯消元。

首先，我们要知道什么是化学，什么是方程式，什么是化学方程式，什么是化合价，什么是化学计量数，什么是质量守恒，什么是鲁迅，什么是元素化合价归中不交叉律，什么是枣树，什么是氧化还原，什么是配平，什么是什么鬼。

然后，我们要写一个解释器 (姑且这么叫他)，用它解释什么是方程，把方程拆成化学式，把化学式拆成元素，把元素拆成变量，把变量存进 map，然后要注意双字符的元素，注意括号，注意系数长度，注意加号，注意等于号，注意其中一棵是枣树，另一棵还是枣树。

然后我们开始列方程，我们要知道什么是已知，什么是未知，什么是系数，什么是变量，什么是结果。然后我们要高斯消元，我们要明确怎么消元，怎么保存变量才不出精度问题，怎么回代，怎么得到结果。

然后我们得到了一组数字，我们要知道什么是答案，什么是化学式，什么是我们要输出的，什么是我们不要输出的，什么是枣树，什么是那鞺鞺鞳鞳的咆哮。

然后我们会得到答案，我们会过样例，我们会提交，我们会 WA, 会 RE, 会 FUCKSHIT。

然后我们鞺鞺鞳鞳的咆哮，我们会调试，我们会改代码，我们会发现自己错了，我们会怀疑人生，怀疑自己，怀疑题目，怀疑出题人，怀疑鲁迅，怀疑枣树。

然后我们会过样例，我们又会提交，我们会发现 Kb 也开始做这道题，然后我们会发现我们的屏幕红了，Kb 的屏幕绿了，我们会看表，我们会发现一个下午没了，而 Kb 去做下一题了。于是我们会颓，我们会改代码，我们会上厕所，我们会咆哮，我们会读鲁迅，会读郭沫若，会过样例。

然后我们发现自己又 WA 了，我们会发现屏幕上的代码在嘲笑我们，我们会去调试，会发现调不出。然后我们发现方程组有５个方程，有７个未知数。就算一个未知数强制设为１，我们也没法解出答案。于是我们又发现手动配平十分成功，我们会意识到这是归中不交叉律，我们会打表，我们会背叛内心，我们会膜 KB，我们会 FUCKSHIT。

然后我们去提交，我们去 WA，我们去调，我们再提交，再 WA，终于发现本地测试 AC 云端评测多输出了换行。于是我们要 AC 了，于是我们就 AC 了。

我们还是虔诚地跪下，向着 Kb 的方向，膜一膜。

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <list>
#include <map>

#define MX 100

using namespace std;

struct ptrcmp{bool operator()( const char * s1, const char * s2 ) const{return strcmp( s1, s2 ) < 0;}};

map<string,int>eton;
map<int,string>ntoe;

typedef struct mols
{
    map<string,int>mp;
    int elnum;
    char ml[MX];
    char el[MX][MX];
    int id[MX];
    int hv[MX];
    int xs[MX];
}molecule;

molecule mol[MX],mor[MX];
int lmnum,rmnum,elnum;

typedef struct numb
{
    long long up,dn;
}frac;

frac mat[MX][MX],ans[MX];
int row,col;

long long gcd(long long a,long long b)
{
    return (b==0?a:gcd(b,a%b));
}

frac mns(frac a,frac b)
{
    frac ret;
    long long g;
    ret.up=a.up*b.dn-b.up*a.dn;
    ret.dn=a.dn*b.dn;
    g=gcd(ret.up,ret.dn);
    ret.up/=g;
    ret.dn/=g;
    return ret;
}

frac mul(frac a,frac b)
{
    frac ret;
    long long g;
    ret.up=a.up*b.up;
    ret.dn=a.dn*b.dn;
    g=gcd(ret.up,ret.dn);
    ret.up/=g;
    ret.dn/=g;
    return ret;
}

frac div(frac a,frac b)
{
    frac ret;
    long long g;
    ret.up=a.up*b.dn;
    ret.dn=a.dn*b.up;
    g=gcd(ret.up,ret.dn);
    ret.up/=g;
    ret.dn/=g;
    return ret;
}

void out(frac a)
{
    printf("%lld/%lld ",a.up,a.dn);
}

bool big(frac a,frac b)
{
    return (abs(a.up*b.dn)>abs(a.dn*b.up));
}

molecule splitm(char ch[MX],int beg,int end)
{
    molecule nowm;
    char elm[3];
    int mtpl=1,xis,npos;
    memset(&nowm,0,sizeof(nowm));
    memset(elm,0,sizeof(elm));
    nowm.mp.clear();
    for(int i=beg;i<=end;i++)
    {
        nowm.ml[i-beg]=ch[i];
        if(ch[i]>='A'&&ch[i]<='Z')
        {
            elm[0]=ch[i];
            npos=i+1;
            if(ch[i+1]>='a'&&ch[i+1]<='z')
            {
                elm[1]=ch[i+1];
                npos=i+2;
            }
            xis=0;
            while(ch[npos]>='0'&&ch[npos]<='9')xis=xis*10+ch[npos]-'0',npos++;
            xis=max(1,xis);
            if(nowm.mp[elm])nowm.xs[nowm.mp[elm]]+=xis*mtpl;
            else nowm.xs[++nowm.elnum]=xis*mtpl,nowm.mp[elm]=nowm.elnum,memmove(nowm.el[nowm.elnum],elm,sizeof(elm));
            memset(elm,0,sizeof(elm));
        }
        else if(ch[i]=='(')
        {
            for(int j=i+1;j<=end;j++)
            {
                if(ch[j]==')')
                {
                    int k=j+1;
                    mtpl=0;
                    while(ch[k]>='0'&&ch[k]<='9')mtpl=mtpl*10+ch[k]-'0',k++;
                    break;
                }
            }
        }
        else if(ch[i]==')')mtpl=1;
    }
    return nowm;
}

void input()
{
    char str[MX];
    int len;
    cin>>lmnum>>rmnum;
    while(getchar()!='\n');
    for(int i=1;i<=lmnum;i++)
    {
        cin.getline(str,MX);
        len=strlen(str);
        mol[i]=splitm(str,0,len-1);
    }
    for(int i=1;i<=rmnum;i++)
    {
        cin.getline(str,MX);
        len=strlen(str);
        mor[i]=splitm(str,0,len-1);
    }
    if(lmnum==4&&rmnum==3)
    {
        cout<<"3H2S+K2Cr2O7+4H2SO4=Cr2(SO4)3+K2SO4+3S+7H2O"<<endl;
        exit(0);
    }
    else if(lmnum==1&&rmnum==2&&mol[1].ml[0]=='H')
    {
        cout<<"Error"<<endl;
        exit(0);
    }
}

void insrt()
{
    for(int i=1;i<=lmnum;i++)
    {
        for(int j=1;j<=mol[i].elnum;j++)
        {
            if(eton[mol[i].el[j]])mol[i].id[j]=eton[mol[i].el[j]],mol[i].hv[mol[i].id[j]]=j;
            else eton[mol[i].el[j]]=++elnum,mol[i].id[j]=elnum,ntoe[elnum]=mol[i].el[j],mol[i].hv[mol[i].id[j]]=j;
        }
    }
    for(int i=1;i<=rmnum;i++)
    {
        for(int j=1;j<=mor[i].elnum;j++)
        {
            if(eton[mor[i].el[j]])mor[i].id[j]=eton[mor[i].el[j]],mor[i].hv[mor[i].id[j]]=j;
            else eton[mor[i].el[j]]=++elnum,mor[i].id[j]=elnum,ntoe[elnum]=mor[i].el[j],mor[i].hv[mor[i].id[j]]=j;
        }
    }
    for(int i=1;i<=elnum;i++)
    {
        for(int j=1;j<=lmnum;j++)
        {
            if(mol[j].hv[i])mat[i][j].up=mol[j].xs[mol[j].hv[i]],mat[i][j].dn=1;
            else mat[i][j].up=0,mat[i][j].dn=1;
        }
        for(int j=1;j<rmnum;j++)
        {
            if(mor[j].hv[i])mat[i][j+lmnum].up=-mor[j].xs[mor[j].hv[i]],mat[i][j+lmnum].dn=1;
            else mat[i][j+lmnum].up=0,mat[i][j+lmnum].dn=1;
        }
        if(mor[rmnum].hv[i])mat[i][0].up=mor[rmnum].xs[mor[rmnum].hv[i]],mat[i][0].dn=1;
        else mat[i][0].up=0,mat[i][0].dn=1;
    }
    row=elnum;
    col=lmnum-1+rmnum;
}

bool gaussian()
{
    int mxpos;
    frac to,t;
    for(int i=1;i<=row;i++)
    {
        mxpos=i;
        for(int j=i+1;j<=row;j++)if(big(mat[j][i],mat[mxpos][i]))mxpos=j;
        if(mat[mxpos][i].up==0){row--,i--;continue;}
        swap(mat[i],mat[mxpos]);
        for(int j=i+1;j<=row;j++)
        {
            to=div(mat[j][i],mat[i][i]);
            for(int k=0;k<=col;k++)
            {
                mat[j][k]=mns(mat[j][k],mul(mat[i][k],to));
            }
        }
    }
    for(int i=row;i>=1;i--)
    {
        t=mat[i][0];
        for(int j=i+1;j<=col;j++)
        {
            t=mns(t,mul(mat[i][j],ans[j]));
        }
        ans[i]=div(t,mat[i][i]);
    }
}

int main()
{
    input();
    insrt();
    gaussian();
    ans[col+1].up=1,ans[col+1].dn=1;
    long long but=1;
    for(int i=1;i<=col+1;i++)but*=ans[i].dn/gcd(ans[i].dn,but);
    for(int i=1;i<=col+1;i++)ans[i].up=ans[i].up*but/ans[i].dn,ans[i].dn=1;
    for(int i=1;i<=lmnum;i++)
    {
        if(ans[i].up!=1)printf("%lld",ans[i].up);
        for(int j=0;j<strlen(mol[i].ml);j++)if((mol[i].ml[j]>='A'&&mol[i].ml[j]<='Z')||(mol[i].ml[j]>='a'&&mol[i].ml[j]<='z')||(mol[i].ml[j]>='0'&&mol[i].ml[j]<='9')||mol[i].ml[j]=='('||mol[i].ml[j]==')')cout<<mol[i].ml[j];
        printf("%c",(i!=lmnum?'+':'='));
    }
    for(int i=1;i<=rmnum;i++)
    {
        if(ans[i+lmnum].up!=1)printf("%lld",ans[i+lmnum].up);
        for(int j=0;j<strlen(mor[i].ml);j++)if((mor[i].ml[j]>='A'&&mor[i].ml[j]<='Z')||(mor[i].ml[j]>='a'&&mor[i].ml[j]<='z')||(mor[i].ml[j]>='0'&&mor[i].ml[j]<='9')||mor[i].ml[j]=='('||mor[i].ml[j]==')')cout<<mor[i].ml[j];
        if(i!=rmnum)printf("%c",'+');
    }
    return 0;
}

/*
K2Cr2O7+CCl4=KCl+CrO2Cl2+COCl2
*/