被这道题折磨了很久，那就写篇题解吧（大雾）

一、背景

这是一道高斯-约旦消元（Guess-Jordan Elimination）的板子题（当然你用纯高斯也行，我嫌烦），与平时的区别就在于本题要取模7，相当于一堆同余方程组（然而这并不影响消元）。

二、题意&&解法

Boss告诉你一堆工人做零件的数据，然后告诉你天数（就相当于告诉了你一堆方程）。我们不妨把式子列出来。

对于每一个工人，我们都有以下式子：

a1 × x1 + a2 × x2 + a3 × x3 …… + an × xn ≡ b(mod 7)
， 其中，0 <= b <= 6。

对于每个零件i，ai表示这个工人做的个数，xi则表示一个零件耗时几天，b就是老板告诉的数据（从星期x到星期y这之间相差几天，模7）。

好的，我们不妨考虑加减同余方程

(a1 - a‘1) × x1 + (a2 - a‘2) × x2 + …… + (an - a’n) × xn ≡ b - b’(mod 7)

这很明显成立（大雾），模7的条件下加减乘都是可以乱搞的。

因此，我们用高斯消元把方程组消消就行了。

三、坑（以下内容可能引起不适）

1.本题没有告诉你m >= n（仿佛看到出题者的奸笑）。你可能会说：m < n，不肯定是多解吗？

然而并不是。

比如:x1 + 2 × x2 + 2 × x3 = 1
x1 + 2 × x2 + 2 × x3 = 0

然后你的正解咕了……

那么怎么判断多解呢?

我们把方程消为简化阶梯矩阵（概念见https://www.cnblogs.com/dclicker/p/9876278.html）

A:如果说当前这一个方程只有一个未知数前有系数，那么肯定不是多解（无解或唯一解，至于为什么过活说）。

B:如果有多个未知数前有系数，那么这里面就有自由元（可以随意变化的未知量），就要撇开这个方程不管，去查别的方程是否有解。

C:如果该方程所有未知数系数都是0，假设右边的常量为0，那么同B处理（好多自由元……），假设常量不是0，那么这个方程就咕了，于是不管别的什么自由元之类的，结果就是无解。

同时，为了避免m < n在消元时的不方便，我就判断：如果m < n,那么就把m个方程放在n~n - m + 1号位置上，前面就放一堆恒等式0=0，这样就方便了找未知数。

然后，去把处理好的简化方程按ABC求解，如果无解那么就直接退出，有解就解，然后开一个变量cnt纪录一共几个未知数有解。如果cnt < n, 那么就是多解。（cnt 不可能比 n 大，因为只要当前未知数消元成功，原方程中就只有至多一个方程是含有该未知数，且是A的情况。）

2.那么以上是不是就是所有特殊情况呢？然而又不是。

还有一种可能是无解的，是在解扩展欧几里得的时候判断的.

a × x ≡ b(mod 7), 假如 a 是 7 的倍数而b不是0，这个方程就又咕了。

3.就算你判断完以上情况，你会发现你还是wa，（我在ACWING上一直Float Point Exception， 大雾了很久），这是为什么呢？原来数字爆long long了……

每次加减乘完了之后要记得模一个七！（错了6次，痛哭流涕~）

4.方程消元切记不能用double（否则自寻死路），这可是模7意义下的方程啊，套个double简直自杀行为。

那么怎么消元呢？

譬如下列两个方程的系数：

2 4 3 | 1

3 1 4 | 2

如果我们想消掉第一项，不能用小数，那怎么办？

模仿通分，乘上对方

第二个方程统统乘上2（第一个方程第一位的系数）：

6 2 8 | 4

然后第一个方程统统乘上3（第二个方程第一位的系数）：

6 12 9 | 3

相减就完事了

四、代码

