310170: CF1792D. Fixed Prefix Permutations
Memory Limit：256 MB
Time Limit：2 S
Judge Style：Text Compare
Creator：
Submit：0
Solved：0
Description
Fixed Prefix Permutations
题意翻译
对于一个排列 $p$，定义其美丽度 $k$ 为 - $p_1=1,p_2=2,\cdots,p_k=k,p_{k+1} \neq k+1$ 若 $p,q$ 均为长度为 $n$ 的排列，定义排列的运算 $p \cdot q$ 为： - $p \cdot q = r$，$p,q,r$ 均为长度为 $n$ 的排列 - $r_j = q_{p_j}$ 现在给出 $n$ 个长度为 $m$ 的排列，对于每一个 $a_i$，求 $a_i \cdot a_j(1 \le j \le n)$ 美丽值最大为多少，允许有 $i=j$。 多测，$T \le 10^4$，$\sum n \le 5 \times 10^4$，$m \le 10$题目描述
You are given $ n $ permutations $ a_1, a_2, \dots, a_n $ , each of length $ m $ . Recall that a permutation of length $ m $ is a sequence of $ m $ distinct integers from $ 1 $ to $ m $ . Let the beauty of a permutation $ p_1, p_2, \dots, p_m $ be the largest $ k $ such that $ p_1 = 1, p_2 = 2, \dots, p_k = k $ . If $ p_1 \neq 1 $ , then the beauty is $ 0 $ . The product of two permutations $ p \cdot q $ is a permutation $ r $ such that $ r_j = q_{p_j} $ . For each $ i $ from $ 1 $ to $ n $ , print the largest beauty of a permutation $ a_i \cdot a_j $ over all $ j $ from $ 1 $ to $ n $ (possibly, $ i = j $ ).输入输出格式
输入格式
The first line contains a single integer $ t $ ( $ 1 \le t \le 10^4 $ ) — the number of testcases. The first line of each testcase contains two integers $ n $ and $ m $ ( $ 1 \le n \le 5 \cdot 10^4 $ ; $ 1 \le m \le 10 $ ) — the number of permutations and the length of each permutation. The $ i $ -th of the next $ n $ lines contains a permutation $ a_i $ — $ m $ distinct integers from $ 1 $ to $ m $ . The sum of $ n $ doesn't exceed $ 5 \cdot 10^4 $ over all testcases.
输出格式
For each testcase, print $ n $ integers. The $ i $ -th value should be equal to the largest beauty of a permutation $ a_i \cdot a_j $ over all $ j $ ( $ 1 \le j \le n $ ).
输入输出样例
输入样例 #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 7Input
题意翻译
对于一个排列 $p$，定义其美丽度 $k$ 为 - $p_1=1,p_2=2,\cdots,p_k=k,p_{k+1} \neq k+1$ 若 $p,q$ 均为长度为 $n$ 的排列，定义排列的运算 $p \cdot q$ 为： - $p \cdot q = r$，$p,q,r$ 均为长度为 $n$ 的排列 - $r_j = q_{p_j}$ 现在给出 $n$ 个长度为 $m$ 的排列，对于每一个 $a_i$，求 $a_i \cdot a_j(1 \le j \le n)$ 美丽值最大为多少，允许有 $i=j$。 多测，$T \le 10^4$，$\sum n \le 5 \times 10^4$，$m \le 10$Output
**固定前缀排列**
**题意翻译**
对于一个排列 $p$，定义其美丽度 $k$ 为
- $p_1=1,p_2=2,\cdots,p_k=k,p_{k+1} \neq k+1$
若 $p,q$ 均为长度为 $n$ 的排列，定义排列的运算 $p \cdot q$ 为：
- $p \cdot q = r$，$p,q,r$ 均为长度为 $n$ 的排列
- $r_j = q_{p_j}$
现在给出 $n$ 个长度为 $m$ 的排列，对于每一个 $a_i$，求 $a_i \cdot a_j(1 \le j \le n)$ 美丽值最大为多少，允许有 $i=j$。
多测，$T \le 10^4$，$\sum n \le 5 \times 10^4$，$m \le 10$。
**题目描述**
给定 $ 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 \neq 1 $，那么美丽度为 $ 0 $。
两个排列 $ p $ 和 $ q $ 的乘积是一个排列 $ r $，使得 $ r_j = q_{p_j} $。
对于每个 $ i $ 从 $ 1 $ 到 $ n $，打印出所有 $ j $ 从 $ 1 $ 到 $ n $（可能 $ i = j $）的排列 $ a_i \cdot a_j $ 的最大美丽值。
**输入输出格式**
**输入格式**
第一行包含一个整数 $ t $（$ 1 \le t \le 10^4 $）——测试用例的数量。
每个测试用例的第一行包含两个整数 $ n $ 和 $ m $（$ 1 \le n \le 5 \times 10^4 $；$ 1 \le m \le 10 $）——排列的数量和每个排列的长度。
接下来的 $ n $ 行中的第 $ i $ 行包含一个排列 $ a_i $——$ m $ 个从 $ 1 $ 到 $ m $ 的不同整数。
所有测试用例的 $ n $ 之和不超过 $ 5 \times 10^4 $。
**输出格式**
对于每个测试用例，打印 $ n $ 个整数。第 $ i $ 个值应等于所有 $ j $（$ 1 \le j \le n $）的排列 $ 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
```**固定前缀排列** **题意翻译** 对于一个排列 $p$，定义其美丽度 $k$ 为 - $p_1=1,p_2=2,\cdots,p_k=k,p_{k+1} \neq k+1$ 若 $p,q$ 均为长度为 $n$ 的排列，定义排列的运算 $p \cdot q$ 为： - $p \cdot q = r$，$p,q,r$ 均为长度为 $n$ 的排列 - $r_j = q_{p_j}$ 现在给出 $n$ 个长度为 $m$ 的排列，对于每一个 $a_i$，求 $a_i \cdot a_j(1 \le j \le n)$ 美丽值最大为多少，允许有 $i=j$。 多测，$T \le 10^4$，$\sum n \le 5 \times 10^4$，$m \le 10$。 **题目描述** 给定 $ 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 \neq 1 $，那么美丽度为 $ 0 $。 两个排列 $ p $ 和 $ q $ 的乘积是一个排列 $ r $，使得 $ r_j = q_{p_j} $。 对于每个 $ i $ 从 $ 1 $ 到 $ n $，打印出所有 $ j $ 从 $ 1 $ 到 $ n $（可能 $ i = j $）的排列 $ a_i \cdot a_j $ 的最大美丽值。 **输入输出格式** **输入格式** 第一行包含一个整数 $ t $（$ 1 \le t \le 10^4 $）——测试用例的数量。 每个测试用例的第一行包含两个整数 $ n $ 和 $ m $（$ 1 \le n \le 5 \times 10^4 $；$ 1 \le m \le 10 $）——排列的数量和每个排列的长度。 接下来的 $ n $ 行中的第 $ i $ 行包含一个排列 $ a_i $——$ m $ 个从 $ 1 $ 到 $ m $ 的不同整数。 所有测试用例的 $ n $ 之和不超过 $ 5 \times 10^4 $。 **输出格式** 对于每个测试用例，打印 $ n $ 个整数。第 $ i $ 个值应等于所有 $ j $（$ 1 \le j \le n $）的排列 $ 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 ```
**题意翻译**
对于一个排列 $p$，定义其美丽度 $k$ 为
- $p_1=1,p_2=2,\cdots,p_k=k,p_{k+1} \neq k+1$
若 $p,q$ 均为长度为 $n$ 的排列，定义排列的运算 $p \cdot q$ 为：
- $p \cdot q = r$，$p,q,r$ 均为长度为 $n$ 的排列
- $r_j = q_{p_j}$
现在给出 $n$ 个长度为 $m$ 的排列，对于每一个 $a_i$，求 $a_i \cdot a_j(1 \le j \le n)$ 美丽值最大为多少，允许有 $i=j$。
多测，$T \le 10^4$，$\sum n \le 5 \times 10^4$，$m \le 10$。
**题目描述**
给定 $ 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 \neq 1 $，那么美丽度为 $ 0 $。
两个排列 $ p $ 和 $ q $ 的乘积是一个排列 $ r $，使得 $ r_j = q_{p_j} $。
对于每个 $ i $ 从 $ 1 $ 到 $ n $，打印出所有 $ j $ 从 $ 1 $ 到 $ n $（可能 $ i = j $）的排列 $ a_i \cdot a_j $ 的最大美丽值。
**输入输出格式**
**输入格式**
第一行包含一个整数 $ t $（$ 1 \le t \le 10^4 $）——测试用例的数量。
每个测试用例的第一行包含两个整数 $ n $ 和 $ m $（$ 1 \le n \le 5 \times 10^4 $；$ 1 \le m \le 10 $）——排列的数量和每个排列的长度。
接下来的 $ n $ 行中的第 $ i $ 行包含一个排列 $ a_i $——$ m $ 个从 $ 1 $ 到 $ m $ 的不同整数。
所有测试用例的 $ n $ 之和不超过 $ 5 \times 10^4 $。
**输出格式**
对于每个测试用例，打印 $ n $ 个整数。第 $ i $ 个值应等于所有 $ j $（$ 1 \le j \le n $）的排列 $ 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
```**固定前缀排列** **题意翻译** 对于一个排列 $p$，定义其美丽度 $k$ 为 - $p_1=1,p_2=2,\cdots,p_k=k,p_{k+1} \neq k+1$ 若 $p,q$ 均为长度为 $n$ 的排列，定义排列的运算 $p \cdot q$ 为： - $p \cdot q = r$，$p,q,r$ 均为长度为 $n$ 的排列 - $r_j = q_{p_j}$ 现在给出 $n$ 个长度为 $m$ 的排列，对于每一个 $a_i$，求 $a_i \cdot a_j(1 \le j \le n)$ 美丽值最大为多少，允许有 $i=j$。 多测，$T \le 10^4$，$\sum n \le 5 \times 10^4$，$m \le 10$。 **题目描述** 给定 $ 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 \neq 1 $，那么美丽度为 $ 0 $。 两个排列 $ p $ 和 $ q $ 的乘积是一个排列 $ r $，使得 $ r_j = q_{p_j} $。 对于每个 $ i $ 从 $ 1 $ 到 $ n $，打印出所有 $ j $ 从 $ 1 $ 到 $ n $（可能 $ i = j $）的排列 $ a_i \cdot a_j $ 的最大美丽值。 **输入输出格式** **输入格式** 第一行包含一个整数 $ t $（$ 1 \le t \le 10^4 $）——测试用例的数量。 每个测试用例的第一行包含两个整数 $ n $ 和 $ m $（$ 1 \le n \le 5 \times 10^4 $；$ 1 \le m \le 10 $）——排列的数量和每个排列的长度。 接下来的 $ n $ 行中的第 $ i $ 行包含一个排列 $ a_i $——$ m $ 个从 $ 1 $ 到 $ m $ 的不同整数。 所有测试用例的 $ n $ 之和不超过 $ 5 \times 10^4 $。 **输出格式** 对于每个测试用例，打印 $ n $ 个整数。第 $ i $ 个值应等于所有 $ j $（$ 1 \le j \le n $）的排列 $ 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 ```