AGC030D Inversion Sum

简单题。难点是容易想歪。

求逆序对数，其实就是求有多少种方案使得对 $i < j$ 满足 $A_i > A_j$ 。

考虑直接设一个矩阵 $G$ ，其中 $G[i][j]$ 表示有多少种使用操作的方案使得 $A_i > A_j$ 。

每次操作 $(x,y)$ 其实就是将 $G[x],G[y]$ 两行以及 $G[.][x],G[.][y]$ 两列加起来放回去，并且将其他位置的值乘二，再特判一下 $G[x][y]$ 和 $G[y][x]$ 的值。

整体乘二可以通过打标记来实现，而加起来两行或者两列一次的复杂度都是 $O(n)$ ，可以接受

这个东西其实有更好的理解方法，可以设 $G[i][j]$ 表示前面随机使用操作时 $A_i > A_j$ 的概率，这样转移就更容易看出来了。但是实际的代码应该和前面的做法一样。

最终只需要取所有 $i < j$ 的 $G[i][j]$ 求和即可。

复杂度 $O(n^2 + nq)$ 。

#include "iostream"
#include "algorithm"
#include "cstring"
#include "cstdio"
#include "cmath"
#include "vector"
#include "map"
#include "set"
#include "queue"
using namespace std;
const int MAXN = 3e3 + 10;
//#define int long long
#define rep(i, a, b) for (int i = (a), i##end = (b); i <= i##end; ++i)
#define per(i, a, b) for (int i = (a), i##end = (b); i >= i##end; --i)
#define pii pair<int,int>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define vi vector<int>
#define all(x) (x).begin() , (x).end()
#define mem( a ) memset( a , 0 , sizeof a )
typedef long long ll;
const int P = 1e9 + 7;
int n;
int q;
int A[MAXN] , S[MAXN][MAXN] , p2[MAXN];

void solve() {
    cin >> n >> q;
    p2[0] = 1;
    rep( i , 1 , q ) p2[i] = ( p2[i - 1] * 2 ) % P;
    rep( i , 1 , n ) scanf("%d",A + i);
    rep( i , 1 , n ) rep( j , 1 , n ) if( A[i] > A[j] ) S[i][j] = 1;
    int ans = 0;
    const int iv2 = ( P + 1 >> 1 );
    rep( w , 1 , q ) {
        int u , v;
        scanf("%d%d",&u,&v);
        rep( i , 1 , n ) if( i != u && i != v ) {
            int ts = ( S[i][u] + S[i][v] ) % P;
            S[i][u] = S[i][v] = ts * 1ll * iv2 % P;
            ts = ( S[u][i] + S[v][i] ) % P;
            S[u][i] = S[v][i] = ts * 1ll * iv2 % P;
        }
        int ts = ( S[u][v] + S[v][u] ) * 1ll * iv2 % P;
        S[u][v] = S[v][u] = ts;
//        ans = ( ans + ts * 1ll * p2[q - w] ) % P;
    }
    rep( i , 1 , n ) rep( j , i + 1 , n ) ans = ( ans + S[i][j] * 1ll * p2[q] ) % P;
    cout << ans << endl;
}

signed main() {
//    freopen("in","r",stdin);
//    int T;cin >> T;while( T-- ) solve();
    solve();
}