题意:

给你个化学方程式,求配平

题目非常不给力..连数据范围都不给全...

很简单的高斯消元....

开-DH2可以看到调试信息,或者说..真正的方程式..

#include<set>
#include<map>
#include<list>
#include<queue>
#include<stack>
#include<string>
#include<math.h>
#include<time.h>
#include<vector>
#include<bitset>
#include<memory>
#include<utility>
#include<fstream>
#include<stdio.h>
#include<sstream>
#include<iostream>
#include<stdlib.h>
#include<string.h>
#include<algorithm>
using namespace std;
map<string,int> ma;
const int modo=1000000009;
struct part
{
    int chem[25];
    part ()
    {
        memset(chem,0,sizeof(chem));
    }
    friend part operator * (const part &a,int b)
    {
        int i;
        part c=a;
        for (i=0;i<20;i++)
        {
            c.chem[i]*=b;
            if (c.chem[i]<0) c.chem[i]+=modo;
        }
        return c;
    }
    void add(int x,int y)
    {
        chem[x]+=y;
    }
    friend part operator + (const part &a,const part &b)
    {
        part c;
        int i;
        for (i=0;i<20;i++)
        {
            c.chem[i]=a.chem[i]+b.chem[i];
        }
        return c;
    }
};
part a[25];
char c[10005];
int sum=0;
int ans[25];
#ifdef H2
string b[25];
#endif
part get_val(int l,int r)
{
    if (l>r)
    {
        return part();
    }
    if (c[l]=='(')
    {
        int i;
        int tot=0;
        for (i=l;i<=r;i++)
        {
            if (c[i]=='(') tot++;
            if (c[i]==')') tot--;
            if (tot==0) break;
        }
        part t=get_val(l+1,i-1);
        int sum=0;
        for (i++;;i++)
        {
            if ((c[i]>'9')||(c[i]<'0')) break;
            sum*=10;
            sum+=c[i]-'0';
        }
        if (c[i-1]==')') sum=1;
        return t*sum+get_val(i,r);
    }
    else
    {
        string x;
        x=c[l];
        if (c[l+1]>='a')
        {
            x+=c[l+1];
            l++;
        }
        if (ma.find(x)==ma.end())
        {
            ma[x]=sum++;
        }
        int sum=0;
        for (l++;;l++)
        {
            if ((c[l]>'9')||(c[l]<'0')) break;
            sum*=10;
            sum+=c[l]-'0';
        }
        if (c[l-1]>='A') sum=1;
        part t=get_val(l,r);
        t.add(ma[x],sum);
        return t;
    }
}
int d[25][25];
int power(int x,int y)
{
    if (y==0) return 1;
    int t=power(x,y/2);
    t=(long long)t*t%modo;
    if (y&1) t=(long long)t*x%modo;
    return t;
}
bool try_ans(int n)
{
    int i;
    for (i=0;i<sum;i++)
    {
        int j;
        for (j=0;j<n;j++)
        {
            d[i][j]=a[j].chem[i];
        }
        for (;j<sum;j++)
        {
            d[i][j]=0;
        }
    }
    int tot=n;
    for (i=0;i<sum;i++)
    {
        int j;
        for (j=i;j<sum;j++)
        {
            if (d[j][i]!=0)
            {
                break;
            }
        }
        if (j==sum) continue;
        int k;
        for (k=0;k<n;k++)
        {
            swap(d[i][k],d[j][k]);
        }
        int t=power(d[i][i],modo-2);
        for (j=0;j<n;j++)
        {
            d[i][j]=(long long)d[i][j]*t%modo;
        }
        for (j=i+1;j<sum;j++)
        {
            for (k=i+1;k<n;k++)
            {
                d[j][k]=((d[j][k]-(long long)d[i][k]*d[j][i])%modo+modo)%modo;
            }
            d[j][i]=0;
        }
        tot--;
    }
    if (tot!=1) return true;
    ans[n-1]=1;
    for (i=n-2;i>=0;i--)
    {
        ans[i]=0;
        int j;
        for (j=i+1;j<n;j++)
        {
            ans[i]=((ans[i]-(long long)ans[j]*d[i][j])%modo+modo)%modo;
        }
    }
    int mini=modo;
    int minsi=0;
    for (i=1;i<100000;i++)
    {
        int j;
        int maxi=0;
        for (j=0;j<n;j++)
        {
            maxi=max((long long)maxi,(long long)ans[j]*i%modo);
        }
        if (maxi<mini)
        {
            mini=maxi;
            minsi=i;
        }
    }
    for (i=0;i<n;i++)
    {
        ans[i]=(long long)ans[i]*minsi%modo;
        if (ans[i]==0) return true;
        if (ans[i]>100000) return true;
    }
    return false;
}
int main()
{
    #ifdef absi2011
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    #endif
    int n,m;
    int zu=0;
    for (;;)
    {
        scanf("%d%d",&n,&m);
        if ((n==0)&&(m==0)) break;
        sum=0;
        ma.clear();
        int i;
        for (i=0;i<n;i++)
        {
            scanf("%s",c);
            a[i]=get_val(0,strlen(c)-1);
            #ifdef H2
            b[i]=c;
            #endif
        }
        for (i=n;i<n+m;i++)
        {
            scanf("%s",c);
            a[i]=get_val(0,strlen(c)-1)*-1;
            #ifdef H2
            b[i]=c;
            #endif
        }
        zu++;
        printf("Case %d: ",zu);
        if (try_ans(n+m))
        {
            printf("No\n");
            continue;
        }
        for (i=0;i<n+m;i++)
        {
            #ifdef H2
            if (ans[i]!=1)
            #endif
            printf("%d",ans[i]);
            #ifdef H2
            printf("%s",b[i].c_str());
            #endif
            printf(" ");
            #ifdef H2
            if (i==n-1)
            {
                printf("=== ");
            }
            else if (i!=n+m-1)
            {
                printf("+ ");
            }
            #endif
        }
        printf("\n");
    }
    return 0;
}