题目链接
https://www.luogu.org/problem/P5367
什么是康托展开
百度百科上是这样说的：
是不是讲得很精（meng）致（bi）呢？
我看了无数篇博客，终于明白了一点点。
其实，康托展开就是求一个全排列在所有全排列中字典序排名第几。
举个例子：
比如说n=3的一个全排列：2 1 3 它的排名是3。
我们列出所有的全排列：
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1
显然，2 1 3在里面字典序排名第三。
暴力求法（基本思路）
首先我们用a[i]表示原数的第i位在当前未出现的元素中是排在第几个
比如说 "2 3 4 1"
a[1]=2 a[2]=2 a[3]=2 a[4]=0
拿a[2]举例子，到第二位时，未出现的数字有1，3，4，显然3排在第二位上，所以a[2]=2。
然后我们想，在前k-1位相等的情况下，a[k]具有什么意义？比当前情况字典序小的全排列数有多少呢？
显然是 a[k]*(k-1)! （注意阶乘的优先级比乘法运算高） 哪里显然了QAQ？
好像这叫做乘法原理来着（蒟蒻记不清楚了）
a[k]是第k位的比原排列小的数字数量，而第k-1~n位无论是什么数一定小于原数列，而且每一位都要用掉一个数字，所以就是a[k]*(k-1)*(k-2)*(k-3)*……*2*1。
最后把这些小于原排列的排列数量加起来，最后在+1就是原数列的排名。
放公式：ans=a1*0+a2*(2-1)!+a3*(3-1)!+……+an*(n-1)!+1。
时间复杂度为O(n^2)
优化
- 先预处理1到n的阶乘
- 用树状数组来维护有多少个未出现的比自己小的数（单点修改，区间查询）——一开始所有点都修改为1，然后每遇到一个点，就修改为0，最后查询1~s[k-1]有多少个1就行了(s为原数列)。
当然了，也可以用万能的线段树（只不过常数比较大罢了）
AC代码
#include<iostream>
#include<cstdio>
using namespace std;
const int mod=;
const int maxn=;
int ss[maxn],a[maxn],s[maxn],n;
inline int lowbit(int x){
return x&(-x);
}
void update(int id,int x){
for(int i=id;i<=n;i+=lowbit(i)){
s[i]+=x;
}
}
int query(int id){
int res=;
for(int i=id;i>;i-=lowbit(i)){
res+=s[i];
}
return res;
}
long long ans,jc[maxn];
int main()
{
cin>>n;
jc[]=;
for(int i=;i<n;i++) jc[i]=jc[i-]*i%mod;
for(int i=;i<=n;i++) scanf("%d",&ss[i]);
for(int i=;i<=n;i++) update(ss[i],);
for(int i=;i<=n;i++){
update(ss[i],-);
a[n-i+]=query(ss[i]);
}
for(int i=;i<=n;i++) ans=(ans+(long long)a[i]*jc[i-]%mod)%mod;
cout<<ans+;
return ;
}