A7391. 固定前缀排列
编程题
普及+/提高
知识点
题目描述
给定 $n$ 个长度为 $m$ 的排列 $a_1,a_2,\dots,a_n$。
长度为 $m$ 的排列，指的是由 $1$ 到 $m$ 这 $m$ 个整数各出现一次组成的序列。
对于一个排列 $p_1,p_2,\dots,p_m$，定义它的“固定前缀长度”为最大的整数 $k$，满足：
$$ p_1=1,p_2=2,\dots,p_k=k $$
如果 $p_1\ne 1$，那么它的固定前缀长度为 $0$。
两个排列 $p$ 和 $q$ 的乘积 $p\cdot q$ 定义为一个新排列 $r$，其中：
$$ r_j=q_{p_j} $$
也就是说，第 $j$ 个位置的值等于 $q$ 中第 $p_j$ 个位置上的数。
现在，对于每个 $i$，你需要在所有 $a_j(1\le j\le n)$ 中选择一个排列，使得 $a_i\cdot a_j$ 的固定前缀长度尽可能大，并输出这个最大值。
注意：可以选择 $j=i$。
长度为 $m$ 的排列，指的是由 $1$ 到 $m$ 这 $m$ 个整数各出现一次组成的序列。
对于一个排列 $p_1,p_2,\dots,p_m$，定义它的“固定前缀长度”为最大的整数 $k$，满足：
$$ p_1=1,p_2=2,\dots,p_k=k $$
如果 $p_1\ne 1$，那么它的固定前缀长度为 $0$。
两个排列 $p$ 和 $q$ 的乘积 $p\cdot q$ 定义为一个新排列 $r$，其中：
$$ r_j=q_{p_j} $$
也就是说，第 $j$ 个位置的值等于 $q$ 中第 $p_j$ 个位置上的数。
现在，对于每个 $i$，你需要在所有 $a_j(1\le j\le n)$ 中选择一个排列，使得 $a_i\cdot a_j$ 的固定前缀长度尽可能大，并输出这个最大值。
注意：可以选择 $j=i$。
输入格式
第一行输入一个整数 $T$，表示测试数据组数。
对于每组测试数据：
第一行输入两个整数 $n,m$，表示排列个数和每个排列的长度。
接下来 $n$ 行，每行输入 $m$ 个整数，表示一个长度为 $m$ 的排列。
对于每组测试数据：
第一行输入两个整数 $n,m$，表示排列个数和每个排列的长度。
接下来 $n$ 行，每行输入 $m$ 个整数，表示一个长度为 $m$ 的排列。
输出格式
对于每组测试数据，输出一行 $n$ 个整数。
第 $i$ 个整数表示：在所有 $j$ 中，$a_i\cdot a_j$ 的固定前缀长度最大是多少。
第 $i$ 个整数表示：在所有 $j$ 中，$a_i\cdot a_j$ 的固定前缀长度最大是多少。
输入输出样例
输入 #1
3 3 4 2 4 1 3 1 2 4 3 2 1 3 4 2 2 1 2 2 1 8 10 3 4 9 6 10 2 7 8 1 5 3 9 1 8 5 7 4 10 2 6 3 10 1 7 5 9 6 4 2 8 1 2 3 4 8 6 10 7 9 5 1 2 3 4 10 6 8 5 7 9 9 6 1 2 10 4 7 8 3 5 7 9 3 2 5 6 4 8 1 10 9 4 3 7 5 6 1 10 8 2
输出 #1
1 4 4 2 2 10 8 1 6 8 10 1 7
说明/提示
对于所有测试数据，满足：
- $1\le T\le 10^4$
- $1\le n\le 5\times 10^4$
- $1\le m\le 10$
- 每个 $a_i$ 都是一个长度为 $m$ 的排列
- 所有测试数据中 $n$ 的总和不超过 $5\times 10^4$
## 样例解释
对于第一组测试数据，三个排列分别为：
$$ a_1=[2,4,1,3] $$
$$ a_2=[1,2,4,3] $$
$$ a_3=[2,1,3,4] $$
先看 $a_1$。
如果选择 $a_3$，那么：
$$ a_1\cdot a_3=[1,4,2,3] $$
这个排列的第 $1$ 个位置是 $1$，但是第 $2$ 个位置不是 $2$，所以固定前缀长度为 $1$。
尝试所有 $a_j$ 后，$a_1\cdot a_j$ 的最大固定前缀长度为 $1$。
再看 $a_2$。
如果选择 $a_2$，那么：
$$ a_2\cdot a_2=[1,2,3,4] $$
这个排列的前 $4$ 个位置都满足：
$$ p_1=1,p_2=2,p_3=3,p_4=4 $$
所以固定前缀长度为 $4$。
再看 $a_3$。
如果选择 $a_3$，那么：
$$ a_3\cdot a_3=[1,2,3,4] $$
所以最大固定前缀长度也是 $4$。
因此第一组测试数据的答案为：
```text
1 4 4
```
对于第二组测试数据，两个排列分别为：
$$ [1,2] $$
和
$$ [2,1] $$
它们都可以通过选择合适的排列，使乘积结果变成：
$$ [1,2] $$
所以答案为：
```text
2 2
```
- $1\le T\le 10^4$
- $1\le n\le 5\times 10^4$
- $1\le m\le 10$
- 每个 $a_i$ 都是一个长度为 $m$ 的排列
- 所有测试数据中 $n$ 的总和不超过 $5\times 10^4$
## 样例解释
对于第一组测试数据，三个排列分别为：
$$ a_1=[2,4,1,3] $$
$$ a_2=[1,2,4,3] $$
$$ a_3=[2,1,3,4] $$
先看 $a_1$。
如果选择 $a_3$，那么：
$$ a_1\cdot a_3=[1,4,2,3] $$
这个排列的第 $1$ 个位置是 $1$，但是第 $2$ 个位置不是 $2$，所以固定前缀长度为 $1$。
尝试所有 $a_j$ 后，$a_1\cdot a_j$ 的最大固定前缀长度为 $1$。
再看 $a_2$。
如果选择 $a_2$，那么：
$$ a_2\cdot a_2=[1,2,3,4] $$
这个排列的前 $4$ 个位置都满足：
$$ p_1=1,p_2=2,p_3=3,p_4=4 $$
所以固定前缀长度为 $4$。
再看 $a_3$。
如果选择 $a_3$，那么：
$$ a_3\cdot a_3=[1,2,3,4] $$
所以最大固定前缀长度也是 $4$。
因此第一组测试数据的答案为：
```text
1 4 4
```
对于第二组测试数据，两个排列分别为：
$$ [1,2] $$
和
$$ [2,1] $$
它们都可以通过选择合适的排列，使乘积结果变成：
$$ [1,2] $$
所以答案为：
```text
2 2
```