首先从$1$到$n$枚举，计算满足前$i-1$个位置与$p$相同且第$i$个位置比$p_i$小的排列中的逆序对个数，再加上$p$序列本身的个数，这样做事实上是覆盖了所有情况的，且不重复。
先求出$d_i$，表示$p$中后$n-i$个数比$p_i$小的个数。
对于每个$i$，分类讨论如下：
1.前$i-1$个数内部逆序对、前$i-1$个数与后$n-i+1$个数生成的逆序对。对于每个数，都有$d$个数在它之后并比它小，还需乘上第$i$个数方案数和后$n-i$个数排列方案数，答案为$d_i \times (n-i)! \times \sum_{j=1}^{i-1} d_j$
2.第$i$个数和后$n-i$个数的逆序对个数。第$i$个数可以放$d_i$种数，我们将这$d_i$个数两两组合，并取最大值在前的一种，再乘上后$n-i$个数的排列情况，答案即为$(n-i)! \times (d_i \times (d_i-1))/2$
3.后$n-i$个数内部逆序对数。首先第$i$个数有$d_i$种方案，后面$n-i$个数中，我们选出两个位置，再选出两个数，按大小排列后放入并固定，再乘上其他数排列的方案数，这样可以做到不重不漏统计，答案即为$d_i \times {n-i \choose 2}^2 \times (n-i-2)!$
4.考虑$p$序列本身，答案为$\sum_{1}^{n}d_i$
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
|
#include<bits/stdc++.h>
using namespace std;
#define LL long long
const LL MAXN=2e6+5;
const LL MOD=1e9+7;
LL n,p[MAXN];
struct BIT{
LL nod[MAXN];
void init(){
memset(nod,0,sizeof(nod));
}
LL lowbit(LL x){
return x&(-x);
}
void update(LL x,LL val){
if(x<=0)return ;
while(x<=2e6){
nod[x]+=val;
x+=lowbit(x);
}
}
LL query(LL x){
if(x<=0)return 0;
LL res=0;
while(x){
res+=nod[x];
x-=lowbit(x);
}
return res;
}
}tree;
LL d[MAXN],fac[MAXN],g[MAXN];
LL ksm(LL x,LL y){
LL res=1;
while(y){
if(y&1){
res=res*x%MOD;
}
x=x*x%MOD;
y>>=1;
}
return res;
}
int main(){
scanf("%lld",&n);
for(LL i=1;i<=n;i++){
scanf("%lld",&p[i]);
}
fac[0]=1;
for(LL i=1;i<=2000000;i++){
fac[i]=fac[i-1]*i%MOD;
}
LL ans=0,sum=0;
for(LL i=1;i<=n;i++){
g[i]=tree.query(p[i]);
d[i]=p[i]-g[i]-1ll;
LL x=n-i;
ans=(ans+1ll*((x-1ll)%MOD*x%MOD*ksm(2,MOD-2)%MOD)%MOD*((x-1ll)*x%MOD*ksm(2,MOD-2)%MOD)%MOD*fac[x-2]%MOD*d[i]%MOD)%MOD;
ans=(ans+1ll*fac[x]%MOD*((d[i]*(d[i]-1ll)%MOD*ksm(2,MOD-2)%MOD)%MOD)%MOD)%MOD;
ans=(ans+1ll*d[i]*fac[x]%MOD*sum%MOD)%MOD;
sum=(sum+1ll*d[i])%MOD;
tree.update(p[i],1);
}
ans=(ans+sum)%MOD;
printf("%lld",ans);
}
|