Submission #3895817


Source Code Expand

Copy
// {{{ by shik
#include <bits/stdc++.h>
#pragma GCC diagnostic ignored "-Wunused-result"
#pragma GCC diagnostic ignored "-Wunused-function"
#define SZ(x) ((int)(x).size())
#define ALL(x) begin(x), end(x)
#define REP(i, n) for (int i = 0; i < int(n); i++)
#define REP1(i, a, b) for (int i = (a); i <= int(b); i++)
#define MP make_pair
#define PB push_back
using namespace std;
typedef int64_t LL;
typedef pair<int, int> PII;
typedef vector<int> VI;

namespace { namespace shik {

template<class T> void _R(T &x) { cin >> x; }
void _R(int &x) { scanf("%d", &x); }
void _R(int64_t &x) { scanf("%" SCNd64, &x); }
void _R(double &x) { scanf("%lf", &x); }
void _R(char &x) { scanf(" %c", &x); }
void _R(char *x) { scanf("%s", x); }
void R() {}
template<class T, class... U> void R(T &head, U &... tail) { _R(head); R(tail...); }

template<class T> void _W(const T &x) { cout << x; }
void _W(const int &x) { printf("%d", x); }
void _W(const int64_t &x) { printf("%" PRId64, x); }
void _W(const double &x) { printf("%.16f", x); }
void _W(const char &x) { putchar(x); }
void _W(const char *x) { printf("%s", x); }
template<class T> void _W(const vector<T> &x) { for (auto i = x.begin(); i != x.end(); _W(*i++)) if (i != x.cbegin()) putchar(' '); }
void W() {}
template<class T, class... U> void W(const T &head, const U &... tail) { _W(head); putchar(sizeof...(tail) ? ' ' : '\n'); W(tail...); }

#ifdef SHIK
#include "dump.hpp"
#else
#define dump(...)
#endif

template<class T, class F = less<T>> void sort_uniq(vector<T> &v, F f = F()) { sort(begin(v), end(v), f); v.resize(unique(begin(v), end(v)) - begin(v)); }
template<class T> inline T bit(T x, int i) { return (x >> i) & 1; }
template<class T> inline bool chkmax(T &a, const T &b) { return b > a ? a = b, true : false; }
template<class T> inline bool chkmin(T &a, const T &b) { return b < a ? a = b, true : false; }
template<class T> using MaxHeap = priority_queue<T>;
template<class T> using MinHeap = priority_queue<T, vector<T>, greater<T>>;

// }}}

// {{{ ModInt
template<int _MOD>
struct ModInt {
    static const auto MOD = _MOD;
    template<class T> using integral_only = typename enable_if<is_integral<T>::value>::type;

