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):
import math
import collections

n = int(input())
mod = 10 * 6 + 7
c = []
d = []

tan = []
atan = []

for _ in range(n):
    a, b = map(int, input().split())
    if b == 0: tan.append(float('inf'))
    else: tan.append(a / b)
    if a == 0: atan.append(float('inf'))
    else: atan.append(- b / a)

tan = collections.Counter(tan)
atan = collections.Counter(atan)

for key, value in tan.items():
    print(key)
    if abs(key) > 1: continue
    if atan[key] > 0:
        c.append(value)
        d.append(value)

# print(c, d)

ans = pow(2, n - sum(c) - sum(d), mod)
for i, j in zip(c, d):
    ans = (ans * (pow(2, i, mod) + pow(2, j, mod) - 1)) % mod
ans -= 1

print(ans)

import collections
import math

n = int(input())
m = 0
mod = 10 ** 9 + 7
c = []
d = []
frac = []

for _ in range(n):
    a, b = map(int, input().split())
    if a == 0 and b == 0:
        n -= 1
        m += 1
        continue
    if a == 0:
        frac.append('0/1')
    elif b == 0:
        frac.append(('1/0'))
    else:
        gcd = abs(math.gcd(a, b))
        sign = 1 if a * b > 0 else -1
        a = sign * abs(a) // gcd
        b = abs(b) // gcd
        frac.append('{}/{}'.format(a, b))

frac = collections.Counter(frac)
print(frac)

def inverse(key):
    if key == '0/1':
        return '1/0'
    elif key == '1/0':
        return '0/1'
    elif key[0] != '-':
        a, b = key.split('/')
        return '-{}/{}'.format(b, a)
    else:
        a, b = key[1:].split('/')
        return '{}/{}'.format(b, a)

for key, value in frac.items():
    if key[0] == '-' or key[0] == '0': continue
    if frac[inverse(key)] > 0:
        c.append(value)
        d.append(frac[inverse(key)])

ans = pow(2, n - sum(c) - sum(d), mod)
for i, j in zip(c, d):
    tmp = (pow(2, i, mod) + pow(2, j, mod) - 1)
    ans = (ans * (pow(2, i, mod) + pow(2, j, mod) - 1)) % mod
ans = (ans - 1 + m) % mod

print(ans)


import collections
import math

n = int(input())
m = 0
mod = 10 ** 9 + 7
c = []
d = []
frac = []

for _ in range(n):
    a, b = map(int, input().split())
    if a == 0 and b == 0:
        n -= 1
        m += 1
        continue
    if a == 0:
        frac.append('0/1')
    elif b == 0:
        frac.append(('1/0'))
    else:
        gcd = abs(math.gcd(a, b))
        sign = 1 if a * b > 0 else -1
        a = sign * abs(a) // gcd
        b = abs(b) // gcd
        frac.append('{}/{}'.format(a, b))

frac = collections.Counter(frac)
print(frac)

def inverse(key):
    if key == '0/1':
        return '1/0'
    elif key == '1/0':
        return '0/1'
    elif key[0] != '-':
        a, b = key.split('/')
        return '-{}/{}'.format(b, a)
    else:
        a, b = key[1:].split('/')
        return '{}/{}'.format(b, a)

for key, value in frac.items():
    if key[0] == '-' or key[0] == '0': continue
    if frac[inverse(key)] > 0:
        c.append(value)
        d.append(frac[inverse(key)])

ans = pow(2, n - sum(c) - sum(d), mod)
for i, j in zip(c, d):
    tmp = (pow(2, i, mod) + pow(2, j, mod) - 1) % mod
    ans = ans * tmp % mod
ans = (ans - 1 + m) % mod

print(ans)


import collections
import fractions

n = int(input())
mod = 10 ** 6 + 7
c = []
d = []

tan = []
atan = []

for _ in range(n):
    a, b = map(int, input().split())
    if b == 0: tan.append(float('inf'))
    else: tan.append(fractions.Fraction(a, b))
    if a == 0: atan.append(float('inf'))
    else: atan.append(fractions.Fraction(-1 * b, a))

print('yes')

import collections
import math

n = int(input())
m = 0
mod = 10 ** 9 + 7
c = []
d = []
frac = []

for _ in range(n):
    a, b = map(int, input().split())
    if a == 0 and b == 0:
        n -= 1
        m += 1
        continue
    if a == 0:
        frac.append('0/1')
    elif b == 0:
        frac.append(('1/0'))
    else:
        gcd = abs(math.gcd(a, b))
        sign = 1 if a * b > 0 else -1
        a = sign * abs(a) // gcd
        b = abs(b) // gcd
        frac.append('{}/{}'.format(a, b))

frac = collections.Counter(frac)

def inverse(key):
    if key == '0/1':
        return '1/0'
    elif key == '1/0':
        return '0/1'
    elif key[0] != '-':
        a, b = key.split('/')
        return '-{}/{}'.format(b, a)
    else:
        a, b = key[1:].split('/')
        return '{}/{}'.format(b, a)

for key, value in frac.items():
    if key[0] == '-' or key[0] == '0': continue
    if frac[inverse(key)] > 0:
        c.append(value)
        d.append(frac[inverse(key)])

ans = pow(2, n - sum(c) - sum(d), mod)
for i, j in zip(c, d):
    tmp = (pow(2, i, mod) + pow(2, j, mod) - 1) % mod
    ans = ans * tmp % mod
ans = (ans - 1 + m) % mod

print(ans)

Verdicts: Wrong Answer

Wrong Answer

Wrong Answer

Wrong Answer

Accepted