一、关于康托展开
1.什么是康托展开
求出给定一个由1~n个整数组成的任意排列在1~n的全排列中的位置。
解决这样问题的算法叫康托展开。
例如：
(n=4)，序列a={(1，3，4，2)}，那么a在1~4中的全排列位置为第4个。
2.康托展开实现原理
要知道序列a排在第几位，我们就需要知道序列a之前有多少位。
我们按照上面的栗子计算：
1.比1小的数有0个，有(0 imes(4-1)!=0)种排列。
2.比3小的数有2个，但是1已经被占用了，因此可用只有1个数，共有(1 imes(3-1)!=2)种排列。
3.比4小的数有3个，但是1，3被占用，可用的数字只有1个，共有(1 imes(2-1)!=1)种排列。
4.比2小的数有一个，但是全被占用了，因此可用排列为(0 imes(1-1)!=0)。
到现在为止，我们知道在序列a前面的排列有3个，因此序列a排在第4位。
公式：
[pos=k_1(n-1)!+k_2(n-2)!+...+k_n(n-n)!
]
统计时使用树状数组优化，总复杂度为(O(NlogN))。
二、具体实施
1.模板
#include<bits/stdc++.h>
#define ll long long
#define N 1000010
#define MOD 998244353
using namespace std;
int n,t[N];
ll fac[N],ans;
inline void calc_factorial(int n){
fac[1]=1;
for(int i=2;i<=n;i++)
fac[i]=i*fac[i-1]%MOD;
}
inline int lowbit(int x){
return x&(-x);
}
inline void modify(int x,int k){
while(x<=n){
t[x]+=k;
x+=lowbit(x);
}
}
inline ll query(int x){
ll res=0;
while(x>0){
res+=t[x];
x-=lowbit(x);
}
return res;
}
int main()
{
scanf("%d",&n);
calc_factorial(n);
for(int i=1;i<=n;i++) modify(i,1);
for(int i=1,num;i<=n;i++){
scanf("%d",&num);
ans=(ans+((query(num)-1)*fac[n-i])%MOD)%MOD;
//core code: restnum*(n-i)!
modify(num,-1);
}
printf("%lld",ans+1);
return 0;
}
