天下一プログラマーコンテスト2015本戦 E - 天下一コップ

問題

tenka1-2015-final-open.contest.atcoder.jp

解法

kmjp さんの解説を参考にしました。kmjp.hatenablog.jp

得た知見

• 「全部やる」みたいな問題で実際に全部やるのは無理なので, 問題を小分けにする
  • 今回の場合は「全部やる」 = 「すべての順列を試す」, 小分け = 「2 つの長方形に注目してその関係を調べる」
  • SRM の med とかはこういうタイプも結構ある気がする
• 計算量を落とす際に f(x, y) = g(x) * g(y) というような形になっていればやりやすい

struct rect {
    ll w, h;
    rect(ll w, ll h) : w(w), h(h) {}
    rect() {}
    bool operator<(const rect& rhs) {return h < rhs.h;}
};

const int MAXN = 100007;
const ll MOD = 1e9+7;
rect r[MAXN];
ll fact[MAXN], rfact[MAXN], inv[MAXN];

// extgcd
ll extgcd(ll a, ll b, ll& x, ll& y) {
    ll d = a;
    if (b != 0) {
        d = extgcd(b, a % b, y, x);
        y -= (a / b) * x;
    } else {
        x = 1; y = 0;
    }
    return d;
}

// mod_inverse
ll mod_inverse(ll a, ll m) {
    ll x, y;
    extgcd(a, m, x, y);
    return (m+x%m) % m;
}

ll nCr(int n, int r) {
    ll ret = fact[n];
    (ret *= rfact[r]) %= MOD;
    (ret *= rfact[n-r]) %= MOD;
    return ret;
}

ll sum[MAXN];
ll hsum[MAXN];

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N;
    cin >> N;
    fact[0] = rfact[0] = 1;
    for (int i = 1; i < MAXN; i++) {
        inv[i] = mod_inverse(i, MOD);
        fact[i] = (fact[i-1]*i)%MOD;
        rfact[i] = mod_inverse(fact[i], MOD);
    }
    for (int i = 0; i < N; i++) {
        cin >> r[i].w >> r[i].h;
    }
    sort(r, r+N);
    reverse(r, r+N);
    for (int i = 2; i <= N; i++) {
        ll tmp = (inv[i]*inv[i+1]) % MOD;
        sum[i] = (sum[i-1] + tmp) % MOD;
        hsum[i] = (hsum[i-1] + r[i-1].h * tmp) % MOD;
    }
    ll ans = 0;
    for (int i = 3; i <= N; i++) {
        ll tmp = 2*fact[i];
        (tmp *= nCr(N, i)) %= MOD;
        (tmp *= fact[N-i]) %= MOD;
        (tmp *= r[i-1].w) %= MOD;
        ll mul = hsum[i-1];
        mul -= (r[i-1].h * sum[i-1]) % MOD;
        mul %= MOD;
        if (mul < 0) mul += MOD;
        (tmp *= mul) %= MOD;
        ans += tmp;
    }
    ans %= MOD;
    cout << ans << endl;
    return 0;
}