CF 871 C - Points, Lines and Ready-made Titles
問題
問題概要
2次元平面上に点が個ある。番目の点の座標はである。各点に対して、x軸に平行な線を描く、y軸に平行な線を描く、何も描かないのどれかの操作を選ぶことが出来る。 この個の点から描かれた線を平面上に描かれた画像と見なすと、画像は何通りの可能性があるか、で割った余りを答えよ。
- 全ての点は平面上で異なる位置にある。
アイデア
全ての点に対して操作は3通りあるので、全体としては通りあるけど、同じy座標の点がそれぞれ横に線引いたら被るしどうやってその重複する数え上げを排除しよう...とか悩んでいた。
点を基準にするのではなく、出来上がる画像を基準にして考える。線が発生し得るx座標に対して小さい順に、同様にy座標に対してもとして、これらを頂点とし、このxとyを結ぶ辺として各点を考える。
上のグラフを考えると、今回できる操作は各辺に対してその辺をつなぐ2点のどちらかをonに出来るということに対応する。連結成分ごとに考えてみると(連結成分の頂点数をとする)、連結成分が木なら、全部の頂点をonにするということ以外は出来るので、通りが出来る。木ではなく、閉路が1つでもできるなら全ての通りを実現できるので通りが出来る。
実装(C++)
#include <bits/stdc++.h> using namespace std; using ll = long long; #define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i)) #define all(x) (x).begin(),(x).end() #define pb push_back #define fi first #define se second using pi = pair<int,int>; const ll mod = 1e9+7; const int N = 222222; ll pw[N]; vector<int> G[N]; bool vis[N]={}; int cv; set<pi> ce; void dfs(int v) { vis[v] = true; ++cv; for(int e:G[v]) { ce.insert({min(e,v),max(e,v)}); if(!vis[e]) dfs(e); } } int main() { pw[0] = 1; for(int i=1; i<N; ++i) pw[i] = (pw[i-1]*2)%mod; int n; scanf(" %d", &n); vector<int> x(n),y(n),xx,yy; rep(i,n) { scanf(" %d %d", &x[i], &y[i]); xx.pb(x[i]); yy.pb(y[i]); } sort(all(xx)); xx.erase(unique(all(xx)),xx.end()); sort(all(yy)); yy.erase(unique(all(yy)),yy.end()); int a = xx.size(), b = yy.size(); rep(i,n) { int vx = lower_bound(all(xx),x[i])-xx.begin(); int vy = lower_bound(all(yy),y[i])-yy.begin()+a; G[vx].pb(vy); G[vy].pb(vx); } ll ans = 1; rep(i,a+b) { if(vis[i]) continue; cv = 0; ce.clear(); dfs(i); int E = ce.size(); if(E>=cv) (ans*=pw[cv])%=mod; else (ans*=pw[cv]-1)%=mod; } printf("%lld\n", ans); return 0; }