#include<bits/stdc++.h>
using namespace std;
template <typename T>
inline void readin(T &x) {
    x = 0;
    T fh = 1;
    char ch = getchar();
    for (; !isdigit(ch); ch = getchar()) if (ch == '-') fh = -1;
    for (; isdigit(ch); ch = getchar()) x = (x << 1) + (x << 3) + (ch ^ 48);
    x *= fh;
}
template <typename T>
inline void wt(T x) {
    if (x > 9) wt(x / 10);
    putchar(x % 10 + 48);
}
template <typename T>
inline void writeln(T x, char c) {
    if (x < 0) {
        putchar('-');
        x = -x;
    }
    wt(x);
    putchar(c);
}
const int N = 305;
int c[N][N], b[N], ans[N];
inline int turn(string st) {
    if (st[0] == 'M') return 1;
    if (st[0] == 'W') return 3;
    if (st[0] == 'F') return 5;
    if (st[0] == 'S') {
        if (st[1] == 'A') return 6;
        return 7;
    }
    if (st[0] == 'T') {
        if (st[1] == 'U') return 2;
        return 4;
    }
}
inline int exgcd(int ai, int bi, int &x, int &y) {
    if (!bi) {
        x = 1;
        y = 0;
        return ai;
    }
    int di = exgcd(bi, ai % bi, x, y);
    int tmp = x;
    x = y;
    y = tmp - (ai / bi) * y;
    return di;
}
int main() {
    int n, m, ty, s, t, num;
    string s1, s2;
    readin(n); readin(m);
    while(n && m) {
        bool rev = false; // m < n就要多加方程 
        if (m < n) rev = true;
        for (int i = 1; i <= m; i ++) {
            memset(c[i], 0, sizeof(c[i]));
            readin(ty);
            cin >> s1 >> s2;
            s = turn(s1);
            t = turn(s2);
            if (!rev) b[i] = t - s + 1;
            else b[n - i + 1] = t - s + 1;
            while(ty --) {
                readin(num);
                if (!rev) {
                    c[i][num] ++;
                    c[i][num] %= 7;
                }
                else {
                    c[n - i + 1][num] ++;
                    c[n - i + 1][num] %= 7;
                }
            }
        }
        int las = 1;
        for (int i = 1; i <= n; i ++) {
            if (!c[i][i]) { // 找一个未知量i有系数的方程 
                for (int j = i + 1; j <= max(n, m); j ++) {
                    if (c[j][i]) {
                        for (int k = 1; k <= n; k ++) {
                            swap(c[i][k], c[j][k]);
                        }
                        swap(b[i], b[j]);
                        break;
                    }
                }
            }
            if (!c[i][i]) continue; // 没找到，有可能是自由元，先跳过， 找到了就消元 
            for (int j = 1; j <= max(n, m); j ++) {
                if (c[j][i] && i != j) { 
                    int tmp = c[j][i];
                    for (int k = 1; k <= n; k ++) {
                        c[j][k] = (c[j][k] * c[i][i]) % 7; // 模仿通分 
                    }
                    b[j] *= c[i][i];
                    b[j] %= 7;
                    for (int k = 1; k <= n; k ++) {
                        c[j][k] = (c[j][k] - tmp *c[i][k]) % 7; // 消元 
                    }
                    b[j] -= tmp * b[i];
                    b[j] %= 7;
                }
            }
        }
        int cnt = 0, k1, k2;
        bool flg = false;
        for (int i = 1; i <= max(n, m); i ++) {
            int id = 0;
            for (int k = 1; k <= n; k ++) {
                if (c[i][k] % 7) {
                    if (!id) id = k;
                    else {
                        id = -1;
                        break;
                    }
                }
            }
            if (id == -1) continue; // 有自由元 
            else if (id == 0) { // 系数全部为0 
                if (b[i] == 0) continue;
                puts("Inconsistent data.");
                flg = true;
                break;
            }
            else {
                int d = exgcd(c[i][id], 7, k1, k2);
                if (b[i] % d) { // 扩展欧几里得没有解 
                    puts("Inconsistent data.");
                    flg = true;
                    break;
                }
                else {
                    k1 *= b[i] / d;
                    k1 %= 7;
                    if (k1 < 0) k1 += 7;
                    ans[id] = k1;
                    cnt ++;
                }
            }
        }
        if (!flg) {
            if (cnt < n) { // 解的个数 < n 
                puts("Multiple solutions.");
            }
            else {
                for (int i = 1; i < n; i ++) {
                    if (ans[i] < 3) ans[i] += 7;
                    writeln(ans[i], ' ');
                }
                if (ans[n] < 3) ans[n] += 7;
                writeln(ans[n], '\n');
            }
        }
        memset(b, 0, sizeof(b));
        memset(ans, 0, sizeof(ans));
        for (int i = 1; i <= max(n, m); i ++) {
            memset(c[i], 0, sizeof(c[i]));          
        }       
        // 数组不清空，暴0两行泪 
        readin(n); readin(m);
    }
    return 0;
}

欢迎大家来提问(hack)!