「Widget Factory」 小部件厂

GitHub跳转原题关系图返回列表

把「每条记录 = 一个线性等式」写成模 7 同余方程组，用高斯消元求解；3..9 天与 7 个剩余类一一对应，无解/自由元分别判 Inconsistent/Multiple。

OJ: roj

题目 ID: 3101

难度:提高+/省选-

标签:高斯消元同余线性代数数学python

创建: 2026-10-01 17:06

更新: 2026-10-07 13:50

目录

  1. 形式化题目
  2. 正解
    1. 思路
      1. 代码
      2. 复杂度
    2. 总结
    3. 图示解析

    形式化题目

    有 nn 种型号的小部件，第 jj 种型号的制作耗时 xjx_j 天，且由题面保证 xj∈{3,4,…,9}x_j\in\{3,4,\dots,9\}。 另有 mm 条工人记录，第 ii 条记录给出：

    • 该工人开工与收工是星期几（一周 7 天，首尾都算在工作日内）；
    • 他在这段时间里依次做完的 kik_i 个部件的型号（同一型号可能出现多次）。

    求每种型号的耗时；结果需要区分「唯一」「不唯一」「无解」三种情况。

    记 ci,jc_{i,j} 为型号 jj 在第 ii 条记录中出现的次数，did_i 为该工人的在岗天数。因为 did_i 与「从开工星期 sis_i 数到收工星期 eie_i」相差整数周，得到 mm 条同余方程：

    ∑j=1nci,j xj  ≡  (ei−si+1)(mod7),i=1,2,…,m\sum_{j=1}^{n} c_{i,j}\,x_j \;\equiv\; (e_i - s_i + 1) \pmod 7,\qquad i=1,2,\dots,m

    约束：1⩽n,m⩽3001\leqslant n,m\leqslant 300，1⩽ki⩽100001\leqslant k_i\leqslant 10000，多组测试用例，0 0 结束。

    样例 1 的解是 x1=8, x2=3x_1=8,\ x_2=3（8+3=11≡4(mod7)8+3=11\equiv 4 \pmod 7，正好对应 MON 到 THU 的 4 天）； 样例 2 的两条记录都把同一型号限制成不同的天数，因此无解。

    两个必须先说清的读题点。 其一，天数按首尾都算的方式数：MON THU 是 4 天（周一、二、三、四）， 所以右端是 e−s+1e-s+1 而不是 e−se-s，否则样例立刻出错。 其二，3…9 天共 7 个取值，模 7 后得到 3,4,5,6,0,1,23,4,5,6,0,1,2 七个互不相同的余数， 恰好覆盖全部剩余类，因此「模 7 的解」与「合法天数」一一对应； 这条性质是后面能把方程解直接翻译回天数、并且用「自由元是否为 0」判多解的根据。

    正解

    思路

    朴素做法：枚举天数

    最直接的做法是枚举每组 (x1,…,xn)∈{3,…,9}n(x_1,\dots,x_n)\in\{3,\dots,9\}^n，检查是否满足全部记录。 枚举量是 7n7^n，nn 只有 10 就已经是 2.8×1082.8\times10^8，而数据给了 n⩽300n\leqslant300， 这条路完全走不通。

    朴素做法失败的原因是它没有利用输入的结构：每条记录给的是一个线性等式， 而不是一次需要模拟的过程。把天数当未知量、把记录当方程，问题就落进了线性代数的框架。

    第一步：一条记录 ⇔ 一条同余方程

    一条记录 k s e 后面跟 kk 个型号。该工人的在岗天数等于他做完的 kk 件活的耗时之和； 同一型号做了多次就要加多次。设型号 jj 在第 ii 条记录中出现 ci,jc_{i,j} 次，则

    di=∑j=1nci,jxjd_i = \sum_{j=1}^{n} c_{i,j} x_j

    而我们只看得到星期：工人可能做满几个星期，所以从星期上看不出 did_i 的绝对值， 只能看出它模 7 的值。开工星期 ss、收工星期 ee、首尾都算，故

    di≡ei−si+1(mod7)d_i \equiv e_i - s_i + 1 \pmod 7

    于是每条记录给出一条模 7 的线性同余方程，mm 条记录就是 mm 条方程的方程组 Cx≡d(mod7)C x \equiv d \pmod 7。

    第二步：为什么要用 7，而不是「3 到 9」

    模数选 7 不是随手挑的：合法天数是 3…9 共 7 个数，模 7 后恰好落在 7 个不同的剩余类上， 映射是双射。

    天数 3 4 5 6 7 8 9
    模 7 余数 3 4 5 6 0 1 2

    这带来两个好处：其一，解出的余数 rr 可以唯一还原成天数——r⩾3r\geqslant3 时天数就是 rr， 否则天数 =r+7=r+7（即 0/1/2 分别对应 7/8/9 天），不需要再额外判断；其二， 「余数有多组解」与「天数有多组解」是同一件事，所以直接数自由元就够了。

    第三步：模 7 高斯消元

    77 是素数，Z7\mathbb{Z}_7 是域，非零元素都有乘法逆元（2−1=42^{-1}=4、3−1=53^{-1}=5、4−1=24^{-1}=2、 5−1=35^{-1}=3、6−1=66^{-1}=6）。于是实线性代数的整套手法原样可用，只需把除法换成「乘逆元」：

    1. 逐列找主元，把主元行换上来，整行乘逆元归一化成 1；
    2. 用主元行把它下方该列消成 0（只往下消，具体值留到回代再算， 比每一步都上下通消的高斯-约当少掉大约一半的整行运算）；
    3. 消完后检查：
      • 出现系数全 0 而右端非 0 的行（0≡c0 \equiv c，c≠0c\ne0）→ 无解，输出 Inconsistent data.；
      • 主元个数 <n< n → 有自由元，把自由元全取 0 就得到一组解，故至少两组解 → Multiple solutions.；
      • 主元个数 =n=n → 唯一解，逆序回代求出每个 xjx_j，还原成天数输出。

    每找到一个主元就要扫一遍它下方的行、并对每行处理长度不超过 nn 的后缀，主元最多 min⁡(n,m)\min(n,m) 个，所以消元是 O(mnmin⁡(n,m))O\bigl(mn\min(n,m)\bigr)，n,m⩽300n,m\leqslant300 时约 2.7×1072.7\times10^7 次模运算，与朴素枚举的 7n7^n 不可同日而语。

    用样例核对

    样例 1 的三条记录转成方程（n=2n=2）：

    记录 x1x_1 x2x_2 右端 di mod 7d_i \bmod 7
    1 2 MON THU 1 1 3−0+1=43-0+1=4
    2 3 MON FRI 2 1 4−0+1=54-0+1=5
    3 3 MON SUN 1 2 6−0+1=06-0+1=0

    第 2 行减去第 1 行得 x1≡1x_1 \equiv 1，第 3 行减去第 1 行得 x2≡3x_2 \equiv 3； 按「r⩾3r\geqslant3 时取 rr，否则取 r+7r+7」还原为 x1=8x_1=8、x2=3x_2=3，与样例输出 8 3 一致。

    样例 2 的两条记录分别是 MON TUE 与 MON WED，右端为 2 和 3， 都只涉及型号 3，于是 x3≡2x_3\equiv2 与 x3≡3x_3\equiv3 矛盾，输出 Inconsistent data.。

    代码

    Python 版：

    python
    #!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-01 17:06
