library

This documentation is automatically generated by online-judge-tools/verification-helper

View the Project on GitHub beet-aizu/library

:heavy_check_mark: test/aoj/1300.test.cpp

Depends on

Code

// verification-helper: PROBLEM http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1300

#include<bits/stdc++.h>
using namespace std;

#define call_from_test
#include "../../string/split.cpp"
#include "../../vector/compress.cpp"
#include "../../mod/mint.cpp"
#undef call_from_test

using S = map<string, int>;
S add(S x,S y){
  for(auto p:y)
    x[p.first]+=p.second;
  return x;
}
S mul(S x,int k){
  for(auto &p:x)
    p.second*=k;
  return x;
}

S term(string s){
  S res;
  int n=s.size();
  for(int i=0;i<n;){
    if(s[i]=='('){
      int j=s.find(')',i);
      string t=s.substr(i+1,j-(i+1));
      auto tmp=term(t);
      i=j+1;
      if(i==n) continue;
      if(isdigit(s[i])){
        int num=0;
        while(i<n&&isdigit(s[i]))
          num=num*10+(s[i]-'0'),i++;
        tmp=mul(tmp,num);
      }
      res=add(res,tmp);
      continue;
    }
    assert(isupper(s[i]));
    string c;
    c+=s[i],i++;
    while(i<n&&islower(s[i])) c+=s[i],i++;
    int num=0;
    while(i<n&&isdigit(s[i]))
      num=num*10+(s[i]-'0'),i++;
    if(num==0) num=1;
    res[c]+=num;
  }
  return res;
}

vector<S> conv(string s){
  vector<S> res;
  for(auto t:split(s,'+'))
    res.emplace_back(term(t));
  return res;
}

signed solve(string s){
  s.pop_back();
  string x=s.substr(0,s.find("->"));
  string y=s.substr(s.find("->")+2);
  auto t1=conv(x);
  auto t2=conv(y);

  vector<string> ms;
  for(auto rs:t1)
    for(auto p:rs)
      ms.emplace_back(p.first);
  for(auto rs:t2)
    for(auto p:rs)
      ms.emplace_back(p.first);
  ms=compress(ms);
  auto dc=dict(ms);

  int n=ms.size();
  int m=t1.size()+t2.size();

  using M = Mint<int>;
  vector< vector<M> > mat(n,vector<M>(m));
  for(int i=0;i<(int)t1.size();i++)
    for(auto p:t1[i])
      mat[dc[p.first]][i]=M(p.second);

  for(int i=0;i<(int)t2.size();i++)
    for(auto p:t2[i])
      mat[dc[p.first]][t1.size()+i]=-M(p.second);

  for(int j=0;j+1<m;j++){
    {
      int k=-1;
      for(int i=j;i<n;i++)
        if(mat[i][j]!=M(0)) k=i;
      assert(~k);
      swap(mat[j],mat[k]);
    }
    for(int k=m-1;k>=j;k--)
      mat[j][k]/=mat[j][j];

    for(int i=j+1;i<n;i++){
      M cof=mat[i][j];
      for(int k=0;k<m;k++)
        mat[i][k]-=cof*mat[j][k];
    }
  }

  for(int j=m-2;j>=0;j--){
    for(int i=0;i<j;i++){
      M cof=mat[i][j];
      for(int k=0;k<m;k++)
        mat[i][k]-=cof*mat[j][k];
    }
  }

  using ll = long long;
  auto check=
    [&](vector<ll> cof)->int{
      map<string, ll> res;
      for(int i=0;i<(int)t1.size();i++)
        for(auto p:t1[i])
          res[p.first]+=p.second*cof[i];
      for(int i=0;i<(int)t2.size();i++)
        for(auto p:t2[i])
          res[p.first]-=p.second*cof[t1.size()+i];
      for(auto p:res)
        if(p.second!=0) return 0;
      return 1;
    };

  const int MAX = 40000;
  for(ll l=1;l<=MAX;l++){
    vector<ll> cof(m,0);
    cof[m-1]=l;
    for(int i=0;i+1<m;i++)
      cof[i]=(-M(l)*mat[i][m-1]).v;
    if(*max_element(cof.begin(),cof.end())>MAX) continue;

    if(check(cof)){
      for(int i=0;i<m;i++){
        if(i) cout<<" ";
        cout<<cof[i];
      }
      cout<<endl;
      break;
    }
  }
  return 0;
}

