Problem Statement
You are given an integer sequence of length $N$: $A_1,A_2,...,A_N$. Let us perform $Q$ operations in order. The $i$-th operation is described by two integers $X_i$ and $Y_i$. In this operation, we will choose one of the following two actions and perform it:
- Swap the values of $A_{X_i}$ and $A_{Y_i}$
- Do nothing
There are $2^Q$ ways to perform these operations. Find the sum of the inversion numbers of the final sequences for all of these ways to perform operations, modulo $10^9+7$.
Here, the inversion number of a sequence $P_1,P_2,...,P_M$ is the number of pairs of integers $(i,j)$ such that $1\leq i < j\leq M$ and $P_i > P_j$.
Constraints
- $1 \leq N \leq 3000$
- $0 \leq Q \leq 3000$
- $0 \leq A_i \leq 10^9(1\leq i\leq N)$
- $1 \leq X_i,Y_i \leq N(1\leq i\leq Q)$
- $X_i\neq Y_i(1\leq i\leq Q)$
- All values in input are integers.
先定义 \(dp_{i,j}\) 为 \(a_i<a_j\) 的方案数。
然后发现一次交换会改变所有的 \(dp_{i,j}\)。但是大多的 \(dp_{i,j}\) 都是乘上2，除了 \(x_i\) 和 \(y_i\) 相关的 dp 以外。
所以把 \(dp_{i,j}\) 的定义改为 \(a_i>a_j\) 的概率，然后每次只有 \(O(n)\) 个 dp 值会修改。
#include<bits/stdc++.h>
using namespace std;
const int N=3005,P=1e9+7,iv2=P+1>>1;
int n,q,pw[N],dp[N][N],a[N],x,y,ans,g1[N],g2[N];
int main()
{
scanf("%d%d",&n,&q);
for(int i=1;i<=n;i++)
scanf("%d",a+i);
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
dp[i][j]=a[i]>a[j];
for(int i=pw[0]=1;i<=q;i++)
{
pw[i]=pw[i-1]<<1;
if(pw[i]>=P)
pw[i]-=P;
}
for(int i=1;i<=q;i++)
{
scanf("%d%d",&x,&y);
for(int i=1;i<=n;i++)
g1[i]=dp[i][x]&1? dp[i][x]+P>>1:dp[i][x]>>1,g2[i]=dp[x][i]&1? dp[x][i]+P>>1:dp[x][i]>>1;
for(int i=1;i<=n;i++)
{
if(i^x&&i^y)
{
dp[i][x]=(dp[i][x]&1? dp[i][x]+P>>1:dp[i][x]>>1)+(dp[i][y]&1? dp[i][y]+P>>1:dp[i][y]>>1);
if(dp[i][x]>=P)
dp[i][x]-=P;
}
}
for(int i=1;i<=n;i++)
{
if(i^x&&i^y)
{
dp[x][i]=(dp[x][i]&1? dp[x][i]+P>>1:dp[x][i]>>1)+(dp[y][i]&1? dp[y][i]+P>>1:dp[y][i]>>1);
if(dp[x][i]>=P)
dp[x][i]-=P;
}
}
for(int i=1;i<=n;i++)
{
if(i^y&&i^x)
{
dp[i][y]=(dp[i][y]&1? dp[i][y]+P>>1:dp[i][y]>>1)+g1[i];
if(dp[i][y]>=P)
dp[i][y]-=P;
}
}
for(int i=1;i<=n;i++)
{
if(i^y&&i^x)
{
dp[y][i]=(dp[y][i]&1? dp[y][i]+P>>1:dp[y][i]>>1)+g2[i];
if(dp[y][i]>=P)
dp[y][i]-=P;
}
}
dp[x][y]=dp[y][x]=(dp[x][y]+dp[y][x])*1LL*iv2%P;
}
for(int j=1;j<n;j++)
{
for(int k=j+1;k<=n;k++)
{
ans+=dp[j][k];
if(ans>=P)
ans-=P;
}
}
printf("%lld",ans*1LL*pw[q]%P);
}