# update_at: 2026-10-01 17:15

import sys
from collections import Counter
from collections.abc import Iterator
from itertools import islice

DAYS = [b"MON", b"TUE", b"WED", b"THU", b"FRI", b"SAT", b"SUN"]  # 星期几 → 0..6
INV = [0, 1, 4, 5, 2, 3, 6]  # 模 7 的乘法逆元：3·5、2·4、6·6、1·1 都同余 1，INV[0] 用不到
MOD = 7
MIN_DAYS = 3  # 单件耗时下界；余数小于它时加一个周期 7 即还原成 7/8/9 天

UNIQUE, MULTIPLE, INCONSISTENT = 0, 1, 2  # 方程组解的状态；只有 UNIQUE 才有确定的答案
TEXT = {MULTIPLE: "Multiple solutions.", INCONSISTENT: "Inconsistent data."}


def tokens() -> Iterator[bytes]:
    """按行产出输入词元：整份数据有 450 万个数字，一次性读入会多占几百 MB。"""
    for line in sys.stdin.buffer:
        yield from line.split()


def read_case(data: Iterator[bytes], n: int, m: int) -> tuple[list[list[int]], list[int]]:
    """读入 m 条工人记录，返回 (模 7 系数矩阵, 右端余数向量)。

    第 i 条记录给出一条同余方程 sum_j c[i][j] * x_j ≡ d_i (mod 7)：
    c[i][j] 是型号 j 在这批活里出现的次数（同型号做几次就累加几次耗时），
    d_i 是工人在岗天数对 7 取余，开工星期 s、收工星期 e、首尾都算，故 d_i ≡ e - s + 1。
    """
    mat: list[list[int]] = []
    rhs: list[int] = []
    for _ in range(m):
        k = int(next(data))
        start, end = next(data), next(data)
        counts = Counter(map(int, islice(data, k)))
        mat.append([counts[v] % MOD for v in range(1, n + 1)])
        rhs.append((DAYS.index(end) - DAYS.index(start) + 1) % MOD)
    return mat, rhs


