AtCoder

Luogu

分析

设 $dp_{x,y}$ 表示 $a_x > a_y$ 的概率（假设每个操作发生的概率都为 $\frac{1}{2}$）。

对于每个操作 $(i,j)$，我们会让所有的 $dp_{i,k}$ 和 $dp_{j,k}$ 都变为 $\frac{1}{2}(dp_{i,k}+dp_{j,k})$，会让所有的 $dp_{k,i}$ 和 $dp_{k,j}$ 都变为 $\frac{1}{2}(dp_{k,i}+dp_{k,j})$。

最后统计逆序对的期望，再乘上 $2^Q$ 即为答案。

代码

// ===================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// ===================================
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int mod=1e9+7;
const int inv2=(mod+1)/2;
int qpow(int a,int b) { int c=1;
    for (;b;b>>=1,a=1ll*a*a%mod) if (b&1) c=1ll*c*a%mod;
    return c;
}

const int N=3000+10;

int n,q,a[N],x[N],y[N],dp[N][N];

int main() {
    n=read(),q=read();
    for (int i=1;i<=n;++i) a[i]=read();
    for (int i=1;i<=q;++i) x[i]=read(),y[i]=read();
    for (int i=1;i<=n;++i)
        for (int j=1;j<=n;++j)
            dp[i][j]=a[i]>a[j];
    for (int i=1;i<=q;++i) {
        int u=x[i],v=y[i];
        dp[u][v]=dp[v][u]=1ll*(dp[u][v]+dp[v][u])*inv2%mod;
        for (int j=1;j<=n;++j) {
            if (j==u||j==v) continue;
            dp[u][j]=dp[v][j]=1ll*(dp[u][j]+dp[v][j])*inv2%mod;
            dp[j][u]=dp[j][v]=1ll*(dp[j][u]+dp[j][v])*inv2%mod;
        }
    }
    int ans=0;
    for (int i=1;i<=n;++i)
        for (int j=i+1;j<=n;++j)
            ans=(ans+dp[i][j])%mod;
    printf("%lld\n",1ll*ans*qpow(2,q)%mod);
    return 0;
}