思路
本题用了康托展开。
康托展开表达式：$ans=1+\sum\limits_{i=1}^n A\lbrack i\rbrack\times(n-i)!$
康托展开的主要思想是将所有的情况按顺序编一个号，并用简便的算法快速找出它的顺序。
举个例子：1 4 2 3
还没有出现过的数（从小到大）：1 2 3 4
序列第一位是 1，在还没用过的序列中排第一个所以 $ans=ans+0\times3!$
还没有用过的数（从小到大）：2 3 4
序列第一位是 4，在还没用过的序列中排第三个所以 $ans=ans+2\times2!$
还没有用过的数（从小到大）：2 3
序列第一位是 2，在还没用过的序列中排第一个所以 $ans=ans+0\times1!$
还没有用过的数（从小到大）：3
序列第一位是 2，在还没用过的序列中排第一个所以 $ans=ans+0\times0!$
此时 $ans=4$，根据公式再加一即是结果。
康托展开的查找
根据上面的例子，可能会有疑惑，为什么会出现阶乘？
其实是因为全排列问题，例如还剩 3 个数，有 3 个空共有 $3\times2\times1=6$ 种情况。
这也是前面提过的，为了给每种情况一种编号，而我们是通过从小到大的顺序进行编号的，那么我们可以
通过每一位的判断将这个位数之前的所有情况都算出来，就能知道当前的排名，在最后一位求完时，再加一就是当前排列的排名了。
讲得通俗一点就是，例如在自然数中，你要找到 100 这个数的排名，你可以通过所有可能的排序情况，先求出 99 的排名，最后再加 1 就是 100 的排名了。
所以通过每一位确定的数，求比当前序列已经确定的数组成的序列小的序列排名，最后加一就是当前序列的排名，这就是康托展开的求排序方法。
实现查找当前数位上的数在未用过数的序列中的排名
方法一：通过平衡树找当前数排名，注意及时删点（update）。
方法二：通过树状数组找到当前数的排名（本篇题解的代码就是这个思路）。
细节优化
即时取模。
注意数列中数的下标从 0 开始。
代码
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
using namespace std;
long long tree[1000005];
int n;
int lowbit(int x){//树状数组快速找"儿子"
return x&-x;
}
void update(int x,int y){//更新
while(x<=n){
tree[x]+=y;
x+=lowbit(x);
}
}
long long query(int x){//查询排名
long long sum=0;
while(x){
sum+=tree[x];
x-=lowbit(x);
}
return sum;
}
const long long o_o=1e9+7;//取模
long long k_t[1000005]={1,1};
int a[1000005];
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++){//预处理阶乘
k_t[i]=(k_t[i-1]*i)%o_o;
update(i,1);
}
long long ans=0;
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
ans=(ans+((query(a[i])-1)*k_t[n-i])%o_o)%o_o;//康托展开
update(a[i],-1);//更新排名
}
printf("%lld",ans+1);
return 0;
}
