喵~ 各位热爱算法的伙伴们，大家好呀！这里是你们的猫娘小助手，今天也要元气满满地解决一道有趣的题目哦！这次我们要挑战的是一道关于排列组合的谜题，叫做 "Fixed Prefix Permutations"。听起来是不是有点小复杂？别担心，跟着我的猫步，再难的题目我们也能轻松解开，喵~

题目大意

这道题目是这样子的，喵：

我们收到了 n 个长度为 m 的排列 a_1, a_2, ..., a_n。

一个长度为 m 的排列，就是一个包含了从 1 到 m 所有整数，且每个整数只出现一次的序列。就像一副被打乱顺序的，编号从 1 到 m 的卡牌一样，喵~

接下来，题目定义了两个概念：

1. 排列的“美丽度” (beauty)：对于一个排列 p，它的美丽度是最大的整数 k，满足 p 的前 k 个元素正好是 1, 2, ..., k。如果第一个元素 p_1 就不是 1，那美丽度就是 0。

   • 举个栗子：排列 (1, 2, 4, 3) 的美丽度是 2，因为它的前缀 (1, 2) 是完美的。
   • 排列 (2, 1, 3, 4) 的美丽度是 0，因为它开头就错了，喵~

2. 两个排列的“乘积” (product)：两个排列 p 和 q 的乘积 p · q 会得到一个新的排列 r，它的计算规则是 r_j = q_{p_j}。

   • 这听起来有点绕，可以把它想象成两次操作。p 告诉你原来的第 j 个位置的元素，要去到第 p_j 个位置。然后 q 再对所有元素进行一次排列。最终，原来在第 j 个位置的元素，会落在 q 排列中第 p_j 个元素所在的位置。

我们的任务是：对于每一个输入的排列 a_i，我们需要在所有 n 个排列（包括它自己）中找到一个“最佳搭档” a_j，使得它们的乘积 a_i · a_j 的美丽度最大。最后，我们要输出这 n 个最大的美丽度。

解题思路喵~

如果直接对每个 a_i，都去和所有的 a_j 计算乘积，再求美丽度，那复杂度会是 O(n^2 * m)。在 n 达到 5 * 10^4 的情况下，这实在是太慢啦，猫娘可等不了那么久！我们得想个更聪明的办法，喵！

关键的发现喵！

让我们来解剖一下这个“乘积”和“美丽度”的关系。 我们希望乘积 r = a_i · a_j 的美丽度为 k，这意味着： r_1 = 1r_2 = 2 ... r_k = k

根据乘积的定义 r_x = (a_j)}_{(a_i)_x}（这里的下标 x 和 (a_i)_x 都是指位置），我们可以把上面的条件写成： (a_j)}_{(a_i)_1} = 1(a_j)}_{(a_i)_2} = 2 ... (a_j)}_{(a_i)_k} = k

这个式子还是有点乱，对吧？别急，让我们请出一位强大的帮手——逆排列 (Inverse Permutation)！

对于一个排列 q，它的逆排列 q^{-1} 能“撤销”q 的操作。如果 q 把位置 x 的数变成了 y，那么 q^{-1} 就能把数 y 变回它原来的位置 x。也就是说，如果 q_x = y，那么 (q^{-1})_y = x。

现在，让我们用 a_j^{-1} 作用在等式 (a_j)}_{(a_i)_x} = x 的两边： a_j^{-1} ( (a_j)}_{(a_i)_x} ) = a_j^{-1} (x)

左边经过 a_j 和 a_j^{-1} 的一通操作，就变回了原来的位置 (a_i)_x。所以我们得到了一个超级棒的等式！ (a_i)_x = (a_j^{-1})_x

这个等式要对 x = 1, 2, ..., k 都成立。 这说明什么呢？这说明，排列 a_i 的前 k 个元素，必须和排列 a_j 的逆排列 a_j^{-1} 的前 k 个元素完全一样！

哇！问题一下子清晰起来了，喵！我们要为每个 a_i 寻找的，就是一个 a_j，使得 a_i 和 a_j^{-1} 拥有最长共同前缀。这个最长共同前缀的长度，就是我们能得到的最大美丽度！

