ABC168 - E - ∙ (Bullet) - Senの競技プログラミング備忘録

atcoder.jp

概要

おかずがN種類ある。それぞれのおかずには糖分A[i]、塩分B[i]というパラメータがある。
あなたはおかずを何種類か選んで晩御飯と一緒に食べたい。この時、次の条件を満たすようにする必要がある。

選ばれたおかずが2つ以上存在するのなら、任意の2つの選んで、それの糖分、塩分をA[i], B[i]とA[j], B[j]とすると、A[i]*A[j] + B[i] * B[j] = 0を満たさない。(このとき、選ばれた2つは任意である。つまりどの2つもこの条件を満たしてはならない)
おかずは最低一品を選ぶ。

さて、何通りの選び方があるのだろうか？ $10^9+7$ で割ったあまりを答えて下さい。

制約：　1 <= N <= 2 * 10^5, -10^18 <= A[i], B[i] <= 10^18

ACするまで

省略

考察

まず、条件式の $A_i A_j=-B_i B_j$ をインデックスi, jごとにまとめる。
つまり、 $\frac{A_i}{B_i}=-\frac{B_j}{A_i}$ である。
しかし、(i <-> jと入れ替えもあることを考えると)、この式変形は $A_i \neq 0, A_j \neq 0, B_i \neq 0, B_j \neq 0$ でなければならない。以下では、まずこれを満たすものたちで考える。

A[i]もB[i]も0ではない

まず、すべてのiについて、 $\frac{A_i}{B_i}$ を計算して、std::mapで保持しておく。(保持の方法としては、僕は(int, ll, ll)のstd::tupleでやり、(符号, 分子, 分母)で持った。符号は+1が正、-1が負とする)

$\frac{A_i}{B_i}$ について、 $-\frac{A_j}{A_i}$ になるものが存在するのならば、その2つは一緒に置けない。
そして、 $-\frac{A_j}{A_i}$ についても、 $\frac{A_i}{B_i}$ が存在するのならば、一緒にはおけない。

つまり、 $\frac{A_i}{B_i}$ を採用したら、 $-\frac{A_j}{A_i}$ は禁止でで、逆もしかり。(これは排他的である)これは二部グラフのような構造(2つのうちの一方だけ)になっている。このことから、それぞれのペアを持つグループ内での場合の数はそれぞれ独立であるともわかる。よって、ひとまずグループ内での場合の数を算出して、最後に掛け合わせばよい。

$\frac{x}{y}$ がp個、 $-\frac{y}{x}$ がq個あるとする。この時、何通りあるのだろうか？(グループから何も選ばないというのも1通りとする)
まず、 $\frac{x}{y}$ だけを含む場合を考える。この時、p個のものについてそれぞれが選ぶor選ばないの2択なので、 $2^p$ 通り存在する。
次に、 $-\frac{y}{x}$ だけを含む場合を考える。同じように考えて、 $2^q$ 通り存在する。
よってこたえは $2^p+2^q$ ・・・というわけではない。このままだと、「何も選ばない」という事象をダブルカウントしているため、1引く必要がある。(p個のところでの何も選ばないとq個のところでの何も選ばないでダブルカウント)