【高斯消元】UVA1564 Widget Factory

cjrqwq · 2024-07-23 21:23:46 · 题解

观察题目，发现只知道开始和结束是星期几，但是不知道过了几个星期，其实这就是在模意义下的线性方程组。设处理第 i 条记录时，工人工作了 b_i 天，第 j 种零件做了 a_j 个，第 i 种零件的制作时间是 x_i 天，将其表示一下：

\begin{cases} a_{1, 1} x_1 + a_{1, 2} x_2 + \cdots + a_{1, n} x_n \equiv b_1 \pmod 7\\ a_{2, 1} x_1 + a_{2, 2} x_2 + \cdots + a_{2, n} x_n \equiv b_2 \pmod 7\\ \cdots \\ a_{m,1} x_1 + a_{m, 2} x_2 + \cdots + a_{m, n} x_n \equiv b_m\pmod 7 \end{cases}

使用高斯消元的板子求解，把除以一个数变成乘其逆元。但我们发现，解出来可能导致 x=0,x=1,x=2，这不符合题意。根据同余的性质，变成 x=7,x=8,x=9 即可。

同时，题目还要求我们输出无数解，无解的情况。

对于无数解：当 x_i 没有约束，即 a_{i,i} = 0 ，且 a_{i,n+1}=0 时方程组有无数解。
对于无解：当 i \in [1,n] 且 a_{i,i} = 0（此处 x_i 没有约束，但是取任何值都不满足方程条件），且 a_{i,n+1} > 0 或当 i \in [n+1,m] 且 a_{i,n+1} > 0 时方程组无解。

因为不同人的高斯消元写法不同，上文讨论的情况建议结合代码阅读，实现起来细节比较多。

#include<bits/stdc++.h>
using namespace std;
const int N = 3e2+10, mod = 7;
int mi(int x,int k) {int p; return k?p=mi(x,k>>1),p*p%mod*(k&1?x:1)%mod:1;}
int inv(int x) {return mi(x,mod-2);}
int n,m; int a[N][N];
map<string,int>rq;
string s1,s2;
int main() {
    rq["SUN"]=1,rq["MON"]=2,rq["TUE"]=3,rq["WED"]=4, rq["THU"]=5, rq["FRI"]=6,rq["SAT"]=7;
    while(cin>>n>>m,n||m) {
        memset(a,0,sizeof a);
        for(int i=1,K;i<=m;i++) {
            cin>>K>>s1>>s2; a[i][n+1] = (rq[s2]-rq[s1]+mod+1)%mod;
            for(int j=1,x;j<=K;j++) {
                cin>>x;
                a[i][x] = (a[i][x] + 1) % mod;
            }
        }
        /*
            关于高斯消元，我的写法是如果第 i 个主元不存在时，就空着占位置
            这样可以达到只有 $a_{i,i}$ 与 a_{i,n+1} 有值的效果 
        */
        for(int i=1,h;i<=n;i++) {
            h = 0;
            for(int j=1;j<=m;j++)
                if((j>=i || a[j][j] == 0) && a[j][i]) {
                    h = j; break;
                }
            if(h == 0) continue;
            swap(a[i],a[h]);
            for(int j=1;j<=m;j++) {
                if(i == j || a[j][i] == 0) continue;
                int x = a[j][i] * inv(a[i][i]) % mod;
                for(int k=i;k<=n+1;k++)
                    a[j][k] = (a[j][k] - x * a[i][k] % mod + mod) % mod;
            }
        }
        int wj = 0, wsj = 0;
        for(int i=1;i<=m;i++)
            if((!a[i][i] && a[i][n+1]) || (i>n && a[i][n+1])) wj = 1;
        for(int i=1;i<=n;i++)
            if(a[i][i] == 0 && a[i][n+1] == 0) wsj = 1;
        if(wj) cout<<"Inconsistent data.";
        else if(wsj) cout<<"Multiple solutions.";
        else
            for(int i=1,ans;i<=n;i++) {
                 ans = a[i][n+1]*inv(a[i][i]) % 7;
                if(ans <= 2) ans += 7;
                cout<<ans; if(i != n) cout<<' ';
            }
        cout<<"\n";
    }
    return 0;
}