康托展开，求全排列的排名

来自校内赛的一道题的题解

题目：输入一个n和两个n的全排列，求两个全排列的排名差的绝对值，排名为字典序排名

思路：依据康托展开，思路就是从第一个数组开始遍历，找到这个数字在没有出现过的数字里的排名，之后ans+=(排名数-1)*（n-i）!,其中i为循环次数，从1开始。最后对得到的ans+1.

        我们只需要用一个vis数组记录之前出现过的数字即可正确得到排名

    AC代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxn = 2e5+100;

int vis[10]; int x[100];
int y[100];
void fast ()
{ ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);}

int pail (int a ){        //计算阶乘
	if(a ==0) return 1;
	else {
		int ans =1;
		for(int i=1;i<=a;i++)	
			ans*=i;
		return ans;	
	}
}

signed main ()
{
	fast();
	int n; cin>>n;
	int cnt1 =1,cnt2 =1;
	int ans1=0; int ans2 =0;
	for(int i=1;i<=n;i++){
		cin>>x[i];
		for(int j=1;j<=n;j++){
			if(x[i]>j &&vis[j]==0){  //如果大于这个数字且这个数字没有出现过
				cnt1++; 
			}
		}
		ans1 += (cnt1-1)*pail(n-i);
		vis[x[i]] =1;
		cnt1=1;             //初始化cnt1
	}
	ans1+=1;   //注意+1
	memset(vis,0,sizeof(vis));
	 for (int i=1;i<=n;i++){       //同上一个循环
		cin>>y[i];
	 	for(int j=1;j<=n;j++){
	 		if(y[i]>j &&vis[j]==0){
	 			cnt2++; 
	 		}
	 	}
	 	ans2 += (cnt2-1)*pail(n-i);
	 	vis[y[i]] =1;
	 	cnt2=1;
	 }
	ans2++;   //注意+1
	cout<<abs(ans1-ans2);
	return 0;
}