【题解】AT4513 [AGC030D] Inversion Sum

· · 题解

核心思想：期望的线性性质。

这道题和 CF258D Little Elephant and Broken Sorting 的区别在于结果是否需要乘上 2^q 以及答案求取过程中是否要求取模。此题的取模和除法可以用逆元实现。

由费马小定理可知除以二在模 10^9+7 意义下相当于乘上 2^{10^9+7}。预处理结束后，令 f(i,j) 表示 i 比 j 大的概率，则根据期望的线性性质得到：

f(i,x)=f(i,y)=\dfrac{f(i,x)+f(i,y)}{2} f(x,i)=f(y,i)=\dfrac{f(x,i)+f(y,i)}{2}

由于每次等概率求取，因此对于 f(x,y) 也要进行一次计算，因此答案为：

2^q\times\sum\limits_{i=1}^{n}\sum\limits_{j=i+1}^{n}f(i,j)

代码实现如下：

#include<bits/stdc++.h>
#define N 3005
#define mod 1000000007
#define int long long
using namespace std;
int n,q,s,inv;
int a[N],f[N][N];
int ksm(int b,int p){
    int s=1;b%=mod;
    while(p){
        if(p&1)s=s*b%mod;
        b=b*b%mod;p>>=1;
    }return s%mod;
}signed main(){
    scanf("%lld%lld",&n,&q);
    for(int i=1;i<=n;i++)scanf("%lld",&a[i]);
    for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)
        if(a[i]<a[j])f[i][j]=1;
    inv=ksm(2,mod-2);
    for(int i=1;i<=q;i++){
        int x,y;
        scanf("%lld%lld",&x,&y);
        f[x][y]=f[y][x]=(f[x][y]+f[y][x])*inv%mod;
        for(int j=1;j<=n;j++){
            if(j==x||j==y)continue;
            f[x][j]=f[y][j]=(f[x][j]+f[y][j])*inv%mod;
            f[j][x]=f[j][y]=(f[j][x]+f[j][y])*inv%mod;
        }
    }for(int i=1;i<=n;i++)for(int j=1;j<i;j++)
        s=(s+f[i][j])%mod;
    cout<<s*ksm(2,q)%mod<<endl;
    return 0;
}

时间复杂度 O(qn) 可以通过本题。