固定前缀排列_信奥算法普及+/提高-ACGO题库

题目描述

给定 $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$ 。

输入格式

第一行输入一个整数 $T$ ，表示测试数据组数。

对于每组测试数据：

第一行输入两个整数 $n,m$ ，表示排列个数和每个排列的长度。

接下来 $n$ 行，每行输入 $m$ 个整数，表示一个长度为 $m$ 的排列。

输出格式

对于每组测试数据，输出一行 $n$ 个整数。

第 $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$ 。

因此第一组测试数据的答案为：

1 4 4

对于第二组测试数据，两个排列分别为：

$[1,2]$

和

$[2,1]$

它们都可以通过选择合适的排列，使乘积结果变成：