天下一プログラマーコンテスト2015本戦 E - 天下一コップ
解法
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; }