题目描述

问题模拟了在一个大型代码库中查找功能重复的代码模块。我们简化了这个问题：
功能重复定义: 如果两个模块对于相同的输入总是产生相同的输出，则认为它们功能重复。
输出简化: 每个模块的输出被简化为一个整数序列。

给定 $N$ 个功能模块和 $M$ 个测试输入。对于每个模块，我们已知它对这 $M$ 个测试输入的 $M$ 个输出（均为整数）。

任务是：
1. 找出共有多少种 不同 的功能（即多少种不同的输出序列）。
2. 对于每种不同的功能，统计有多少个模块实现了这个功能。
3. 按照特定顺序输出结果：
* 首先在第一行输出不同功能的总数 $K$。
* 接下来的 $K$ 行，每行代表一种功能，格式为：模块数量 功能对应的M个输出。
* 这 $K$ 行需要排序：首先按“模块数量”非递增（即从大到小）排序；如果模块数量相同，则按“功能对应的输出序列”的字典序升序排序。

序列字典序定义：序列 $A = \{A_1, \dots, A_M\}$ 比序列 $B = \{B_1, \dots, B_M\}$ “小”，是指存在 $1 \le i < M$ 使得 $A_1=B_1, \dots, A_i=B_i$ 且 $A_{i+1} < B_{i+1}$。（注：这似乎是一个稍微不同于标准字典序的定义，标准字典序是比较第一个不同的元素。但 C++ 中 vector 的 < 运算符实现的正是标准的字典序比较，即从头开始比较，第一个不同的元素决定大小。题目中的定义似乎在说，如果前 $i$ 个相同，比较第 $i+1$ 个，这和标准字典序是一致的。所以我们直接使用 vector 的比较即可。）

样例

输入:
7 3
35 28 74
-1 -1 22
28 74 35
-1 -1 22
11 66 0
35 28 74
35 28 74

输出:
4
3 35 28 74
2 -1 -1 22
1 11 66 0
1 28 74 35

说明：
共有 7 个模块，3 个测试输入。
模块 1, 6, 7 的输出序列是 {35, 28, 74}。
模块 2, 4 的输出序列是 {-1, -1, 22}。
模块 3 的输出序列是 {28, 74, 35}。
模块 5 的输出序列是 {11, 66, 0}。
共有 4 种不同的功能（输出序列）。
按模块数量降序排列：
1. {35, 28, 74} 出现 3 次。
2. {-1, -1, 22} 出现 2 次。
3. {11, 66, 0} 出现 1 次。
4. {28, 74, 35} 出现 1 次。
对于数量同为 1 的两个功能，按输出序列字典序升序排列：{11, 66, 0} < {28, 74, 35}。
所以最终输出顺序如样例所示。

算法 (哈希/映射 + 排序)

$O(N M \log N + K M \log K)$ 其中 K 为不同功能的数量 (K ≤ N)

思路分析

1. 识别相同功能: 问题的核心在于如何识别出哪些模块具有相同的功能。根据题意，功能由其对 $M$ 个输入的 $M$ 个输出序列唯一确定。因此，如果两个模块的输出序列完全相同，它们就具有相同的功能。

2. 分组与计数: 我们需要统计每种不同的输出序列（即每种功能）出现了多少次（即有多少个模块实现了它）。

   • 一个自然的想法是使用一种数据结构来存储遇到的每种输出序列，并记录其出现的次数。
   • 由于输出序列是一个整数列表（长度为 M），我们可以使用 std::vector<int> 来表示它。
   • 为了高效地查找和计数，std::map 是一个非常合适的选择。我们可以创建一个 std::map<std::vector<int>, int>，其中 key 是输出序列 (vector<int>)，value 是该序列出现的次数 (int)。
   • 遍历 $N$ 个模块：对于每个模块，读取其 $M$ 个输出，构成一个 vector<int> seq。然后，将这个 seq 作为键，在 map 中对应的值加 1 (freq[seq]++)。map 会自动处理键的比较和存储，将相同的序列归为一类。

3. 整理结果: 遍历完所有 $N$ 个模块后，map 中就存储了所有不同的功能（输出序列）及其对应的模块数量。

   • map 的大小 (freq.size()) 就是不同功能的总数 $K$。
   • 我们需要将 map 中的信息转换成题目要求的输出格式，并按照指定的规则排序。

4. 排序:

   • 创建一个结构体 Info，包含两个成员：count (模块数量) 和 outputs (vector<int>，输出序列)。
   • 创建一个 std::vector<Info> 类型的列表 res。
   • 遍历 map (freq)：对于 map 中的每一个键值对 (sequence, count)，创建一个 Info 对象 {count, sequence} 并添加到 res 列表中。
   • 为 Info 结构体定义一个自定义的小于运算符 operator<，以实现题目要求的排序规则：
     • 优先比较 count，按降序排列（即 a.count > b.count 时 a 应该排在前面）。
     • 如果 count 相等，则比较 outputs 序列，按升序字典序排列（即 a.outputs < b.outputs 时 a 排在前面）。
     • 完整的比较逻辑是：if (count != other.count) return count > other.count; else return outputs < other.outputs;
   • 使用 std::sort(res.begin(), res.end()) 对 res 列表进行排序。std::sort 会使用我们定义的 operator<。

