ABC168 E - ∙ (Bullet)

問題原文

atcoder.jp

解法

実験とかすると、 は としていいことは分かる。（一旦０は無視で）

これをとりあえず集計したくなる。
集計の結果、例えば が 個、 と仲が悪いものの個数が 個 ということがわかれば、
S からも Tからも選ばない S から１つ以上選ぶ T から １つ以上選ぶ 通り数を足し合わせたものがそのキーに関しての通り数となって、答えが計算できそうということがわかる。

ただ、 と仲が悪いものは、 であったり、 であったりしてめんどくさい。
これは、片方がマイナスのものはマイナスを の方に押し付けることで、まとめて集計できる。
（たとえば、 は として集計する）

また、 のようなものは のようにしても問題ないので、そのようにして集計する。

のような片方０に関しては、 仲が悪いものは のようなもう片方が０のものになる。
後々計算しやすくするように、 が 0なら として、 が 0 なら として集計しておく。

は他の全てと仲が悪いので、「 から１つ選ぶ」という組合せを完全に別で計算する必要がある。
これは普通に の数を数えておくことでできる。

実装

複雑ではないんだけどひ〜

from math import gcd
from collections import defaultdict
N = int(input())
MOD = 10 ** 9 + 7

zero_zero_num = 0
fishes = defaultdict(int)
for i in range(N):
    a, b = map(int, input().split())
    if a == 0 and b == 0:
        zero_zero_num += 1
    elif a == 0:
        fishes[(0, -1)] += 1
    elif b == 0:
        fishes[(1, 0)] += 1
    else:
        g = gcd(a, b)
        a, b = a // g, b // g
        if (a > 0 and b > 0) or (a < 0 and b < 0):
            fishes[(abs(a), abs(b))] += 1
        else:
            a, b = (-a, -b) if a < 0 else (a, b)
            fishes[(a, b)] += 1


ans = 1
keys = list(fishes.keys())
visited = set()
for (kai, kbi) in keys:
    if kbi >= 0:
        kaj, kbj = kbi, -kai
    else:
        kaj, kbj = -kbi, kai

    if ((kai, kbi) in visited) or ((kaj, kbj) in visited):
        continue

    ans *= (1 + (pow(2, fishes[(kai, kbi)], MOD) - 1) + (pow(2, fishes[(kaj, kbj)], MOD) - 1))
    ans %= MOD
    visited.add((kai, kbi))
    visited.add((kaj, kbj))

print((ans + zero_zero_num - 1) % MOD)

感想

キーを集計しやすいようにあらかじめ変形する みたいなテク？なのかな。。。
bにマイナスを押し付けるとこんなに楽になるんだなぁ。勉強になりました。