双倍经验：CF258D. Little Elephant and Broken Sorting
好巧妙，想不到。
因为 \(n\) 并不大，且直接统计显然很困难，考虑数对 \((i,j),i<j\) 会在什么条件下形成逆序对，即 \(a_i>a_j\)。
更具体的，我们可以把是否选择执行操作看作等概率的选项，定义 \(f_{k,i,j}\) 表示考虑前 \(k\) 个操作，使得 \(a_i>a_j\) 的期望。那么由于期望的线性性，满足 \(i<j\) 的 \(f_{m,i,j}\) 之和乘 \(2^m\) 就是答案。
转移是简单的，容易发现每次操作只会改变至多 \(2n\) 个位置的值，且第一维完全没有必要记录，可以 \(\mathcal{O}(n^2)\)。
点击查看代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int inf=1e18,mod=1e9+7,i2=(mod+1)/2;
inline int read(){
int x=0,f=1;char ch=getchar();
while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}
while (isdigit(ch)){x=x*10+ch-48;ch=getchar();}
return x*f;
}
int qpow(int b,int p){
int res=1;
for(;p;p>>=1,b=b*b%mod)if(p&1ll)res=res*b%mod;
return res;
}
int a[3005],f[3005][3005];
signed main(){
int n=read(),q=read();
for(int i=1;i<=n;i++)a[i]=read();
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
f[i][j]=(a[i]>a[j]);
}
}
for(int j=1;j<=q;j++){
int x=read(),y=read();
f[x][y]=f[y][x]=(f[x][y]+f[y][x])*i2%mod;
for(int i=1;i<=n;i++){
if(i==x||i==y)continue;
f[i][x]=f[i][y]=(f[i][x]+f[i][y])*i2%mod;
f[x][i]=f[y][i]=(f[x][i]+f[y][i])*i2%mod;
}
}
int ans=0;
for(int i=1;i<=n;i++){
for(int j=i+1;j<=n;j++){
ans=(ans+f[i][j])%mod;
}
}
printf("%lld\n",ans*qpow(2ll,q)%mod);
return 0;
}