题目链接
题目描述
给定一个长度为n的排列，要求输出该排列的字典序名次（1,2,3,...,n的名次为1）。
输入输出格式
输入格式：
第一行一个数n，表示排列长度。
第二行n个数，用空格分隔，表示一个长度为n的排列。
输出格式：
一个数，表示该排列的字典序名次。由于答案可能很大，请输出答案对1e9+7取模后的结果。
输入输出样例
9
9 8 7 6 5 4 3 1 2
362879
说明
对于30%的数据，n<=10。
对于100%的数据，n<=100000。
题解：
30分做法：纯暴力。枚举名次从1至n!的排列，并与给定排列相比较。复杂度O(n!)。
100分做法：类康托展开。
下面进入精彩的猜结论推理时间：
以排列5 9 7 6 8 1 4 3 2为例，第一个数字是5，在5之前还有1,2,3,4，一共4个数字没有用过，脑中模拟暴力过程推理可知以5开头的第一个排列的序号应为1+4*8!。第二个数字是9，在9之前还有1,2,3,4,6,7,8，一共7个数字没有用过，同理可知以59开头的第一个排列的序号为1+4*8!+7*7!。如此递推下去即可得到给定排列的序号。
所以本题需要预处理出1至n的阶乘，还需要得知排列中第i个数之后有多少个数比自己小。这个可以用树状数组维护前缀和得到：初始时每个元素都是1，处理至排列ai 时查询sum(a[i]-1)，然后add(a[i],-1)即可。
预处理O(n)，依次处理每个元素为O(n)，每次处理时sum和add操作为O(logn)，总复杂度O(nlogn)。
代码：
#include<bits/stdc++.h>
#define LL long long
#define lowbit(x) x&(-x)
using namespace std;
const int maxn=1e5+10,MOD=1e9+7;
int a[maxn],c[maxn];
LL fac[maxn],ans=1;
int n;
void add(int x,int d)
{
int i;
for(i=x;i<=n;i+=lowbit(i)){c[i]+=d;}
}
int sum(int x)
{
int i,ans=0;
for(i=x;i>=1;i-=lowbit(i)){ans+=c[i];}
return ans;
}
int main()
{
int i,j;LL tmp;
//freopen("data9.in","r",stdin);
//freopen("data9.out","w",stdout);
cin>>n;fac[0]=1;
for(i=1;i<=n;i++){fac[i]=i*fac[i-1]%MOD;add(i,1);}
for(i=1;i<=n;i++){scanf("%d",&a[i]);}
//for(i=0;i<=n;i++){cout<<sum(i)<<" ";}cout<<endl;
for(i=1;i<=n;i++)
{
tmp=sum(a[i]-1)*fac[n-i]%MOD;
//printf("i=%d sum(a[i]-1)=%d fac[n-i]=%d tmp=%d ans=%d
",i,sum(a[i]-1),fac[n-i],tmp,ans);
ans=(ans+tmp)%MOD;
add(a[i],-1);
}
cout<<ans<<endl;
return 0;
}