codeforce edu round 142 D. Fixed Prefix Permutations

题目链接：https://codeforces.com/contest/1792/problem/D
题意是给出n个长度为m的排列，定义排列p*q为\(r_j = q_{p_j}\) ，令一个排列的价值p为最大的k使得\(p_1 = 1, p_2 = 2, \dots, p_k = k\)。对于每个i求第i个排列与第j（1<=j<=n）个排列相乘的最大价值。
由于m很小（m<=10)，故可以考虑将一个置换表示为一个十进制数来状态压缩，再记录每个长度为k时的逆置换状态值存入哈希表中，最后从1->m依次查询即可得到最大值。
代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;

map<int,int> f;
int a[50005][12],ca[50005][12],s[50005][12],cs[50005][12];
void solve(){
	f.clear();
	int n,m;cin>>n>>m;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cin>>a[i][j];
			ca[i][a[i][j]]=j;
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			s[i][j]=s[i][j-1]*11+a[i][j];
			cs[i][j]=cs[i][j-1]*11+ca[i][j];
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			f[cs[i][j]]=1;
		}
	}
	for(int i=1;i<=n;i++){
		int ans=0;
		for(int j=1;j<=m;j++){
			if(f[s[i][j]]) ans=j;
		}
		cout<<ans<<" ";
	}
	cout<<endl;
}
signed main(){
	int T;cin>>T;
	while(T--) solve();
}