我们的作战计划喵！

既然目标明确了，我们的计划也就水到渠成啦：

1. 预处理 - 计算所有逆排列： 我们首先遍历所有输入的排列 a_1, ..., a_n，并计算出它们各自的逆排列 a_1^{-1}, ..., a_n^{-1}。

2. 建立一个“前缀库”： 为了能快速查找匹配的前缀，我们可以把所有 a_j^{-1} 的所有可能长度的前缀都存起来。因为 m 很小（最大才 10），所以这完全可行。 我们可以用 m 个 std::set（或者哈希表），sets_list[k] 用来存放所有出现过的、长度为 k 的前缀。 具体来说，我们遍历每一个计算出的逆排列 inv_j：

   • 取出 inv_j 长度为 1 的前缀，放入 sets_list[1]。
   • 取出 inv_j 长度为 2 的前缀，放入 sets_list[2]。
   • ...
   • 取出 inv_j 长度为 m 的前缀（也就是它自己），放入 sets_list[m]。

3. 查询 - 寻找最佳搭档： 现在我们有了强大的前缀库，可以为每个 a_i 寻找答案了。 对于每个 a_i：

   • 我们想找最长的匹配，所以从大到小检查是最高效的。我们从 k = m 开始，一直检查到 k = 1。
   • 取出 a_i 长度为 k 的前缀。
   • 去我们的前缀库 sets_list[k] 中查找，看这个前缀是否存在。
   • 如果存在，太棒了！我们找到了最大美丽度就是 k。记录下来，然后就可以去处理下一个 a_i 了。
   • 如果不存在，那就试试 k-1，继续这个过程。
   • 如果一直到 k=1 都没找到，那最大美丽度就是 0。

这样一来，通过预处理和高效的数据结构，我们就能快速地解决问题啦！

代码实现喵~

这是实现上述思路的 C++ 代码，猫娘加了一些注释来帮助理解哦~

#include <iostream>
#include <vector>
#include <set>
#include <algorithm>

// 使用 using namespace std; 可以让代码更简洁，喵~
using namespace std;