5. 输出:

   • 首先输出不同功能的数量 $K$，即 res.size()。
   • 然后遍历排序后的 res 列表。对于每个 Info 对象：
     • 输出 info.count。
     • 接着输出 info.outputs 中的 $M$ 个整数，每个整数前加一个空格。
     • 输出换行符。

时间复杂度

• 读取输入并填充 map: 遍历 N 个模块，每个模块读取 M 个整数。将一个长度为 M 的 vector 作为键插入或更新 map 的时间复杂度约为 $O(M \log K’)$，其中 $K’$ 是当前 map 中的不同键的数量 ($K’ \le N$)。总时间复杂度约为 $O(N \times M \log N)$。
• 将 map 转换为 vector: 遍历 map 中的 K 个元素，复制 vector (长度 M)，时间复杂度为 $O(K \times M)$。
• 排序 vector: 对 K 个 Info 对象排序。每次比较两个 Info 对象：首先比较 count (O(1))，如果 count 相等，则比较两个长度为 M 的 vector (最坏 O(M))。排序总复杂度为 $O(K \log K \times M)$。

• 输出结果: 遍历 K 个 Info 对象，输出 M 个整数，时间复杂度为 $O(K \times M)$。

• 整体复杂度: 主要由填充 map 和排序决定，约为 $O(N M \log N + K M \log K)$。由于 $K \le N$，可以简化为 $O(N M \log N)$。

  • 对于 $N = 10^4, M = 100$， $N M \log N \approx 10^4 \times 100 \times \log_2(10^4) \approx 10^6 \times 14 \approx 1.4 \times 10^7$，这个复杂度在 2 秒的时间限制内是可行的。

C++ 代码

#include <bits/stdc++.h> // 引入所有标准库

using namespace std;

// 定义类型别名 (虽然本题未使用 i64 等)
using i64 = long long;
using u64 = unsigned long long;
using u32 = unsigned;

// 定义结构体 Info，用于存储每个不同功能的信息
struct Info {
    int count;              // 实现该功能的模块数量
    vector<int> outputs;    // 该功能对应的 M 个输出序列

    // 重载小于运算符，用于自定义排序规则
    bool operator<(const Info& other) const {
        // 首先按 count 降序比较
        if (count != other.count) {
            return count > other.count; // count 大的排在前面
        }
        // 如果 count 相等，按 outputs 序列的字典序升序比较
        return outputs < other.outputs; // vector 的 < 运算符默认实现字典序比较
    }
};

int main() {
    // 关闭 C++ 标准 IO 流与 C stdio 的同步，提高 cin/cout 速度
    std::ios::sync_with_stdio(false);
    // 解除 cin 和 cout 的绑定，进一步提速
    std::cin.tie(nullptr);

    int n, m; // N: 模块数量, M: 测试输入数量 (即输出序列长度)
    std::cin >> n >> m;

    // 使用 map 来统计每种输出序列出现的频率
    // key: vector<int> (输出序列)
    // value: int (出现的次数)
    std::map<std::vector<int>, int> freq;

    // 循环读取 N 个模块的输出
    for (int i = 0; i < n; ++i) {
        std::vector<int> seq(m); // 存储当前模块的输出序列
        for (int j = 0; j < m; ++j) {
            std::cin >> seq[j]; // 读取 M 个输出
        }
        // 将该序列在 map 中的计数加 1
        freq[seq]++;
    }

    // 使用 vector<Info> 来存储待排序和输出的结果
    std::vector<Info> res;
    // 遍历 map，将统计结果转换为 Info 对象存入 vector
    for (const auto& pair : freq) {
        // pair.first 是输出序列 (vector<int>)
        // pair.second 是该序列出现的次数 (int)
        res.push_back({pair.second, pair.first}); // 构造 Info 对象 {count, outputs}
    }

    // 根据 Info 结构体中定义的 operator< 进行排序
    std::sort(res.begin(), res.end());

    // 输出不同功能的总数 (即 map 的大小或 res 的大小)
    std::cout << res.size() << "\n";

    // 遍历排序后的结果列表
    for (const auto& info : res) {
        // 输出模块数量
        std::cout << info.count;
        // 输出该功能对应的 M 个输出，用空格分隔
        for (int output : info.outputs) {
            std::cout << " " << output;
        }
        // 输出换行符
        std::cout << "\n";
    }

    return 0; // 程序正常结束
}