def gauss(mat: list[list[int]], rhs: list[int], n: int) -> tuple[int, list[int]]:
    """模 7 高斯消元：先消成阶梯形，再回代，返回 (解的状态, 一组特解)。

    7 是素数，非零系数都有逆元，所以消元过程与实数域一样，只是把除法换成乘逆元。
    """
    pivot_cols: list[int] = []
    for col in range(n):
        pivot = next((r for r in range(len(pivot_cols), len(mat)) if mat[r][col]), None)
        if pivot is None:  # 剩余行在这一列全是 0，说明 x[col] 是自由元
            continue
        rank = len(pivot_cols)
        mat[rank], mat[pivot] = mat[pivot], mat[rank]
        rhs[rank], rhs[pivot] = rhs[pivot], rhs[rank]
        inv = INV[mat[rank][col]]  # 主元归一化成 1
        mat[rank] = [0] * col + [v * inv % MOD for v in mat[rank][col:]]
        rhs[rank] = rhs[rank] * inv % MOD
        for r in range(rank + 1, len(mat)):  # 只往下消成阶梯形，回代时再算具体值
            factor = mat[r][col]
            if factor:
                row = mat[r]
                # 补上前导 0 是为了让「列下标」始终等于变量的编号
                mat[r] = [0] * col + [(v - factor * w) % MOD for v, w in zip(row[col:], mat[rank][col:])]
                rhs[r] = (rhs[r] - factor * rhs[rank]) % MOD
        pivot_cols.append(col)
        if len(pivot_cols) == len(mat):  # 每条方程都拿到主元，剩下的只可能是 0 = 0
            break

    x = [0] * n
    if any(rhs[len(pivot_cols):]):  # 系数全 0 而右端非 0 的行形如 0 = c，方程无解
        return INCONSISTENT, x
    if len(pivot_cols) < n:  # 自由元取 0 就是一组解，故至少两族解对应多组天数
        return MULTIPLE, x
    for i in range(n - 1, -1, -1):  # 回代：主元列右侧的变量此时都已确定
        col = pivot_cols[i]
        x[col] = (rhs[i] - sum(v * x[j] for j, v in enumerate(mat[i][col + 1:], col + 1))) % MOD
    return UNIQUE, x


def solve() -> None:
    data = tokens()
    out: list[str] = []
    while True:
        n, m = int(next(data)), int(next(data))
        if n == 0 and m == 0:
            break
        mat, rhs = read_case(data, n, m)
        state, x = gauss(mat, rhs, n)
        # 耗时 3..9 天与模 7 的 7 个剩余类一一对应：0/1/2 分别还原成 7/8/9 天。
        out.append(" ".join(str(r if r >= MIN_DAYS else r + MOD) for r in x) if state == UNIQUE else TEXT[state])

    sys.stdout.write("\n".join(out) + "\n")


if __name__ == "__main__":
    solve()

    C++ 版（同一算法）：

    cpp
    /**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-06 18:44
 * update_at: 2026-10-06 18:44
 */

// main.cpp：把每条工人记录看成一条模 7 的线性同余方程，用高斯消元判定
// 无解 / 多解 / 唯一解，并把唯一解的余数还原成 3..9 天。
//
// 关键建模：
//   - 设型号 j 在一条记录里出现 c 次，则工人在岗天数 d = sum c[j] * x[j]（同型号做几次加几次）；
//   - 记录只给星期，首尾都算，所以 d ≡ e - s + 1 (mod 7)，得到一条模 7 方程；
//   - 合法天数 3..9 共 7 个，模 7 后恰好覆盖 7 个剩余类（0/1/2 对应 7/8/9），
//     因此「模 7 有多组解」等价于「天数有多组解」，余数可唯一还原成天数；
//   - 7 是素数，Z_7 是域，除法换成乘逆元即可照搬高斯消元。

#include <cstdio>
#include <cstring>
#include <string>
#include <iostream>

typedef long long ll;

const int MAXN = 305;   // 型号数 n <= 300
const int MAXM = 305;   // 记录数 m <= 300
const int MOD = 7;      // 一周 7 天，方程都在模 7 意义下

// 模 7 的乘法逆元：1->1, 2->4, 3->5, 4->2, 5->3, 6->6（2*4、3*5、6*6 都 ≡ 1）
const int INV[MOD] = {0, 1, 4, 5, 2, 3, 6};