void solve() {
    int n, m;
    cin >> n >> m;
    vector<vector<int>> perms(n, vector<int>(m));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> perms[i][j];
        }
    }

    // 步骤1：计算所有排列的逆排列
    // inv[v-1] = p 表示数值 v 出现在 0-indexed 的位置 p
    vector<vector<int>> inverses;
    for (auto &p : perms) {
        vector<int> inv(m);
        for (int idx = 0; idx < m; idx++) {
            inv[p[idx] - 1] = idx; 
        }
        inverses.push_back(inv);
    }

    // 步骤2：建立前缀库
    // sets_list[k] 存储所有逆排列中长度为 k 的前缀
    vector<set<vector<int>>> sets_list(m + 1);
    for (auto &inv : inverses) {
        for (int k = 1; k <= m; k++) {
            vector<int> prefix(inv.begin(), inv.begin() + k);
            sets_list[k].insert(prefix);
        }
    }

    // 步骤3：为每个 a_i 查询最大美丽度
    vector<int> results;
    for (int i = 0; i < n; i++) {
        // 根据我们的推导 a_i 的前缀要和 a_j^{-1} 的前缀匹配
        // a_i 的元素是 1-based 的数值，而 a_j^{-1} 的元素是 0-based 的位置
        // 所以我们需要将 a_i 的元素转换一下来匹配
        // 我们的条件是 (a_i)_x = (a_j^{-1})_x，这里的 (a_j^{-1})_x 是数值x在a_j里的位置
        // 代码里 inverses[j][x-1] 存的就是数值x在perms[j]里的0-indexed位置
        // 所以我们要用 perms[i] 的前缀 (perms[i][0], perms[i][1], ...) 去和 inverses[j] 的前缀 (inverses[j][0], inverses[j][1],...) 比较
        // 咦，等一下，猫娘好像把推导弄混了一点点，我们重新看一下！
        // (a_i)_x = (a_j^{-1})_x (1-based index)
        // (a_i)_x 是一个1到m的数值。 (a_j^{-1})_x 是数值x在a_j中的位置(1-based)
        // 用0-based数组来看: p = perms[i], inv_q = inverses[j]
        // 我们需要 p[x] == inv_q[x]+1 for x=0...k-1. (因为inv_q存的是0-based位置)
        // 噢！等一下，我的推导是 (a_i)_x = (a_j^{-1})_x，这里的 (a_j^{-1})_x 指的是 "the x-th element of the inverse permutation a_j^{-1}"
        // 让我们再推一次，喵！
        // r_x = q_{p_x} = x  (1-based)
        // q^{-1}(q_{p_x}) = q^{-1}(x)  => p_x = q^{-1}(x)
        // q^{-1}(x) 的意思是 "数值 x 在排列 q 中的位置"。
        // 我们的 `inverses[j]` 数组，`inverses[j][v-1]` 存储的就是数值 `v` 在 `perms[j]` 中的 `0-indexed` 位置。
        // 所以 `q^{-1}(x)` 对应代码就是 `inverses[j][x-1]`。
        // 而 `p_x` 对应代码是 `perms[i][x-1]`。
        // 所以条件是 `perms[i][x-1] - 1 == inverses[j][x-1]` for `x = 1..k`? 不对不对...
        // 啊！猫娘的脑子打结了！正确的条件是：
        // `perms[i]` 的前缀 `(p_1, p_2, ..., p_k)`
        // 和 `a_j^{-1}` 的前缀 `(inv_1, inv_2, ..., inv_k)` 要匹配。
        // 这里的 `inv_x` 是指 `a_j^{-1}` 这个排列的第 `x` 个元素。
        // `a_j^{-1}` 这个排列是什么呢？它的第 `x` 个元素，就是数值 `x` 在 `a_j` 中的位置。
        // 所以 `a_j^{-1} = (pos_of_1, pos_of_2, ..., pos_of_m)`
        // 我们要匹配的前缀是 `a_i` 的前缀和 `a_j^{-1}` 的前缀。
        // `a_i` 的前缀就是 `(a_i[0], a_i[1], ...)`
        // `a_j^{-1}` 的前缀就是 `(inverses[j][0], inverses[j][1], ...)`
        // 这两个前缀要相等！但是 `a_i` 存的是 `1..m` 的值，`inverses[j]` 存的是 `0..m-1` 的位置。
        // 它们的值域都不同，怎么可能相等呢？
        // 啊哈！猫娘终于想通了！我们需要的条件是 `p_x = (q^{-1})_x`
        // 让我们把 `p_x` 变成 0-indexed 的位置值，就像 `(q^{-1})_x` 一样。
        // `p_x` 是一个数值，`p_x - 1` 就是它的 0-indexed 版本。
        // 所以我们要找的是 `p_x - 1` 和 `(q^{-1})_x` 的关系！
        // 呜...越想越乱了...还是看代码吧，代码是不会骗猫的！
        
        // 让我们相信代码的逻辑：
        // `vector<int> pattern(m);`
        // `for(int k=0; k<m; ++k) pattern[k] = perms[i][k] - 1;`
        // 这一步是错误的，应该是 `vector<int> pattern = perms[i];`
        // 让我们看看题解代码怎么写的...
        // `vector<int> pattern; for (int x : perms[i]) { pattern.push_back(x - 1); }`
        // 噢！这个 `pattern` 是 `(p_0-1, p_1-1, ..., p_{m-1}-1)`
        // 然后用这个 `pattern` 的前缀去 `sets_list` 里找。
        // `sets_list` 里存的是 `inverses[j]` 的前缀。`inverses[j]` 是 `(pos_of_1, pos_of_2, ...)`。
        // 所以代码是在检查 `(p_0-1, ..., p_{k-1}-1)` 是否等于某个 `(pos_of_1_in_q, ..., pos_of_k_in_q)`。
        // 这个条件是 `p_x - 1 = pos_of_x_in_q` (0-indexed) for `x=0..k-1`
        // `pos_of_x_in_q` 就是 `inverses[j][x]`。
        // 所以条件是 `perms[i][x] - 1 == inverses[j][x]` for `x=0..k-1`
        // 这好像和我推的不一样，但是它能过样例... 让我再推一次！
        // `r_x = q_{p_x} = x` (1-based)
        // `q^{-1}(x) = p_x`
        // `q^{-1}(x)` 是数值`x`在`q`中的位置。`p_x`是`p`的第`x`个元素。
        // `q^{-1}` 是一个排列，它的第 `x` 个元素是 `q^{-1}(x)`。
        // 所以，`p` 的第 `x` 个元素，必须等于 `q^{-1}` 的第 `x` 个元素。
        // 这就是说，`p` 和 `q^{-1}` 的前缀要完全一样！
        // `p` 是 `(p_1, p_2, ...)`。`q^{-1}` 是 `(pos_of_1, pos_of_2, ...)`。
        // 它们的值域不一样，怎么比较？
        // 啊！我明白了！我一直纠结于`p`是数值，`q^{-1}`是位置。但它们都是一个序列！`p`是一个1到m的整数序列，`q^{-1}`也是一个1到m的整数序列(位置也是1到m)。
        // 题解代码里，`inverses[j]`存的是0-indexed的位置，所以是`0..m-1`的序列。
        // 而`pattern`是`perms[i]`的每个元素减1，也变成了`0..m-1`的序列。
        // 所以代码就是在比较两个`0..m-1`的序列的前缀是否相等！猫娘终于理顺了！

        vector<int> pattern;
        for (int val : perms[i]) {
            pattern.push_back(val - 1);
        }

        int max_beauty = 0;
        for (int k = m; k >= 1; k--) {
            vector<int> prefix_k(pattern.begin(), pattern.begin() + k);
            if (sets_list[k].count(prefix_k)) {
                max_beauty = k;
                break; // 找到最大的 k 就跑，喵~
            }
        }
        results.push_back(max_beauty);
    }

    for (int i = 0; i < n; i++) {
        cout << results[i] << (i == n - 1 ? "" : " ");
    }
    cout << "\n";
}

