POJ2947高斯消元+同餘方程

Description

Input

Output

Sample Input

2 3
2 MON THU
1 2
3 MON FRI
1 1 2
3 MON SUN
1 2 2
10 2
1 MON TUE 
3
1 MON WED
3
0 0

Sample Output

8 3
Inconsistent data.

Hint

Source

#include <iostream>
#include <cstring>
#include <stdio.h>
using namespace std;
#define maxn 305
int equ,var,prime;
//char st[80];
char data[7][5]= {"MON","TUE","WED","THU","FRI","SAT","SUN"};
int aa[maxn][maxn],x[maxn];
inline int abs1(int x)
{
    if (x>=0) return x;
    else
        return -1*x;
}
inline int gcd(int a, int b)
{
    int t;
    while (b != 0)
    {
        t = b;
        b = a % b;
        a = t;
    }
    return a;
}
inline int lcm(int a, int b)
{
    return a * b / gcd(a, b);
}
int extgcd(int a, int b, int & x, int & y)
{
    if (b == 0)
    {
        x=1;
        y=0;
        return a;
    }
    int d = extgcd(b, a % b, x, y);
    int t = x;
    x = y;
    y = t - a / b * y;
    return d;
}
int Gauss()
{
    int i,j,k;
    int max_r , col , temp;
    int LCM , GCD;
    int ta,tb;
    col = 0;
    for(k=0 ; k<equ && col < var ; k++,col++)
    {
        max_r = k;
        for(i=k+1 ; i<equ ; i++)
        {
            if(abs1(aa[i][col]) > abs1(aa[max_r][col]))max_r = i;
        }
        if(max_r != k)
        {
            for(j=k ; j<var+1 ; j++)swap(aa[k][j],aa[max_r][j]);
        }
        if(aa[k][col] == 0)
        {
            k--;
            continue;
        }
        for(i=k+1 ; i<equ ; i++)
        {
            if(aa[i][col] != 0)
            {
                LCM = lcm(abs1(aa[i][col]) , abs1(aa[k][col]));
                ta = LCM/abs1(aa[i][col]) ;
                tb = LCM/abs1(aa[k][col]);
                if(aa[i][col] * aa[k][col] < 0)tb = -tb;
                for(j=col ; j<var+1 ; j++)
                {
                    aa[i][j] = (aa[i][j]*ta-aa[k][j]*tb) % prime;
                    aa[i][j]=(aa[i][j]%7+7)%7;
                }
            }
        }//for
    }
    for(i=k; i<equ; i++)
    {
        if (aa[i][col]!=0) return -1;//無解
    }
    if (k<var) return var-k;// 無窮多解
    for(i=var-1 ; i>=0 ; i--)
    {
        temp = aa[i][var];
        for(j=i+1 ; j<var ; j++)
        {
            if(aa[i][j] != 0) temp =(temp - aa[i][j]*x[j]%prime) ;
//temp=temp-aa[i][j]*x[j];
        }
        temp = (temp%prime + prime) % prime;
        GCD = extgcd(aa[i][i] , prime , x[i] , k);
        x[i] = ( (x[i]*(temp/GCD) % prime) + prime) % prime;
// while(temp%aa[i][i])
// temp+=7;
//x[i]=temp/aa[/i][i];
//x[i]=(x[i]%7+7)%7;
        while(x[i]<3) x[i]=x[i]+7;
//while(x[i]>9) x[i]=x[i]-7;
    }
    return 0;
}
//void init()
//{
// int n=var;
//}
int comp_1(char a[])
{
    int j=0;
    for(int i=0; i<7; i++)
        if (strcmp(a,data[i])==0) j=i;
    cout<<"s="<<j<<endl;
    return j;
}
int main()
{
//`MON', `TUE', `WED', `THU', `FRI', `SAT' and `SUN'.
    int m,n,k,typ;
    int num1,num2;
    char s1[5],s2[5];
    prime=7;
    while(scanf("%d%d",&m,&n))
    {
        if (m==0&&n==0) break;
        var=m; //這個要注意,var!=equ 啊
        equ=n;
//var=equ=m;
        memset(aa,0,sizeof(aa));
        memset(x,0,sizeof(x));
        for(int i=0; i<n; i++)
        {
            scanf("%d",&k);
            scanf("%s %s",s1,s2);
            for(int i=0; i<7; i++)
            {
                if (strcmp(s1,data[i])==0)
                    num1=i;
                if (strcmp(s2,data[i])==0)
                    num2=i;
            }
            int day=(num2-num1+1+7)%7;
// cout<<day<<endl;
            for(int j=0; j<k; j++)
            {
                scanf("%d",&typ);
                aa[i][typ-1]++;
                aa[i][typ-1]%=7;
            }
            aa[i][m]=day;
        }
        int free_num=Gauss();
        if (free_num==-1) cout<<"Inconsistent data."<<endl;
        if (free_num>0) cout<<"Multiple solutions."<<endl;
        if (free_num==0)
        {
            for(int i=0; i<var-1; i++)
                cout<<x[i]<<" ";
            cout<<x[var-1]<<endl;
        }
    }
//cout << "Hello world!" << endl;
    return 0;
}