// 星期字符串转 0..6：day_num("MON") = 0, ..., day_num("SUN") = 6
int day_num(const char *s) {
    const char *DAYS[MOD] = {"MON", "TUE", "WED", "THU", "FRI", "SAT", "SUN"};
    for (int i = 0; i < MOD; ++i)
        if (strcmp(s, DAYS[i]) == 0)
            return i;
    return -1; // 题面保证输入合法，不会走到这里
}

// 系数矩阵与右端向量：a[i][j] 是第 i 条方程里 x_j 的系数（已对 7 取余）
ll a[MAXM][MAXN];
ll b[MAXM];  // b[i] = 第 i 条方程的右端 d_i mod 7
ll x[MAXN];  // 唯一解时每个型号的耗时（余数形式，0..6）
ll cnt[MAXN]; // 读记录时的临时计数：cnt[j] = 型号 j 在本条记录出现的次数

int n, m;

// 读入一条记录并转成一条方程：sum_j c[j] * x_j ≡ e - s + 1 (mod 7)
bool read_record(int i) {
    ll k;
    char s1[10], s2[10];
    if (scanf("%lld %9s %9s", &k, s1, s2) != 3)
        return false;
    for (int j = 1; j <= n; ++j) cnt[j] = 0; // 只清这题会用到的下标范围
    for (ll t = 0; t < k; ++t) {
        int v;
        scanf("%d", &v);
        cnt[v]++; // 同型号出现 c 次，耗时累加 c 次，系数就是 c
    }
    for (int j = 1; j <= n; ++j)
        a[i][j] = cnt[j] % MOD;
    // 在岗天数首尾都算，右端是 (收工 - 开工 + 1) mod 7
    b[i] = ((day_num(s2) - day_num(s1) + 1) % MOD + MOD) % MOD;
    return true;
}

// 模 7 高斯消元（7 是素数，非零系数都有逆元）
// 返回值：0 = 唯一解，1 = 多解，2 = 无解；唯一解时结果存入 x[]
int gauss() {
    int r = 0; // 已处理的主元行数（也是当前的秩）
    for (int col = 1; col <= n && r < m; ++col) {
        int p = -1; // 在 r..m-1 行里找这一列系数非 0 的主元行
        for (int i = r; i < m; ++i)
            if (a[i][col] != 0) { p = i; break; }
        if (p == -1)
            continue; // 这一列全是 0，x[col] 是自由元
        // 把主元行换上来
        for (int j = col; j <= n; ++j) {
            ll t = a[r][j]; a[r][j] = a[p][j]; a[p][j] = t;
        }
        ll tb = b[r]; b[r] = b[p]; b[p] = tb;
        // 主元归一化成 1：整行乘主元的逆元
        ll inv = INV[a[r][col]];
        for (int j = col; j <= n; ++j)
            a[r][j] = a[r][j] * inv % MOD;
        b[r] = b[r] * inv % MOD;
        // 用主元行把它下方各行消成 0（只往下消，回代时再算具体值）
        for (int i = r + 1; i < m; ++i) {
            ll f = a[i][col];
            if (f == 0) continue;
            for (int j = col; j <= n; ++j)
                a[i][j] = (a[i][j] - f * a[r][j] % MOD + MOD) % MOD;
            b[i] = (b[i] - f * b[r] % MOD + MOD) % MOD;
        }
        r++; // 主元个数增加
    }
    // 消元后第 r..m-1 行的系数已全为 0，检查有没有 0 ≡ c (c ≠ 0) 的矛盾行
    for (int i = r; i < m; ++i)
        if (b[i] != 0)
            return 2; // Inconsistent data.
    if (r < n)
        return 1;     // 有自由元，自由元取 0 就是一组解，故天数不唯一
    // 满秩，逆序回代求出每个 x[j]
    for (int i = r - 1; i >= 0; --i) {
        // 找到这一行的主元列
        int col = 1;
        while (col <= n && a[i][col] == 0) col++;
        x[col] = b[i];
        for (int j = col + 1; j <= n; ++j)
            x[col] = (x[col] - a[i][j] * x[j] % MOD + MOD) % MOD;
    }
    return 0;
}

// 处理一组测试用例，返回 false 表示读到 n = m = 0 的结束标记
bool solve_case() {
    if (scanf("%d %d", &n, &m) != 2)
        return false;
    if (n == 0 && m == 0)
        return false;
    for (int i = 0; i < m; ++i)
        read_record(i);
    int st = gauss();
    if (st == 2) {
        printf("Inconsistent data.\n");
    } else if (st == 1) {
        printf("Multiple solutions.\n");
    } else {
        // 余数 0/1/2 对应 7/8/9 天，其余直接就是天数
        for (int j = 1; j <= n; ++j) {
            ll d = x[j] < 3 ? x[j] + MOD : x[j];
            printf("%lld%c", d, j == n ? '\n' : ' ');
        }
    }
    return true;
}

