Submission #3957585

---

Source Code Expand

#include <iostream>
#include <vector>
#include <string>
#include <cmath>
#include <algorithm>
#include <utility>
#include <queue>
#include <set>
#include <map>
#include <deque>
#include <iomanip>
#include <cstdio>
#include <stack>

using namespace std;
typedef  long long ll;
typedef pair<int,int> PII;
typedef vector<int> VI;
typedef vector<VI> VVI;
#define  MP make_pair
#define  PB push_back
#define inf  1000000007
#define mod 1000000007
#define rep(i,n) for(ll i=0;i<(ll)(n);++i)


#define MOD 1000000007

long long mod_pow(long long a,long long b)
{
    a %= MOD;
    long long res = 1;
    while(b){
        if(b & 1){
            res = res * a % MOD;
        }
        a = a * a % MOD;
        b >>= 1;
    }
    return res;
}



int main(){
    ll n;
    cin >> n;
    vector<pair<ll,ll> > p;
    vector<ll>h(n),w(n);
    rep(i,n){
        ll a,b;
        cin >> a >> b;
        p.PB(MP(b,a));
    }
    sort(p.begin(),p.end());
    rep(i,n){
        h[i] = p[i].first;
        w[i] = p[i].second;
    }
    ll ans = 0;
    vector<ll> s(n+1);
    vector<ll> ss(n+1);
    
    for(ll i=n-2;i>=0;i--){
        ll k = mod_pow(n+1-i,mod-2);
        k = (k*mod_pow(n-i,mod-2))%mod;
        ss[i] += h[i]*k%mod;
        ss[i] %= mod;
        ss[i] += ss[i+1];
        ss[i] %= mod;
    }
    for(ll i=n-2;i>=0;i--){
        ll k = mod_pow(n+1-i,mod-2);
        k = (k*mod_pow(n-i,mod-2))%mod;
        s[i] += k%mod;
        s[i] %= mod;
        s[i] +=s[i+1];
        s[i] %= mod;
    }
    
    rep(i,n){
        ans += (2*w[i]*ss[i+1])%mod;
        ans %= mod;
        ans += (mod -(2*(h[i]*w[i]%mod)*s[i+1])%mod);
        ans %= mod;
    }
    ll tmp = 1;
    rep(i,n){
        tmp *=(i+1);
        tmp %= mod;
    }
    
    cout << (ans*tmp)%mod << endl;
    
    // ll test = 0;
    // rep(i,n){
    //     for(ll j=i+1;j<n;j++){
    //         test += 2*((h[j]-h[i])*w[i]*tmp)/((n+1-j)*(n-j));
    //         cerr << i << " " << j << " " << test << endl;
    //     }
    // }
    // cerr << test << endl;
    return 0;
}

Submission Info

Judge Result