Problem: We have caught N sardines. The _deliciousness_ and _fragrantness_ of the i-th sardine is A_i and B_i, respectively.  We will choose one or more of these sardines and put them into a cooler. However, two sardines on bad terms cannot be chosen at the same time.  The i-th and j-th sardines (i \neq j) are on bad terms if and only if A_i \cdot A_j + B_i \cdot B_j = 0.  In how many ways can we choose the set of sardines to put into the cooler? Since the count can be enormous, print it modulo 1000000007.

Submission attempts (in order):

from collections import Counter
mod = 1000000007

n = int(input())
a_div_b = []
a_0 = 0
b_0 = 0
a_b_0 = 0
for _ in range(n):
    a, b = map(int, input().split())
    if a == 0 or b == 0:
        if a == 0 and b == 0:
            a_b_0 += 1
        elif a == 0:
            a_0 += 1
        else b == 0:
            b_0 += 1
        continue
    if a * b < 0:
        a_div_b.append(a/b)
    else:
        a_div_b.append(b/a)

cnt = Counter(a_div_b)
cnt2 = sorted(cnt.items())
lst = []
total = 0
for num, _ in cnt2:
    if num > 0:
        break
    a1 = cnt[num]
    a2 = cnt[-num]
    if a1 * a2 != 0:
        total += a1 + a2
        lst.append([a1, a2])
if a_0 > 0 and b_0 > 0:
    total += a_0 + b_0
    lst.append([a_0, b_0])
n -= a_b_0
ans = pow(2, n - total, mod)
for a, b in lst:
    ans = (ans * (pow(2, a, mod) + pow(2, b, mod) - 1)) % mod
ans = (ans - 1 + a_b_0) % mod
    
print(ans)
    


from collections import Counter
mod = 1000000007

n = int(input())
a_div_b = []
a_0 = 0
b_0 = 0
a_b_0 = 0
for _ in range(n):
    a, b = map(int, input().split())
    if a == 0 or b == 0:
        if a == 0 and b == 0:
            a_b_0 += 1
        elif a == 0:
            a_0 += 1
        else b == 0:
            b_0 += 1
        continue
    if a * b < 0:
        a_div_b.append(a/b)
    else:
        a_div_b.append(b/a)

cnt = Counter(a_div_b)
cnt2 = sorted(cnt.items())
lst = []
total = 0
for num, _ in cnt2:
    if num > 0:
        break
    a1 = cnt[num]
    a2 = cnt[-num]
    if a1 * a2 != 0:
        total += a1 + a2
        lst.append([a1, a2])
if a_0 > 0 and b_0 > 0:
    total += a_0 + b_0
    lst.append([a_0, b_0])
n -= a_b_0
ans = pow(2, n - total, mod)
for a, b in lst:
    ans = (ans * (pow(2, a, mod) + pow(2, b, mod) - 1)) % mod
ans = (ans - 1 + a_b_0) % mod
    
print(ans)
    


from collections import defaultdict
from math import gcd
mod = 1000000007

n = int(input())
plus = defaultdict(int)
minus = defaultdict(int)
a_0 = 0
b_0 = 0
a_b_0 = 0
xxx = 10 ** 10
for _ in range(n):
    a, b = map(int, input().split())
    if a == 0 or b == 0:
        if a == 0 and b == 0:
            a_b_0 += 1
        elif a == 0:
            a_0 += 1
        else:
            b_0 += 1
        continue
    g = gcd(a, b)
    a //= g
    b //= g
    if a * b < 0:
        minus[(abs(a), abs(b))] += 1
    else:
        plus[(abs(b), abs(a))] += 1

total = 0
lst = []
for num, _ in minus.items():
    a1 = minus[num]
    a2 = plus[num]
    if a1 * a2 != 0:
        total += a1 + a2
        lst.append([a1, a2])
if a_0 > 0 and b_0 > 0:
    total += a_0 + b_0
    lst.append([a_0, b_0])
n -= a_b_0
ans = pow(2, n - total, mod)
for a, b in lst:
    ans = (ans * (pow(2, a, mod) + pow(2, b, mod) - 1)) % mod
ans = (ans - 1 + a_b_0) % mod
    
print(ans)
    


Verdicts: Runtime Error

Runtime Error

Accepted