signed main(){
  string s;
  while(cin>>s,s!=".") solve(s);
  return 0;
}
#line 1 "test/aoj/1300.test.cpp"
// verification-helper: PROBLEM http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1300

#include<bits/stdc++.h>
using namespace std;

#define call_from_test
#line 1 "string/split.cpp"

#line 3 "string/split.cpp"
using namespace std;
#endif
//BEGIN CUT HERE
vector<string> split(string& s,char c){
  int n=s.size();
  vector<string> res;
  for(int i=0;i<n;i++){
    if(s[i]==c) continue;
    res.emplace_back();
    while(i<n and s[i]!=c) res.back()+=s[i++];
  }
  return res;
}
//END CUT HERE
#ifndef call_from_test
signed main(){
  return 0;
}
#endif
#line 1 "vector/compress.cpp"

#line 3 "vector/compress.cpp"
using namespace std;
#endif

//BEGIN CUT HERE
template<typename V>
V compress(V vs){
  sort(vs.begin(),vs.end());
  vs.erase(unique(vs.begin(),vs.end()),vs.end());
  return vs;
}
template<typename T>
map<T, int> dict(const vector<T> &vs){
  map<T, int> res;
  for(int i=0;i<(int)vs.size();i++)
    res[vs[i]]=i;
  return res;
}
map<char, int> dict(const string &s){
  return dict(vector<char>(s.begin(),s.end()));
}
template<typename T>
vector<T> compressed(vector<T> vs){
  auto dc=dict(compress(vs));
  for(auto &v:vs) v=dc[v];
  return vs;
}
//END CUT HERE
#ifndef call_from_test
//INSERT ABOVE HERE
signed main(){
  return 0;
}
#endif
#line 1 "mod/mint.cpp"

#line 3 "mod/mint.cpp"
using namespace std;
#endif

//BEGIN CUT HERE
template<typename T, T MOD = 1000000007>
struct Mint{
  inline static constexpr T mod = MOD;
  T v;
  Mint():v(0){}
  Mint(signed v):v(v){}
  Mint(long long t){v=t%MOD;if(v<0) v+=MOD;}

  Mint pow(long long k){
    Mint res(1),tmp(v);
    while(k){
      if(k&1) res*=tmp;
      tmp*=tmp;
      k>>=1;
    }
    return res;
  }

  static Mint add_identity(){return Mint(0);}
  static Mint mul_identity(){return Mint(1);}

  Mint inv(){return pow(MOD-2);}

  Mint& operator+=(Mint a){v+=a.v;if(v>=MOD)v-=MOD;return *this;}
  Mint& operator-=(Mint a){v+=MOD-a.v;if(v>=MOD)v-=MOD;return *this;}
  Mint& operator*=(Mint a){v=1LL*v*a.v%MOD;return *this;}
  Mint& operator/=(Mint a){return (*this)*=a.inv();}

  Mint operator+(Mint a) const{return Mint(v)+=a;}
  Mint operator-(Mint a) const{return Mint(v)-=a;}
  Mint operator*(Mint a) const{return Mint(v)*=a;}
  Mint operator/(Mint a) const{return Mint(v)/=a;}

  Mint operator+() const{return *this;}
  Mint operator-() const{return v?Mint(MOD-v):Mint(v);}

  bool operator==(const Mint a)const{return v==a.v;}
  bool operator!=(const Mint a)const{return v!=a.v;}

  static Mint comb(long long n,int k){
    Mint num(1),dom(1);
    for(int i=0;i<k;i++){
      num*=Mint(n-i);
      dom*=Mint(i+1);
    }
    return num/dom;
  }
};
template<typename T, T MOD>
ostream& operator<<(ostream &os,Mint<T, MOD> m){os<<m.v;return os;}
//END CUT HERE
#ifndef call_from_test
signed main(){
  return 0;
}
#endif
#line 10 "test/aoj/1300.test.cpp"
#undef call_from_test