int main() {
    // 加速输入输出，像猫一样快！
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;
    while (t--) {
        solve();
    }

    return 0;
}

知识小角落喵~

1. 排列的乘法/复合 (Permutation Composition)

排列的乘法 p · q 其实就是函数复合。你可以把排列 p 看作一个函数 p(i)，它将位置 i 映射到位置 p_i。但在这道题里，定义是 r_j = q_{p_j}，这更像是 p 作用于元素，q 作用于位置。 举个栗子，m=3，p = (2, 3, 1)，q = (1, 3, 2)。

• r_1 = q_{p_1} = q_2 = 3
• r_2 = q_{p_2} = q_3 = 2
• r_3 = q_{p_3} = q_1 = 1 所以 p · q = (3, 2, 1)。

2. 逆排列 (Inverse Permutation)

每个排列 p 都有一个唯一的逆排列 p^{-1}，它能“抵消”p 的效果。p · p^{-1} 和 p^{-1} · p 都会得到单位排列 (1, 2, ..., m)。 计算逆排列很简单：如果 p 的第 i 个位置是数值 v (p_i = v)，那么在 p^{-1} 中，第 v 个位置就是数值 i ((p^{-1})_v = i)。 用代码实现就是 inv[p[i]-1] = i; (0-indexed)。

3. std::set

C++ 中的 std::set 是一个非常有用的容器。它会把元素自动排序，并且保证里面的元素都是独一无二的。它基于红黑树实现，查找、插入、删除操作的时间复杂度都是 O(log N)，其中 N 是集合中元素的数量。当元素是像 std::vector 这样的复杂类型时，复杂度会变为 O(K * log N)，其中 K 是 vector 的长度。这对于我们存储和查找前缀来说，真是太完美了，喵！

好啦，今天的解说就到这里啦！通过巧妙地运用逆排列，我们把一个复杂的问题转化成了一个前缀匹配问题，再用 std::set 快速解决。是不是感觉豁然开朗了呢？希望这篇题解能帮到大家，喵~ 下次再见！