int main() {
    while (solve_case())
        ;
    return 0;
}

    代码与上面的推导一一对应：

    • read_case 是「记录 → 方程」：Counter(map(int, islice(data, k))) 一次遍历统计每个 型号的出现次数（对应 ci,jc_{i,j}），DAYS.index(end) - DAYS.index(start) + 1 对应右端 ei−si+1e_i-s_i+1；
    • gauss 是模 7 消元：INV 表存模 7 的逆元（2⋅4=8≡12\cdot4=8\equiv1、3⋅5=15≡13\cdot5=15\equiv1、 6⋅6=36≡16\cdot6=36\equiv1，11 的逆元是它自己）， 前向消元把主元行以下的该列清成 0，pivot_cols 记录主元列。消元结束后，下标 ⩾\geqslant 主元数的那些行系数已经全是 0，于是 any(rhs[len(pivot_cols):]) 就是 「有没有 0≡c0\equiv c 的行」的判定，而 len(pivot_cols) < n 是「主元够不够 nn 个」的判定；
    • solve 只管还原与输出：余数 ⩾3\geqslant3 直接当天数，否则加 7。

    复杂度

    设一组数据的型号数为 nn、记录数为 mm、总部件数为 K=∑ikiK=\sum_i k_i。

    • 读入 O(K)O(K)（真实数据里 K≈4.5×106K\approx4.5\times10^6，是本题最大的常数项）；
    • 建方程 O(mn)O(mn)；
    • 高斯消元 O(mnmin⁡(n,m))O\bigl(mn\min(n,m)\bigr)（主元最多 min⁡(n,m)\min(n,m) 个），回代 O(n2)O(n^2)；
    • 空间 O(mn)O(mn) 存矩阵，不随 KK 增长。

    朴素枚举是 O(7n)O(7^n)，完全不可比。实测真实数据 g1.in（13.7 MB，26 组，总部件数约 4.5×1064.5\times10^6）：约 0.9 s、峰值 16 MB。时间贴近 1000 ms 的限制线，Python 被卡常的风险 客观存在（同样算法在 C++ 里是 0.05 s 量级）；内存则离 128 MB 很远。

    实现上有一处必须强调：输入不能一次性 read().split()。整份数据有约 450 万个数字， 全部转成 bytes 对象会占到 257 MB，直接 MLE。代码里改成按行流式产出词元， 峰值内存降到 16 MB。

    总结

    本题的全部难度在建模，不在写代码：

    1. 一条记录 = 一条线性方程：天数是未知量，同型号做几次就累加几次系数；
    2. 只在模 7 下成立：星期只能给出在岗天数模 7 的余数，右端是 e−s+1e-s+1；
    3. 3…9 天 ↔ 7 个剩余类：这个一一对应让「解出的余数」能唯一还原成天数， 也让「自由元个数」直接决定是唯一解还是多解；
    4. 模 7 是域：高斯消元照搬，无解判 0≡c0\equiv c，多解判主元个数 <n<n。

    最需要留心的两个细节是天数首尾都算（e−s+1e-s+1）与同型号重复出现的累加； 最容易踩的工程坑是输入规模导致的 MLE。

    图示解析

    这张图串起本题从输入到答案的主线：

    text
    输入: m 条记录 (开工星期 s, 收工星期 e, k 个型号)
|- 在岗天数 = 型号耗时求和 (同型号出现 c 次就加 c 次)
|- 星期只确定"模 7": d ≡ e - s + 1 (mod 7)  ->  m 条同余方程 C x ≡ d
`- 7 是素数 -> 高斯消元 (除法 = 乘逆元)
   |- 有 0 ≡ c (c != 0) 的行     -> Inconsistent data.
   |- 主元个数 < n (存在自由元)   -> Multiple solutions.
   `- 主元个数 = n -> 回代得 x; 余数 r < 3 时加 7 (即 0/1/2 -> 7/8/9)

    从上往下看：先是把「一个工人的在岗天数」写成型号耗时的加权和，再意识到记录只给出 模 7 的余数，于是得到同余方程组；因为 7 是素数，消元过程与实数域完全相同；最后只剩三种 出口，分别对应无解、多解和唯一解。最后一步的「余数加 7」正是前面那张天数↔余数对照表给 出的双射，图中每一步都对应正文已经说明的结论，不替代 ### 思路 里的样例推演。