数弱による ABC168-E "・(Bullet)" 解説
かなり詳しい解説記事は既にあったのですが、
自分は数弱で、ちょっと難しいと思った部分もあったので、詰まった箇所を補足します。
余りの計算や連想配列（map）に pair を入れるやり方に慣れておらず苦しみましたが、楽しんで解けました。
この map の使い方は、結構役に立つ気がします。
今回は、以下のブログ記事を参考（というか解法自体はそのまま同じ）に解きました。
AtCoder ABC #168 : E - ∙ (Bullet) - kmjp's blog
余りの計算は、こちらが参考になりました。
「1000000007 で割ったあまり」の求め方を総特集！ 〜 逆元から離散対数まで 〜 - Qiita
概要
コンテスト中は、この問題はどう整理していいか分かりませんでした。
ここが数弱たる所以ですが、ともかくこの問題は、まず数式的に考えて整理しないといけない問題だったようです。
具体的には、２つのアプローチがありますが、どちらも結論は同じになります。
（一旦、美味しさや香りがゼロになる場合のことは考えずに進めます。）
1. 与えられた数式 Ai*Aj + Bi*Bj = 0 を変形する
2. イワシの性質 (Ai, Bi) を、平面上の座標（ベクトル）と考える
＜1. 式変形＞
与えられた数式を変形すると、Bi/Ai * Bj/Aj = -1 となります。
これだけでも問題は解けるのかもしれませんが、数弱的に、式変形しただけだとなんだか怖い（？）ので、2. に進みます。
＜2. 平面上の座標と考える＞
座標と考えるって何やねんって感じですが、下図のとおりです。
イワシiの(美味しさAi, 香りBi)を、(A, B)を座標軸とする平面上の点だと考えます。
図の中には2尾のイワシ i, j がいることになりますが、実は、問題で与えられた Ai*Aj + Bi*Bj = 0 というのは、この2つのイワシの傾き（原点からイワシに向けて引いた直線）が垂直に交わっているということらしいです。
（ベクトルが直交している時、それらの内積は0、ということらしいです）
また、「傾きが垂直ということは、お互いの傾きを掛け合わせると -1 になる」という数学の知識があります。
傾きというのは、普通のxy平面だと y/x, つまり今回で言うと Bi/Ai のことですから、やはり Bi/Ai * Bj/Aj = -1 という結論が出てきました。
ちなみに、こうして座標で考えてみると、「仲が悪くなるペアは固定されていて、複雑に絡み合っていない」という重要な事実が分かります。
現実の複雑な人間関係のようにはなっていなくて、傾きが垂直になっているペア同士が仲が悪いだけで、それ以外の組み合わせは全員仲が良いということです（0が絡む場合は別ですが）。
自分はこれが分からず、複雑な人間関係の相関図みたいなものをイメージして迷宮入りしました……。
解法の概要
さて、どうやら、Bi/Ai * Bj/Aj = -1 となるようなイワシは仲が悪いので、それをなんとかしてうまい感じに数え上げればいいという気がしてきました。
……しかし、ここでまた詰まりました。
一体何をどうやってどのように数え上げれば、解法にたどり着けるか全く分かりません。
これは、連想配列（C++ でいうと map ）を賢く使うことで解決します。
「各イワシを、水槽に分けていく」ということを考えます。
水槽に分けて数を数えていくことが、バケツソートで使うバケツの考え方に似ていますので、バケツと呼ぶことにします。
今回は、「2つのセクションに区分されたバケツ」を沢山（最大N個ほど）用意します。
このバケツに、各イワシを「お互いに仲の悪いイワシは、同じバケツの別のセクションに」入れていきます。
バケツに入れ終わったら、最後に「同じバケツの違うセクションからは同時にイワシを取らない」ということに気を付けながら、数え上げをすればいいということになります。
（公式の解説PDFだと、ここまで分かればあとは基礎的な数え上げの範疇、と言っているのだと思います）
どんな連想配列を作ればいいか
今回は、普通に連想配列（C++でいうとmap）を使っても解けません。
イワシの傾きごとにバケツ（連想配列の各要素）を作りたいのに、傾きは整数ではなく実数だからです。
実数を連想配列のキーにできればいいですが、誤差があるので多分難しいです。
ということで、今回は連想配列のキーとして、タプル（C++でいうと今回はpair
連想配列[(a, b)] = (セクション1のイワシの数, セクション2のイワシの数)
となるように、keyにもvalueにもintのタプルを持つ連想配列を作って、それをバケツとして使います。
注意点1
ここで注意点があります。
これが今回の重要なポイントで、難しい部分だったと思います。
例えば、(1, 2) のイワシと (-2, 1) のイワシは仲が悪いですが、同様に (2, 4)のイワシや、(3, 6)のイワシ、また、(-1, -2) のイワシも、(-2, 1) のイワシと仲が悪いのです。
つまり、「具体的な値は違うけど、傾きが同じイワシ」は、同じバケツに入れなければいけないということです。
これを解決するためには、最大公約数（gcd）を使います。
(2, 4) や (3, 6) や (-1, -2) のイワシは、結局のところ、「(1の倍数, 2の倍数) のイワシ」と言い換えられます。
ということは、(a, b) の 最大公約数で割って互いに素な状態にし、(負, 負)なら符号をひっくり返して(正, 正)にすれば、統一した表現に変えられます。
また、(-1, 2) と (1, -2) なども同様に、傾きは同じ別のイワシということになっています。
これらも統一しないといけないため、(正, 負) のものは符号をひっくり返して、(負, 正)に統一することにします。
この統一化の作業を、参考として挙げた記事では「正規化」と呼んでいます。
公式の解説PDFだと、「既約分数で表す」に当たる部分です。
注意点2（ゼロが絡む場合）
ゼロが絡む場合は、特殊なバケツに入れて区別します。
＜(0, 0)のイワシ＞
まず、美味しさも香りも 0 のイワシは、どんなイワシと組み合わせても 数式の答えが0になるので、どんなイワシとも組み合わせられない（もちろん、(0,0)のイワシ同士も組み合わせられない）孤高のイワシです。
よって、そいつ専用のバケツ（図の右下）に入れます。
＜(0, *), (*, 0) のイワシ＞
次に、(0, 任意の整数), (任意の整数, 0) のイワシです。
こいつらは、数式に当てはめてみると、お互い仲が悪く、また、(1~N, 1~N) の普通のイワシとは仲が良いと分かります。
よって、この組み合わせは2つのセクションに区分されたバケツに入れたいです。
そこで、こいつは「(0, 0)」とラベルのついたバケツに入れることにします。
本当は(0, *), (*, 0)なので違いますが、こうすることで、最後の計算を統一的に行うことができます。
実際の数え上げ
これで、各イワシをバケツに入れることができました。
あと少しです。
MODのとり方に気を付けながら、丁寧に計算をしていきます。
1. 普通のイワシ（(0, *), (*, 0) のイワシも含む）の取り方
各バケツの両方のセクションから同時に取ることはできません。
なので、各バケツからの取り方は「セクション1の取り方の個数」＋「セクション2の取り方の個数」となります（同時に取れないので「×」ではなく「＋」）。
セクション1からの取り方は、各イワシの数だけ「取るか取らないかの2択」をするわけなので、2^イワシ数 です。
ということで、 2^セクション1のイワシ数 + 2^セクション2のイワシ数 としたいですが、これだと「1つもイワシを取らない場合」をダブルカウントしていますので、
2^セクション1のイワシ数 + 2^セクション2のイワシ数 - 1 が正解です。
（なお、引き算をするときにはMODが負になることがありますので、負になっていたら + MODをしなくてはいけないので注意です。）
各バケツ毎の取り方の組み合わせは自由なので、毎回の計算で出た数値は足していくのではなく、掛けていきます。
類問
問題を読んでも「え？ これ類問？」となるかもしれません（実際、公式解説PDFにも想定解として載っていません）が、
今回のように「mapで作ったバケツにpairを入れる」テクと、またもやバケツにおけるテクである「バケツに数以外（boolなど）を入れる」というテク（今回は使っていないですが）によって、かなり直感的に分かりやすく実装しやすい解き方ができます。