using S = map<string, int>;
S add(S x,S y){
  for(auto p:y)
    x[p.first]+=p.second;
  return x;
}
S mul(S x,int k){
  for(auto &p:x)
    p.second*=k;
  return x;
}

S term(string s){
  S res;
  int n=s.size();
  for(int i=0;i<n;){
    if(s[i]=='('){
      int j=s.find(')',i);
      string t=s.substr(i+1,j-(i+1));
      auto tmp=term(t);
      i=j+1;
      if(i==n) continue;
      if(isdigit(s[i])){
        int num=0;
        while(i<n&&isdigit(s[i]))
          num=num*10+(s[i]-'0'),i++;
        tmp=mul(tmp,num);
      }
      res=add(res,tmp);
      continue;
    }
    assert(isupper(s[i]));
    string c;
    c+=s[i],i++;
    while(i<n&&islower(s[i])) c+=s[i],i++;
    int num=0;
    while(i<n&&isdigit(s[i]))
      num=num*10+(s[i]-'0'),i++;
    if(num==0) num=1;
    res[c]+=num;
  }
  return res;
}

vector<S> conv(string s){
  vector<S> res;
  for(auto t:split(s,'+'))
    res.emplace_back(term(t));
  return res;
}

signed solve(string s){
  s.pop_back();
  string x=s.substr(0,s.find("->"));
  string y=s.substr(s.find("->")+2);
  auto t1=conv(x);
  auto t2=conv(y);

  vector<string> ms;
  for(auto rs:t1)
    for(auto p:rs)
      ms.emplace_back(p.first);
  for(auto rs:t2)
    for(auto p:rs)
      ms.emplace_back(p.first);
  ms=compress(ms);
  auto dc=dict(ms);

  int n=ms.size();
  int m=t1.size()+t2.size();

  using M = Mint<int>;
  vector< vector<M> > mat(n,vector<M>(m));
  for(int i=0;i<(int)t1.size();i++)
    for(auto p:t1[i])
      mat[dc[p.first]][i]=M(p.second);

  for(int i=0;i<(int)t2.size();i++)
    for(auto p:t2[i])
      mat[dc[p.first]][t1.size()+i]=-M(p.second);

  for(int j=0;j+1<m;j++){
    {
      int k=-1;
      for(int i=j;i<n;i++)
        if(mat[i][j]!=M(0)) k=i;
      assert(~k);
      swap(mat[j],mat[k]);
    }
    for(int k=m-1;k>=j;k--)
      mat[j][k]/=mat[j][j];

    for(int i=j+1;i<n;i++){
      M cof=mat[i][j];
      for(int k=0;k<m;k++)
        mat[i][k]-=cof*mat[j][k];
    }
  }

  for(int j=m-2;j>=0;j--){
    for(int i=0;i<j;i++){
      M cof=mat[i][j];
      for(int k=0;k<m;k++)
        mat[i][k]-=cof*mat[j][k];
    }
  }

  using ll = long long;
  auto check=
    [&](vector<ll> cof)->int{
      map<string, ll> res;
      for(int i=0;i<(int)t1.size();i++)
        for(auto p:t1[i])
          res[p.first]+=p.second*cof[i];
      for(int i=0;i<(int)t2.size();i++)
        for(auto p:t2[i])
          res[p.first]-=p.second*cof[t1.size()+i];
      for(auto p:res)
        if(p.second!=0) return 0;
      return 1;
    };

  const int MAX = 40000;
  for(ll l=1;l<=MAX;l++){
    vector<ll> cof(m,0);
    cof[m-1]=l;
    for(int i=0;i+1<m;i++)
      cof[i]=(-M(l)*mat[i][m-1]).v;
    if(*max_element(cof.begin(),cof.end())>MAX) continue;

    if(check(cof)){
      for(int i=0;i<m;i++){
        if(i) cout<<" ";
        cout<<cof[i];
      }
      cout<<endl;
      break;
    }
  }
  return 0;
}

signed main(){
  string s;
  while(cin>>s,s!=".") solve(s);
  return 0;
}
Back to top page