D. Fixed Prefix Permutations

题意

给定 $n$ 个长度为 $m$ 的排列 $a_1,a_2,...a_n$

定义一个排列 $p$ 的 价值 为 最大顺序长度 $k$：$p_1=1,p_2=2,p_3=3,...p_k=k$，如果 $p_1\ne 1$，那么 $p$ 的价值为 $0$

定义两个排列的 乘积 为：$p\cdot q=r，其中r_j=q_{p_j}$

现在对于每个 $i\in [1,n]$，求出 最大 的 $a_i\cdot a_j$（注意 $j$ 可以等于 $i$）

思路

对于当前的 $a_i$，我们需要找到一个 $j$，使得 $a_i\cdot a_j=(1,2,3,4,....k,r_{k+1},....r_m)$ 中的 $k$ 最大
如果 $k$ 刚好等于 $m$ 的话，$a_i\cdot a_j=(1,2,3,4,....,m)$

此时我们转换一下：$a_i=(1,2,3,4,...,m)\cdot a_j^{-1}$

不难发现，对于一个顺序度为 $m$ 的排列 $(1,2,3,4,...,m)$，它乘上 $a_j^{-1}$ 不会改变 $a_j^{-1}$ 的内容

也就是：$a_i=a_j^{-1}$；
更一般地，当 $k<m$ 时，$a_i$ 的前 $k$ 位 与 $a_j^{-1}$ 的前 $k$ 位是 一样 的！

那么我们只需要求出每个 $a_i$ 的 逆，然后再与当前的 $a_i$ 比较，最长公共前缀就是当前 $a_i$ 的答案

如何求逆？由 $p\cdot p^{-1}=[1,2,3,4,...,m]$ 得：$p_{p_j}^{-1}=j$，也就是以 $p$ 为下标映射，$p_j$ 指向的位置一定得为 $j$

那么我们只需要将每个逆存在 $Trie$ 上，对于当前的 $a_i$ 在 $Trie$ 上跑 $LCP$ （最大公共前缀）即可

时间复杂度：$O(nm)$

#include<bits/stdc++.h>
#define fore(i,l,r)	for(int i=(int)(l);i<(int)(r);++i)
#define fi first
#define se second
#define endl '\n'
#define ull unsigned long long
#define ALL(v) v.begin(), v.end()
#define Debug(x, ed) std::cerr << #x << " = " << x << ed;const int INF=0x3f3f3f3f;
const long long INFLL=1e18;typedef long long ll;const int N = 500050;struct node{int son[11];
}tree[N];int cnt = 0;int main(){std::ios::sync_with_stdio(false);std::cin.tie(nullptr);std::cout.tie(nullptr);int t;std::cin >> t;while(t--){int n, m;std::cin >> n >> m;std::vector<int> ans(n + 1, 0);std::vector<std::vector<int>> a(n + 1, std::vector<int>(m + 1, 0));fore(i, 1, n + 1)fore(j, 1, m + 1)std::cin >> a[i][j];fore(i, 1, n + 1){std::vector<int> b(m + 1);fore(j, 1, m + 1) b[a[i][j]] = j;int now = 0;fore(j, 1, m + 1){ //Trie 插入 排列的逆int val =  b[j];if(!tree[now].son[val]) tree[now].son[val] = ++cnt;now = tree[now].son[val];}}fore(i, 1, n + 1){int now = 0;fore(j, 1, m + 1){ //Trie 查询最长前缀int val = a[i][j];if(!tree[now].son[val]) break;++ans[i];now = tree[now].son[val];}}fore(i, 1, n + 1) std::cout << ans[i] << " \n"[i == n];fore(i, 0, cnt + 1) //清空 Triefore(j, 1, m + 1)tree[i].son[j] = 0;cnt = 0;}return 0;
}