CF396D

· · 题解

题意:是给你一个n的排列,然后要你求字典序小于等于它的里面的逆序数.

先处理小于的情况,显然可以枚举前i-1个与之相同,第i个小于p_i,其他位子任意排.

那么逆序对的方案数就分四块了.

令f_i表示i个数的逆序对数量.显然先取两个数{C(n,2)},再选择两个位子C(n,2),然后其他n-2个数字随意排列,(n-2)!.

令i可选择的数的个数为num

1.$前$i-1$个自己的贡献,这个显然就是前${i-1}$个自己对自己逆序对的数量$*t*$$(n-(i))!. 2.$前${i-1}$个对后$n-i+1$的贡献,这个显然是前${i-1}$个自己对后面逆序对的数量$*t*$$(n-(i))!. $3.$第$i$个自己对后面的贡献.第${i}$个可选择的数量是${num}$,选择${num}$将产生${num-1}$的贡献,那么方案即是$num*(num-1)/2*(n-(i))!. 4.$后$n-i$个自身的贡献,这个显然$num*f_{n-i}.

最后不要忘记是不超过,可以等于,记得计算下原序列的逆序对数量.

code:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e6+5;
const int mod=1e9+7;
int p[N],n;
ll c[N],f[N];

int lowbit(int u)
{
    return u&(-u);
}

void add(int u,int val)
{
    while(u<=n)
    {
        c[u]+=val;
        u+=lowbit(u);
    }
}

int query(int u)
{
    int res=0;
    while(u)
    {
        res+=c[u];
        u-=lowbit(u);
    }
    return res;
}

ll cnt(ll num)
{
    return (num*(num-1)/2%mod)*(num*(num-1)/2%mod)%mod*f[num-2]%mod;
}

void run()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)   scanf("%d",&p[i]);
    f[0]=1;
    for(int i=1;i<=n;i++)
        f[i]=f[i-1]*i%mod;
    ll ans=0,sum=0;
    for(int i=1;i<=n;i++)
    {
        ll num=p[i]-1-query(p[i]);
        ans+=num;ans%=mod;
        ans+=num*cnt(n-i)%mod;ans%=mod;
        ans+=(num*(num-1)/2%mod)*f[n-i]%mod;ans%=mod;
        ans+=sum*num%mod*f[n-i]%mod;
        add(p[i],1);
        sum+=num;
    }
    printf("%lld\n",ans);
}

int main()
{
    int T=1;
    while(T--)  run();
    return 0;
}