問題はこちら
問題概要
2次元上の点が
与えらえれる. すべての点集合について, その集合のすべての点を含む最小の長方形の内部にある点の総数を998244353で割った値を求めよ.
思考の流れ
全列挙できない場合は寄与分を考える でいけそう. 一つの点に対してその点を含むような長方形を作る集合の数を求めればよい.
その点を含む集合が作る長方形の内部にその点は必ずある. そのような集合の数は
個ある. その点を含まない集合のうち, その集合が作る長方形の内部にその点があるような集合の数を求めたい. 以下の図のようにその点を中心にして左上, 左下, 右上, 右下の数を数えておくと, 集合の数を簡単に求めることができる. (点の数求め方や, それから集合の数を求める方法はプログラムを参考にしてください)
提出プログラム
https://atcoder.jp/contests/abc136/submissions/12299165
感想
すんなり解けたのでよかった.