    int x;
    constexpr ModInt() : x() {}
    template<class T, integral_only<T>* = nullptr>
    ModInt(T _x) {
        x = _x % MOD;
        if (x < 0) x += MOD;
    }
    ModInt operator-() const { return {x == 0 ? 0 : MOD-x}; }
    ModInt& operator+=(ModInt rhs) {
        x += rhs.x;
        if (x >= MOD) x -= MOD;
        return *this;
    }
    ModInt& operator-=(ModInt rhs) {
        x -= rhs.x;
        if (x < 0) x += MOD;
        return *this;
    }
    ModInt& operator*=(ModInt rhs) {
        x = (long long)x * rhs.x % MOD;
        return *this;
    }
    ModInt& operator/=(ModInt rhs) {
        return *this *= rhs.inv();
    }
    ModInt operator+(ModInt rhs) const { return ModInt(*this) += rhs; }
    ModInt operator-(ModInt rhs) const { return ModInt(*this) -= rhs; }
    ModInt operator*(ModInt rhs) const { return ModInt(*this) *= rhs; }
    ModInt operator/(ModInt rhs) const { return ModInt(*this) /= rhs; }
    ModInt inv() const {
        // should work for non-prime MOD if gcd(x, MOD) = 1
        int a = x, b = MOD, u = 1, v = 0;
        while (b != 0) {
            int t = a / b;
            a -= t * b;
            u -= t * v;
            swap(a, b);
            swap(u, v);
        }
        return u;
    }
    template<class T, integral_only<T>* = nullptr>
    ModInt pow(T e) {
        ModInt r = 1, p = *this;
        while (e) {
            if (e & 1) r *= p;
            p *= p;
            e >>= 1;
        }
        return r;
    }
    bool operator==(ModInt rhs) const { return x == rhs.x; }
    bool operator!=(ModInt rhs) const { return x != rhs.x; }
    bool operator<(ModInt rhs) const { return x < rhs.x; }
    bool operator<=(ModInt rhs) const { return x <= rhs.x; }
    bool operator>(ModInt rhs) const { return x > rhs.x; }
    bool operator>=(ModInt rhs) const { return x >= rhs.x; }
    friend string to_string(ModInt i) { return to_string(i.x); }
    friend ostream& operator<<(ostream &os, ModInt i) { return os << i.x; }
};
// }}}

using mint=ModInt<1000000007>;

const int N=3010;
const mint inv2=mint(2).inv();
int n;
mint dp[N][N];
void go( int x, int y ) {
    auto to=[&]( int i ) {
        if ( i==x ) return y;
        if ( i==y ) return x;
        return i;
    };
    vector<tuple<int,int,mint>> v;
    auto push=[&]( int r, int c ) {
        if ( r<c ) v.PB(make_tuple(r,c,dp[r][c]));
    };
    REP1(i,1,n) {
        push(i,x);
        push(i,y);
        push(x,i);
        push(y,i);
    }
    sort_uniq(v);
    for ( auto i:v ) {
        int r=get<0>(i),c=get<1>(i);
        mint t=get<2>(i);
        dp[r][c]-=t*inv2;
        int nr=to(r),nc=to(c);
        mint nt=t;
        if ( nr>nc ) {
            swap(nr,nc);
            nt=mint(1)-nt;
        }
        dp[nr][nc]+=nt*inv2;
    }
}

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

mint run() {
    REP(i,q) go(x[i],y[i]);
    mint ans=0;
    REP1(i,1,n) REP1(j,i+1,n) ans+=dp[i][j];
    ans*=mint(2).pow(q);
    return ans;
}

void main() {
    R(n,q);
    REP1(i,1,n) R(a[i]);
    REP(i,q) R(x[i],y[i]);
    mint ans=0;
    REP1(i,1,n) REP1(j,i+1,n) dp[i][j]=(a[i]>a[j]);
    ans+=run();
    memset(dp,0,sizeof(dp));
    REP1(i,1,n) REP1(j,i+1,n) dp[i][j]=(a[i]>=a[j]);
    ans+=run();
    mint cnt=0;
    REP1(i,1,n) REP1(j,i+1,n) cnt+=(a[i]==a[j]);
    cnt*=mint(2).pow(q);
    ans-=cnt;
    ans*=inv2;
    W(ans);
}

// {{{ main
}}
int main() { shik::main(); return 0; }
// }}}

Submission Info

Submission Time
Task D - Inversion Sum
User shik
Language C++14 (GCC 5.4.1)
Score 1000
Code Size 5754 Byte
Status
Exec Time 2206 ms
Memory 35896 KB

Judge Result

Set Name Score / Max Score Test Cases
Sample 0 / 0 s1.txt, s2.txt, s3.txt
All 1000 / 1000 01.txt, 02.txt, 03.txt, 04.txt, 05.txt, 06.txt, 07.txt, 08.txt, 09.txt, 10.txt, 11.txt, 12.txt, 13.txt, 14.txt, 15.txt, 16.txt, 17.txt, 18.txt, 19.txt, 20.txt, 21.txt, 22.txt, 23.txt, 24.txt, 25.txt, 26.txt, 27.txt, 28.txt, 29.txt, 30.txt, 31.txt, 32.txt, 33.txt, 34.txt, 35.txt, 36.txt, s1.txt, s2.txt, s3.txt
Case Name Status Exec Time Memory
01.txt 2148 ms 35896 KB
02.txt 2065 ms 35892 KB
03.txt 2190 ms 35896 KB
04.txt 2148 ms 35892 KB
05.txt 2152 ms 35892 KB
06.txt 2047 ms 35892 KB
07.txt 2169 ms 35892 KB
08.txt 2078 ms 35896 KB
09.txt 2179 ms 35896 KB
10.txt 2114 ms 35892 KB
11.txt 2206 ms 35896 KB
12.txt 2104 ms 35892 KB
13.txt 1903 ms 35892 KB
14.txt 1759 ms 35896 KB
15.txt 1870 ms 35892 KB
16.txt 2095 ms 35892 KB
17.txt 1842 ms 35896 KB
18.txt 2058 ms 35896 KB
19.txt 1865 ms 35892 KB
20.txt 2105 ms 35892 KB
21.txt 2111 ms 35896 KB
22.txt 2140 ms 35896 KB
23.txt 1851 ms 35892 KB
24.txt 2063 ms 35896 KB
25.txt 2120 ms 35892 KB
26.txt 2137 ms 35892 KB
27.txt 2082 ms 35896 KB
28.txt 2031 ms 35892 KB
29.txt 2125 ms 35892 KB
30.txt 2077 ms 35892 KB
31.txt 2072 ms 35896 KB
32.txt 1728 ms 35892 KB
33.txt 2041 ms 35892 KB
34.txt 1984 ms 35896 KB
35.txt 10 ms 35584 KB
36.txt 10 ms 35584 KB
s1.txt 10 ms 35712 KB
s2.txt 10 ms 35712 KB
s3.txt 10 ms 35712 KB