ABC 401-500/ABC402D - Line Crossing - 競技プログラミング用 知識集積所

---

問題

ABC402D

必要知識

B以下レベルの内容は省略

• 必要十分条件（未作成）
• 補集合（未作成）
• 順列組み合わせ（未作成）

考え方

考察系問題。

交わるものよりも交わらないものの方が考えやすいので、補集合で考える。
まず、2本の線の組み合わせはm*(m-1)/2で求められる。
そこから平行になっている組の総数を引き算することを目指す。

まず、平行になっているかどうかの判定を考える。
入力例1で「1-8」の直線に平行な線を考えると、「2-7」「3-6」「4-5」がある。
これらは全て2点の和が9である。
また、「1-5」の直線に平行な線を考えると、「2-4」「6-8」」がある。
これらは全て2点の和が6か14である。
つまり、平行であることの必要十分条件は、2点の和のmod nが等しい値であることと考えられる。

そこで、全ての直線で2点の和のmod nを計算し、0からn-1までそれぞれいくつあるかカウントし、同じ余りのものが複数あったらそれら全てでk*(k-1)/2を求めて引いていけばよい。

解答例

解答例

注意点

必要十分条件の判断を慎重に。

厳密な証明まではしないとしても、「平行だが2点の和のmod nが異なるケースはないか？」「2点の和のmod nが等しいのに平行でないケースはないか？」を注意深く確認するくらいはするべき。

long long型を使う。

Combの計算時にint型をはみ出ることになる。

別解