atcoder168eが分からず困ってます。

Question

atcoderで下記問題に対して
問題
参考URL

下のコードで回答されている方がいて、
この39行目
result *= pow(2, i + j, 1000000007) + pow(2, k + l, 1000000007) - 1
ここの処理が理解できず困っています。
こなぜi+j乗とk+l乗でかけるのでしょうか？
ご教示よろしくお願いいたします。

from math import gcd

N = int(input())
AB = [map(int, input().split()) for _ in range(N)]

t = []
d = {}
d[0] = {}
d[0][0] = 0
for a, b in AB:
    i = gcd(a, b)
    if i != 0:
        a //= i
        b //= i
    t.append((a, b))
    d.setdefault(a, {})
    d[a].setdefault(b, 0)
    d[a][b] += 1

used = set()
result = 1
for a, b in t:
    if (a, b) in used:
        continue
    used.add((a, b))
    if a == 0 and b == 0:
        continue
    i = d[a][b]
    j, k, l = 0, 0, 0
    if -a in d and -b in d[-a]:
        j = d[-a][-b]
        used.add((-a, -b))
    if -b in d and a in d[-b]:
        k = d[-b][a]
        used.add((-b, a))
    if b in d and -a in d[b]:
        l = d[b][-a]
        used.add((b, -a))
    result *= pow(2, i + j, 1000000007) + pow(2, k + l, 1000000007) - 1
    result %= 1000000007
result += d[0][0] - 1
result %= 1000000007
print(result)

Answer 1

この問題は、イワシの特徴をベクトルで考えた場合、そのベクトルが直交する組はどのくらいあるかという問題に置き換えることができます。
例えばa,bを(a,b)のベクトルと考えると、(-b,a)との内積は0です。
また、(-b,a)は(-a,-b)とのベクトルの内積も0です。
なので、(a,b)と(-a,-b)は(-b,a)に対して同じグループと解釈することができます。

参考URLの、

また (-b, a), (b, -a) は (-a, -b) とも仲が悪いので、(a, b) と (-a, -b) はグループとなる.

という表現と同じです。

iとjは(a,b)(-a,-b)のグループで、kとlは(-b,a)(b,-a)のグループになります。
グループijとグループklのイワシは双方必ず仲が悪いです。
件の階乗の計算は、双方のグループからイワシを選択する組み合わせを表しています。

(ijグループ内でイワシを選ぶ全パターン)+(klグループ内でイワシを選ぶ全パターン)

なお、一番最後の-1は、どちらのグループからも1匹も選ばれなかった場合を除外しています。

このあたりの考え方はyoutubeの解説を見るとよく理解できるのではないかと思います。
（私はyoutube見ないと分かりませんでした）

Comments

[syuheisyosinsya]

内積も出てくるんですね。勉強になります。
回答依頼に対応していただき本当にありがとうございます！

[hope_mucci]

内積も出てくる、というより内積そのものです。
ぜひyoutubeの解説を見てください。イワシはこじつけということがよくわかります。
AtCoderのコンテストは高校～大学の数学知識がないと後半の問題は全然太刀打ちできないので、数学の勉強も必須です。