POJ 2947 Widget Factory

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
const int N=305;
inline int read(){
    char c=getchar();int x=0,f=1;
    while(c<‘0‘||c>‘9‘){if(c==‘-‘)f=-1;c=getchar();}
    while(c>=‘0‘&&c<=‘9‘){x=x*10+c-‘0‘;c=getchar();}
    return x*f;
}
typedef int Matrix[N][N];
int n,m,P=7;
char s1[5],s2[5];
Matrix a;
int mp[300];
inline int num(char *s){
    if(s[0]==‘T‘) return s[1]==‘U‘?1:3;
    else if(s[0]==‘S‘) return s[1]==‘A‘?5:6;
    else return mp[s[0]];
}
int inv[10];
void iniInv(){
    inv[1]=1;
    for(int i=2;i<=P;i++) inv[i]=(-P/i*inv[P%i]%P+P)%P;
}
int now,pivot[N];
void Gauss(){
    now=1;
    for(int i=1;i<=n;i++){
        int j=now;
        while(j<=m&&!a[j][i]) j++;
        if(j==m+1) continue;
        //printf("hi %d %d %d\n",i,now,j);
        if(j!=now) for(int k=1;k<=n+1;k++) swap(a[now][k],a[j][k]);
        for(int j=now+1;j<=m;j++) if(a[j][i]){//printf("jjj %d\n",j);
            int t=a[j][i]*inv[a[now][i]]%P;//printf("t %d\n",t);
            for(int k=i;k<=n+1;k++) a[j][k]=(a[j][k]-a[now][k]*t%P+P)%P;
        }
        pivot[i]=now;//printf("pivot %d %d\n",i,pivot[i]);
        now++;
    }
    //printf("now %d\n",now);now--;
    for(int i=now;i>=1;i--){
        int pi=pivot[i],pj;
        for(int j=now;j>i;j--) 
            pj=pivot[j],a[pi][n+1]=(a[pi][n+1]-a[pi][pj]*a[pj][n+1]%P+P)%P;
            a[pi][n+1]=a[pi][n+1]*inv[a[pi][i]]%P;
    }
}
void solve(){
    //printf("now %d\n",now);
    //for(int i=1;i<=m;i++)
        //for(int j=1;j<=n+1;j++) printf("%d%c",a[i][j],j==n+1?‘\n‘:‘ ‘);
    for(int i=1;i<=m;i++) if(a[i][n+1]){
        int f=0; 
        for(int j=1;j<=n;j++) if(a[i][j]) {f=1;break;}
        if(f==0){puts("Inconsistent data.");return;}
    }
    if(now<n) {puts("Multiple solutions.");return;}
    for(int i=1;i<=n;i++) printf("%d%c",a[i][n+1]<3?a[i][n+1]+P:a[i][n+1],i==n?‘\n‘:‘ ‘);
}

inline void ini(){memset(a,0,sizeof(a));memset(pivot,0,sizeof(pivot));}
int main(){
    //freopen("in","r",stdin);
    mp[‘M‘]=0;mp[‘W‘]=2;mp[‘F‘]=4;
    iniInv();
    while(true){
        ini();
        n=read();m=read();
        if(n==0&&m==0) break;
        for(int i=1;i<=m;i++){
            int k=read();scanf("%s%s",s1,s2);
            a[i][n+1]=(num(s2)-num(s1)+1+P)%P;
            while(k--) a[i][read()]++;
            for(int j=1;j<=n+1;j++) a[i][j]%=P;
            //printf("a %d\n",i);
            //for(int j=1;j<=n+1;j++) printf("%d%c",a[i][j],j==n+1?‘\n‘:‘ ‘);
        }
        Gauss();
        solve();
    }
}