Problem:


Score: 500 points

Problem Statement

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.

Constraints

All values in input are integers.

1 \leq N \leq 2 \times 10^5

-10^{18} \leq A_i, B_i \leq 10^{18}

Input

Input is given from Standard Input in the following format:

N
A_1 B_1
:
A_N B_N

Output

Print the count modulo 1000000007.

Sample Input 1

3
1 2
-1 1
2 -1

Sample Output 1

5

There are five ways to choose the set of sardines, as follows:

The 1-st

The 1-st and 2-nd

The 2-nd

The 2-nd and 3-rd

The 3-rd

Sample Input 2

10
3 2
3 2
-1 1
2 -1
-3 -9
-8 12
7 7
8 1
8 2
8 4

Sample Output 2

479



Sample input:
3
1 2
-1 1
2 -1


Sample output:
5

Submission status: Accepted

Solution code:
import sys, os

if 'local' in os.environ :
    sys.stdin = open('./input.txt', 'r')

f = lambda:list(map(int, input().split()))


def gcd(a,b):
    return b if a == 0 else gcd(b%a, a)

def quick_pow(x,n, mod):
    ans= 1
    while n:
        if n&1:
            ans *= x
            ans %= mod
        x *= x
        x %= mod
        n >>= 1
    
    return ans


def solve():
    mod = 1000000007
    n = f()[0]

    dirs = {}

    all0 = 0
    x0 = 0
    y0 = 0

    for _ in range(n):
        a,b = f()
        if a ==0 and b == 0:
            all0 += 1
            continue
        if a == 0:
            x0 += 1
            continue
        if b == 0:
            y0 += 1
            continue

        if a <0:
            a = -a
            b = -b
        g = gcd(abs(a),abs(b))
        a //= g
        b //= g

        if a*b >0:
            if (a,b) not in dirs:
                dirs[(a,b)] = {}
                dirs[(a,b)][0] = 0
                dirs[(a,b)][1] = 0
            dirs[(a,b)][0] = dirs[(a,b)][0]+ 1
        else:
            if (-b,a) not in dirs:
                dirs[(-b,a)] = {}
                dirs[(-b,a)][0] = 0
                dirs[(-b,a)][1] = 0
            dirs[(-b,a)][1] = dirs[(-b,a)][1] + 1 
            
    
    ans = 1
    ans *= (quick_pow(2, x0, mod) + quick_pow(2, y0, mod)-1 + mod) % mod

    
    ans %= mod
    for _, l in dirs.items():
        ans *= (quick_pow(2, l[0], mod) + quick_pow(2, l[1], mod)-1 + mod)%mod
        ans %= mod

    
    ans -= 1
    if all0:
        ans+= all0
    
    ans += mod
    ans%= mod
    print(ans)
    

solve()

Submission status: Accepted

Solution code:
from collections import defaultdict
from math import gcd
C = defaultdict(lambda: 0)
for i in range(int(input())):
    x, y = map(int, input().split())
    g = max(gcd(x, y), 1)
    x, y = x // g, y // g
    if y < 0 or (x == -1 and y == 0):
        x, y = -x, -y
    C[(x, y)] += 1
S = set()
for x, y in C:
    if x > 0 and y >= 0:
        S.add((x, y))
    if x <= 0 and y > 0:
        S.add((y, -x))
ans = 1
p = 10**9 + 7
for x, y in S:
    ans *= pow(2, C[(x, y)], p) + pow(2, C[(-y, x)], p) - 1
    ans %= p
print((ans + C[(0, 0)] - 1) % p)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import math

n = int(input())

mod = 10**9+7

data = {}
zero_zero = 0

for i in range(n):
    a, b = list(map(int, input().split()))
    # # print(a, b)
    if a == 0 and b == 0:
        zero_zero += 1
        continue
    gcd = math.gcd(a, b)
    a, b = a//gcd, b//gcd
    if a < 0:
        a, b = -a, -b

    if a == 0:  # (0, 1)
        a, b = 0, 1

    elif b == 0:  # (1, 0)
        a, b = 1, 0

    # print(a, b)
    # print()

    if b <= 0:  # (+, -) or (1, 0)
        if (-b, a) in data:
            data[(-b, a)][1] += 1
        else:
            data[(-b, a)] = [0, 1]
    elif b > 0:  # (+, +) or (1, 0)
        if (a, b) in data:
            data[(a, b)][0] += 1
        else:
            data[(a, b)] = [1, 0]

# print(data)
# print(zero_zero)

power_2 = [1]
for i in range(1, 2*10**5+100):
    power_2.append(power_2[i-1]*2 % mod)

ans = 1
# print(ans)
# print()
for (a, b), (l, m) in data.items():
    ans *= (power_2[l]+power_2[m]-1) % mod
    # print(power_2[l]+power_2[m]-1)
    # print(ans)
    # print()

ans = ans - 1  # removed not selected
ans += zero_zero
print(ans % mod)
# count_pp = 0
# count_pm = 0
# ans = 0
# while(1):
#     pp_tmp = plus_plus[count_pp]
#     pm_tmp = plus_minus[count_pm]

#     print("pp_tmp", pp_tmp)
#     print("pm_tmp", pm_tmp)

#     if pp_tmp[0]*pm_tmp[0] + pp_tmp[1]*pm_tmp[1] == 0:
#         pp_mag, pm_mag = 1, 1  # magnitude
#         while(1):
#             if count_pp < len(plus_plus)-1:
#                 if plus_plus[count_pp] == plus_plus[count_pp+1]:
#                     pp_mag += 1
#                     count_pp += 1
#                 else:
#                     break
#             else:
#                 break
#         while(1):
#             if count_pm < len(plus_minus)-1:
#                 if plus_minus[count_pm] == plus_minus[count_pm+1]:
#                     pm_mag += 1
#                     count_pm += 1
#                 else:
#                     break
#             else:
#                 break
#         ans += pp_mag*pm_mag

#     elif pp_tmp[2]*pm_tmp[2] > -1:
#         count_pp += 1

#     elif pp_tmp[2]*pm_tmp[2] < -1:
#         count_pm += 1

#     if count_pp == len(plus_plus)-1:
#         break
#     if count_pm == len(plus_minus)-1:
#         break
#     print(1)

# ans += zero_zero
# n = n - zero_zero
# count = ((n % mod) * ((n-1) % mod))//2
# count -= (negative) % mod

# print(count % mod)

Submission status: Accepted

Solution code:
from math import gcd
MOD = 10 ** 9 + 7
N = int(input())
d = dict()
zeros = 0
for _ in range(N):
    a, b = tuple(map(int, input().split()))
    if not any((a, b)):
        zeros += 1
        continue
    g = gcd(a, b) * (a // abs(a)) if all((a, b)) else a if a else b
    p = a // g, b // g
    d[p] = d.get(p, 0) + 1
done = set()
total = 1
for (a, b), v in d.items():
    if (b, -a) in done or (-b, a) in done:
        continue
    done.add((a, b))
    w = d.get((b, -a), 0) + d.get((-b, a), 0)
    total = total * (pow(2, v, MOD) + pow(2, w, MOD) - 1) % MOD
print((total + zeros - 1) % MOD)

Submission status: Accepted

Solution code:
from math import gcd
n = int(input())
C = {}
z = 0
for i in range(n):
    x, y = map(int, input().split())
    if x == 0 and y == 0:
        z += 1
        continue
    g = gcd(x, y)
    x, y = x // g, y // g
    if y < 0:
        x, y = -x, -y
    try:
        C[(x, y)] += 1
    except KeyError:
        C[(x, y)] = 1
ans = 1
p = 10**9 + 7
for x, y in C:
    if C[(x, y)] == 0:
        continue
    a = C[(x, y)]
    if x > 0:
        x0, y0 = -y, x
    else:
        x0, y0 = y, -x
    try:
        b = C[(x0, y0)]
        C[(x0, y0)] = 0
    except KeyError:
        b = 0
    ans *= pow(2, a, p) + pow(2, b, p) - 1
    ans %= p
    C[(x, y)] = 0
print((ans + z - 1) % p)

Submission status: Accepted

Solution code:
def main():
    from sys import setrecursionlimit, stdin
    from os import environ
    from collections import defaultdict, deque, Counter
    from math import ceil, floor, gcd
    from itertools import accumulate, combinations, combinations_with_replacement
    setrecursionlimit(10**6)
    dbg = (lambda *something: print(*something)) if 'TERM_PROGRAM' in environ else lambda *x: 0
    input = lambda: stdin.readline().rstrip()
    LMIIS = lambda: list(map(int,input().split()))
    II = lambda: int(input())
    P = 10**9+7
    INF = 10**9+10

    N = II()
    args = defaultdict(lambda:defaultdict(lambda:[0]*2))
    zeros = 0
    for _ in range(N):
        x,y = map(int,input().split())
        if x == 0:
            if y == 0:
                zeros += 1
            else:
                args[0][0][0] += 1
            continue
        elif y == 0:
            args[0][0][1] += 1
            continue
        
        g = gcd(x,y)
        x2,y2 = abs(x//g),abs(y//g)
        if x*y < 0:
            args[x2][y2][1] += 1
        else:
            args[y2][x2][0] += 1

    ans = 1
    for y, a in args.items():
        for x, p in a.items():
            ans *= (pow(2,p[0],P) + pow(2,p[1],P) -1)
            ans %= P
    print((ans + zeros -1 + P)%P)

main()

Submission status: Accepted

Solution code:
from math import gcd

n = int(input())
ration = dict()
used = dict()
for _ in range(n):
    a, b = map(int, input().split())
    if a == 0 or b == 0:
        if a == b == 0:
            r = '0'
        elif a == 0:
            r = '0a'
        else:
            r = '0b'
    else:
        s = '-' if (a < 0) ^ (b < 0) else '+'
        a = abs(a)
        b = abs(b)
        g = gcd(a, b)
        r = f'{s} {a//g} {b//g}'
    ration[r] = ration.get(r, 0) + 1
    used[r] = 0

res = 1
mod = 10**9+7
add = 0
for k, v in ration.items():
    if used[k]:
        continue
    if k == '0':
        add += v
        used[k] = 1
    elif k == '0a' or k == '0b':
        res *= 2**ration.get('0a', 0) + 2**ration.get('0b', 0) - 1
        used['0a'] = used['0b'] = 1
    else:
        r = k.split()
        l = f'{"-" if r[0]=="+" else "+"} {r[2]} {r[1]}'
        res *= 2**v + 2**ration.get(l, 0) - 1
        used[k] = used[l] = 1
    res %= mod

res += add
res -= 1
if res < 0:
    res += mod
print(res)

Submission status: Accepted

Solution code:
from collections import defaultdict
import math

def main():
    n = int(input())
    mod = 1000000007
    zeroes = 0
    quadrant1 = defaultdict(int)
    quadrant2 = defaultdict(int)

    for _ in range(n):
        a, b = map(int, input().split())
        if a == b == 0:
            zeroes += 1
            continue

        g = math.gcd(a, b)
        a, b = a//g, b//g 
        
        if b < 0:
            a, b = -a, -b
        
        if a <= 0:
            a, b = b, -a
            quadrant1[(a, b)] += 0
            quadrant2[(a, b)] += 1
        else:
            quadrant1[(a, b)] += 1
            quadrant2[(a, b)] += 0
    
    ans = 1
    for key, value in quadrant1.items():
        now = 1
        now += pow(2, value, mod) - 1
        now += pow(2, quadrant2[key], mod) - 1
        ans = (ans * now) % mod
    
    ans += (zeroes - 1)
    return ans % mod

if __name__ == '__main__':
    print (main())

Submission status: Accepted

Solution code:
from collections import defaultdict
import math


def main():
    n = int(input())
    mod = 1000000007
    zeroes = 0
    counter1 = defaultdict(int)
    counter2 = defaultdict(int)
    for _ in range(n):
        x, y = [int(x) for x in input().split()]

        if x == y == 0:
            zeroes += 1
            continue

        denominator = math.gcd(x, y)
        x, y = x // denominator, y // denominator

        if y < 0:
            # quadrant III, IV -> I, II
            x, y = -x, -y

        if x <= 0:
            # round 90° from quadrant II to I
            x, y = y, -x
            counter2[(x, y)] += 1
            counter1[(x, y)] += 0
        else:
            counter1[(x, y)] += 1
            counter2[(x, y)] += 0

    ans = 1
    for k, v in counter1.items():
        now = 1
        now += pow(2, v, mod) - 1
        now += pow(2, counter2[k], mod) - 1
        ans = ans * now % mod
    ans += zeroes
    ans -= 1  # choose no fish
    return ans % mod


if __name__ == '__main__':
    print(main())

Submission status: Accepted

Solution code:
from math import gcd
n = int(input())
ab = [list(map(int, input().split())) for _ in range(n)]
mod = 1000000007

#%%

kai = [1]*(n+1)
gyaku = [1]*(n+1)

for i in range(2, n+1):
    kai[i] = kai[i-1]*i % mod
    gyaku[i] = gyaku[i-1]*pow(i, mod-2, mod) %mod

azero = 0
bzero = 0
zerozero = 0
dict_patterns = {}
dict_patterns_minus = {}
all_effective = 0
answer = 0
dict_patterns["1,0"] = 0
dict_patterns["0,-1"] = 0

for i in range(n):
    minus = False
    a, b = ab[i]
    if a == 0 and b == 0:
        zerozero += 1
        continue
    elif b == 0:
        dict_patterns["1,0"] += 1
        continue
    elif a == 0:
        dict_patterns["0,-1"] += 1
        continue
    
    common = gcd(a,b)
    a = a//common
    b = b//common
    
#%%
    
    if a < 0 and b < 0:
        a = -a
        b = -b
    elif a < 0:
        a = -a
        b = -b
    
    
    to_str = str(a)+","+str(b)
    if to_str not in dict_patterns:
        dict_patterns[to_str] = 1
    else:
        dict_patterns[to_str] += 1


keys = list(dict_patterns.keys())
patterns = []
test = []
for i in range(len(keys)):
    pattern_A = dict_patterns[keys[i]]
    dict_patterns[keys[i]] = 0
    pattern_B = 0
    a, b = map(int, keys[i].split(","))
    
    if str(b)+","+str(-a) in dict_patterns:
        pattern_B += dict_patterns[str(b)+","+str(-a)]
        dict_patterns[str(b)+","+str(-a)] = 0
    if str(-b)+","+str(a) in dict_patterns:
        pattern_B += dict_patterns[str(-b)+","+str(a)]
        dict_patterns[str(-b)+","+str(a)] = 0
    if pattern_A != 0 or pattern_B != 0:
        patterns.append(max(2**pattern_A-1,0) + max(2**pattern_B-1,0)+1)  
    test.append([pattern_A, pattern_B])

answer = 1
for i in range(len(patterns)):
    answer = answer*patterns[i] % mod

print((answer-1+zerozero)%mod)

Submission status: Accepted

Solution code:
from math import gcd
n = int(input())
ab = [list(map(int, input().split())) for _ in range(n)]
mod = 1000000007

#%%

kai = [1]*(n+1)
gyaku = [1]*(n+1)

for i in range(2, n+1):
    kai[i] = kai[i-1]*i % mod
    gyaku[i] = gyaku[i-1]*pow(i, mod-2, mod) %mod

azero = 0
bzero = 0
zerozero = 0
dict_patterns = {}
dict_patterns_minus = {}
all_effective = 0
answer = 0
dict_patterns["1,0"] = 0
dict_patterns["0,-1"] = 0

for i in range(n):
    minus = False
    a, b = ab[i]
    if a == 0 and b == 0:
        zerozero += 1
        continue
    elif b == 0:
        dict_patterns["1,0"] += 1
        continue
    elif a == 0:
        dict_patterns["0,-1"] += 1
        continue
    common = gcd(a,b)
    a, b = int(a//common), int(b//common)
    if a < 0 and b < 0:
        a,b = -a,-b
    elif a < 0:
        a,b = -a,-b
        minus = True
    elif b<0:
        minus = True
    
    to_str = str(a)+","+str(b)
    if to_str not in dict_patterns:
        if minus == False:
            dict_patterns[to_str] = 1
        else:
            dict_patterns[to_str] = 1
    else:
        if minus == False:
            dict_patterns[to_str] += 1
        else:
            dict_patterns[to_str] += 1

#%%

keys = list(dict_patterns.keys())
patterns = []
test = []
for i in range(len(keys)):
    pattern_A = dict_patterns[keys[i]]
    dict_patterns[keys[i]] = 0
    pattern_B = 0
    a, b = map(int, keys[i].split(","))
    if str(b)+","+str(-a) in dict_patterns:
        pattern_B += dict_patterns[str(b)+","+str(-a)]
        dict_patterns[str(b)+","+str(-a)] = 0
    elif str(-b)+","+str(a) in dict_patterns:
        pattern_B += dict_patterns[str(-b)+","+str(a)]
        dict_patterns[str(-b)+","+str(a)] = 0
    if pattern_A != 0 or pattern_B != 0:
        patterns.append(max(2**pattern_A-1,0) + max(2**pattern_B-1,0) + 1)  
    test.append([pattern_A, pattern_B])
#%%
answer = 1
for i in range(len(patterns)):
    answer = answer*patterns[i] % mod

print((answer-1+zerozero)%mod)

Submission status: Accepted

Solution code:
#!python3

import sys
from collections import defaultdict
from math import gcd

iim = lambda: map(int, input().rstrip().split())

def resolve():
    N = input()
    it = map(int, sys.stdin.read().split())
    mod = 10**9 + 7

    d1 = [defaultdict(int), defaultdict(int)]
    z0 = za = zb = 0
    for ai, bi in zip(it, it):
        t = ai * bi
        if t == 0:
            if ai != 0:
                za += 1
            elif bi != 0:
                zb += 1
            else:
                z0 += 1
            continue

        ci = gcd(ai, bi)
        ai, bi = ai // ci, bi // ci

        t = t < 0
        if ai < 0:
            ai, bi = -ai ,-bi

        d1[t][(ai, bi)] += 1


    a1, a2 = d1
    ans = 1
    z1 = 0
    for (ai, bi), v in a1.items():
        k2 = (bi, -ai)
        if k2 in a2:
            v2 = a2[k2]
            ans *= pow(2, v, mod) + pow(2, v2, mod) - 1
            ans %= mod
        else:
            z1 += v

    for (ai, bi), v in a2.items():
        k2 = (-bi, ai)

        if k2 in a1: continue

        z1 += v
    ans *= pow(2, za, mod) + pow(2, zb, mod) - 1
    ans %= mod
    ans *= pow(2, z1, mod)

    print((ans-1+z0) % mod)



if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
from collections import defaultdict
from math import gcd

def main():
    mod=1000000007
    n=int(input())
    AB=[tuple(map(int,input().split())) for _ in range(n)]
    Cnt=defaultdict(int)
    zero=0
    for a,b in AB:
        if a==0 and b==0:
            zero+=1
        elif a==0:
            Cnt[(0,1)]+=1
        elif b==0:
            Cnt[(1,0)]+=1
        elif b!=0 and a>0:
            Cnt[(a//gcd(a,b),b//gcd(a,b))]+=1
        else: #b!=0 and a<0:
            Cnt[(-a//gcd(a,b),-b//gcd(a,b))]+=1
    ans=1
    for Key in list(Cnt.keys()):
        if Key!=(0,1) and Key!=(1,0):
            a,b=Key
            if b>0:
                ans*=pow(2,Cnt[Key],mod)+pow(2,Cnt[(b,-a)],mod)-1
                ans%=mod
                Cnt[(b,-a)]=0
            else:
                ans*=pow(2,Cnt[Key],mod)+pow(2,Cnt[(-b,a)],mod)-1
                ans%=mod
                Cnt[(-b,a)]=0
            Cnt[Key]=0
        else:
            ans*=pow(2,Cnt[(0,1)],mod)+pow(2,Cnt[(1,0)],mod)-1
            ans%=mod
            Cnt[(0,1)],Cnt[(1,0)]=0,0
    print((ans-1+zero)%mod)
    
if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:
from collections import defaultdict
from math import gcd

MOD = 1000000007
N = int(input())
zeros = 0
bads = defaultdict(lambda: [0, 0])
for _ in range(N):
    x, y = map(int, input().split())
    # 両方ゼロの時の例外処理
    if x == 0 and y == 0:
        zeros += 1
        continue
    # 180度回転
    if y < 0 or (y == 0 and x < 0):
        x, y = -x, -y
    g = gcd(x, y)
    x, y = x // g, y // g
    if x > 0:
        bads[(x, y)][0] += 1
    else:
        bads[(y, -x)][1] += 1

ans = 1
for k, l in bads.values():
    ans *= (pow(2, k, MOD) - 1) + (pow(2, l, MOD) - 1) + 1
    ans %= MOD
print((ans + zeros - 1) % MOD)

Submission status: Accepted

Solution code:
from math import gcd
MOD = 10**9+7
N = int(input())
d = {}
zero = 0
for _ in range(N):
    a, b = map(int, input().split())
    if a == b == 0:
        zero += 1
        continue
    # 正規化する
    if b < 0:
        b = -b
        a = -a
    g = gcd(a, b)
    b //= g
    a //= g
    # 入力のbが0の時はaの値を正の1に統一する
    if b == 0 and a == -1:
        a = 1

    # 今bは必ず正
    # aも正，すなわち傾きが正のとき
    if a > 0:
        if (a, b) in d:
            d[(a, b)][0] += 1
        else:
            d[(a, b)] = [1, 0]
    else:
        # aが負，すなわち傾きが負の時
        if (b, -a) in d:
            d[(b, -a)][1] += 1
        else:
            d[(b, -a)] = [0, 1]

ans = 1
for (a, b), (k, l) in d.items():
    ans *= (pow(2, k, MOD)-1 + pow(2, l, MOD)-1 + 1)  # 最後の+1はどちらからも選ばなかったパターン
    ans %= MOD
ans -= 1
ans += zero
ans %= MOD
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter
import math

n = int(input())
ab = []
mod = 10**9+7

num_ab0 = 0
num_a0 = 0
num_b0 = 0

for i in range(n):
    A, B = map(int, input().split())
    if A == 0 and B == 0:
        num_ab0 += 1
    elif A == 0:
        num_a0 += 1
    elif B == 0:
        num_b0 += 1
    else:
        g = math.gcd(A, B)
        if A < 0:
            A = -A
            B = -B
        ab.append((A//g, B//g))

c = Counter(ab)

total = 2 ** num_a0 + 2 ** num_b0 - 1
for k, v in c.items():
    if k[1] < 0:
        num = c.get((-k[1], k[0]))
    else:
        num = c.get((k[1], -k[0]))

    if num:
        if k[1] > 0:
            total *= (2 ** v + 2 ** num - 1)
    else:
        total *= 2 ** v

print((total - 1 + num_ab0) % mod)

Submission status: Accepted

Solution code:
from sys import stdin
from collections import defaultdict
from math import gcd


def main():
    MOD = 1000000007

    N, *AB = map(int, stdin.buffer.read().split())

    d = defaultdict(int)
    n_zeros = 0

    for a, b in zip(AB[::2], AB[1::2]):
        if a == 0 and b == 0:
            n_zeros += 1
            continue

        g = gcd(a, b)
        a, b = a // g, b // g

        if a * b > 0 or b == 0:
            c = (abs(a), abs(b))
        else:
            c = (-abs(a), -abs(b))

        d[c] += 1

    ans = 1
    n_not_paired = 0
    for ab, n in d.items():
        ab_pair = (-ab[1], -ab[0])
        if ab_pair in d:
            if ab[0] > 0:
                m = d[ab_pair]
                ans = ans * (pow(2, n, MOD) + pow(2, m, MOD) - 1) % MOD
        else:
            n_not_paired += n

    ans = (ans * pow(2, n_not_paired, MOD) + n_zeros - 1) % MOD
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from math import gcd
from collections import Counter

mod = 10 ** 9 + 7

N, *AB = map(int, open(0).read().split())

def std(a, b):
    if a == 0:
        return (0, int(b != 0))

    g = gcd(a, b)
    a, b = a // g, b // g
    return (a, b) if a > 0 else (-a, -b)

C = Counter(std(a, b) for a, b in zip(*[iter(AB)] * 2))

ans = 1
cnt = 0
for (a, b), v in C.items():
    if b > 0:
        if (b, -a) in C:
            ans *= -1 + pow(2, v, mod) + pow(2, C[(b, -a)], mod)
            ans %= mod
        else:
            cnt += v
    elif (-b, a) not in C:
        cnt += v

ans *= pow(2, cnt, mod)
ans += C[(0, 0)] - 1

print(ans % mod)

Submission status: Accepted

Solution code:
from math import gcd
from collections import Counter

mod = 10 ** 9 + 7

N, *AB = map(int, open(0).read().split())

def std(a, b):
    if a == 0:
        return (0, int(b != 0))

    g = gcd(a, b)
    a, b = a // g, b // g
    return (a, b) if a > 0 else (-a, -b)

C = Counter()
for a, b in zip(*[iter(AB)] * 2):
    C[std(a, b)] += 1

ans = 1
cnt = 0
for (a, b), v in C.items():
    if b > 0:
        if (b, -a) in C:
            ans *= -1 + pow(2, v, mod) + pow(2, C[(b, -a)], mod)
            ans %= mod
        else:
            cnt += v
    elif (-b, a) not in C:
        cnt += v

ans *= pow(2, cnt, mod)
ans += C[(0, 0)] - 1

print(ans % mod)

Submission status: Accepted

Solution code:
from math import gcd
from collections import Counter

mod = 10 ** 9 + 7

N, *AB = map(int, open(0).read().split())

def std(a, b):
    if a == 0:
        return (0, 1)

    g = gcd(a, b)
    a, b = a // g, b // g
    return (a, b) if a > 0 else (-a, -b)

C = Counter()
orig = 0
for a, b in zip(*[iter(AB)] * 2):
    if a == b == 0:
        orig += 1
    else:
        C[std(a, b)] += 1

ans = 1
cnt = 0
for (a, b), v in C.items():
    if b > 0:
        if (b, -a) in C:
            ans *= -1 + pow(2, v, mod) + pow(2, C[(b, -a)], mod)
            ans %= mod
        else:
            cnt += v
    elif (-b, a) not in C:
        cnt += v

ans *= pow(2, cnt, mod)
ans += orig - 1

print(ans % mod)

Submission status: Accepted

Solution code:
from math import gcd
MOD = 10**9 + 7
MOD_t_MAX = 2*(10**5) + 10

fac  = [None] * MOD_t_MAX
finv = [None] * MOD_t_MAX
inv  = [None] * MOD_t_MAX
def MOD_COM_init():
    fac[0] = fac[1] = 1
    finv[0] = finv[1] = 1
    inv[1] = 1
    for i in range(2, MOD_t_MAX):
        fac[i] = fac[i - 1] * i % MOD
        inv[i] = MOD - inv[MOD%i] * (MOD // i) % MOD
        finv[i] = finv[i - 1] * inv[i] % MOD
def MOD_COM(n, k):
    if n < k:
        return 0
    if n < 0 or k < 0:
        return 0
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD

def main():
    n = int(input())
    iwashi = [list(map(int, input().split())) for _ in range(n)]
    MOD_COM_init()
    ans = pow(2, n, MOD)
    ans -= 1
    ans %= MOD
    dic = {}
    cnt = [0, 0, 0, 0]
    for i in range(n):
        a, b = iwashi[i]
        if a == 0 and b == 0:
            cnt[3] += 1
        elif b == 0:
            cnt[2] += 1
        elif a == 0:
            cnt[1] += 1
        else:
            cnt[0] += 1
            fa, fb = False, False
            if a < 0:
                fa = True
                a *= -1
            if b < 0:
                fb = True
                b *= -1
            c = gcd(a, b)
            a //= c
            b //= c
            if (fa and not fb) or (not fa and fb):
                a *= -1
            tmp = (a, b)
            if tmp in dic:
                dic[tmp] += 1
            else:
                dic[tmp] = 1
    L = 1
    if 0 < cnt[3]:
        p = (pow(2, n-cnt[3], MOD)-1)*MOD_COM(cnt[3], 1)%MOD
        q = 0
        for i in range(2, cnt[3]+1):
            q += MOD_COM(cnt[3], i)
        q *= pow(2, n-cnt[3], MOD)
        ans -= p+q
        ans %= MOD
    if 0 < cnt[1] and 0 < cnt[2]:
        p = (pow(2, cnt[1], MOD)-1) * (pow(2, cnt[2], MOD)-1) % MOD
        p *= pow(2, cnt[0], MOD)
        L *= ((pow(2, cnt[1], MOD)-1) + (pow(2, cnt[2], MOD)-1) + 1) % MOD
        ans -= p
        ans %= MOD
    if 1 < cnt[0]:
        p = 0
        st = set()
        for v in dic.keys():
            if v in st:
                continue
            u = None
            if v[0] > 0 and v[1] > 0:
                u = (-1*v[1], v[0])
            else:
                u = (v[1], -1*v[0])
            x = dic[v]
            y = 0
            if u in dic:
                y = dic[u]
            cnt[0] -= x+y
            q = (pow(2, x, MOD)-1) * (pow(2, y, MOD)-1) * pow(2, cnt[0], MOD) * L % MOD
            p += q
            L *= ((pow(2, x, MOD)-1) + (pow(2, y, MOD)-1) + 1) % MOD
            L %= MOD
            p %= MOD
            st.add(v)
            st.add(u)
        p %= MOD
        ans -= p
        ans %= MOD
    print(ans%MOD)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from math import gcd
MOD = 10**9 + 7
n = int(input())
zero = 0
cnt = dict()
for i in range(n):
    x, y = map(int, input().split())
    if x == 0 and y == 0:
        zero += 1
        continue
    g = gcd(x, y)
    x //= g
    y //= g
    if y < 0 or (y == 0 and x < 0):
        x *= -1
        y *= -1
    rot_90 = 1 if x <= 0 else 0
    if rot_90:
        x, y = y, -x
    try:
        cnt[(x, y)][rot_90] += 1
    except KeyError:
        cnt[(x, y)] = [int(not rot_90), rot_90]

ans = 1
for s, t in cnt.values():
    now = 1
    now += (pow(2, s, MOD) - 1) % MOD
    now += (pow(2, t, MOD) - 1) % MOD
    ans *= now
ans -= 1
ans += zero
print(ans % MOD)

Submission status: Accepted

Solution code:
import math

n=int(input())
D={}
for _ in range(n):
    a,b=map(int, input().split())
    if a==0 and b==0:
        key=(0,0)
    elif a==0:
        key=(0,1)
    elif b==0:
        key=(1,0)
    else:
        if a<0:
            a=-a
            b=-b
        g=math.gcd(a, abs(b))
        key=(a//g, b//g)
    if key not in D:
        D[key]=0
    D[key]+=1

mod=10**9+7
ans=1
zz=0

for k1, v1 in D.items():
    if v1==0:
        continue
    if k1==(0,0):
        zz+=v1
        continue

    if k1[1]>0:
        k2=(k1[1], -k1[0])
    else:
        k2=(-k1[1], k1[0])

    if k2 not in D:
        ans=ans*pow(2, v1, mod)%mod
    else:
        v2=D[k2]
        m=(pow(2, v1, mod)+pow(2, v2, mod)-1)%mod
        ans=ans*m%mod
        D[k2]=0

print((ans+zz-1)%mod)

Submission status: Accepted

Solution code:
import math

n=int(input())
D={}
for _ in range(n):
    a,b=map(int, input().split())
    if a==0 and b==0:
        key=(0,0)
    elif a==0:
        key=(0,1)
    elif b==0:
        key=(1,0)
    else:
        if a<0:
            a=-a
            b=-b
        g=math.gcd(a, abs(b))
        key=(a//g, b//g)
    if key not in D:
        D[key]=0
    D[key]+=1

mod=10**9+7
ans=1
zz=0

for k1, v1 in D.items():
    if k1==(0,0):
        zz+=v1
        continue
    if v1==0:
        continue

    if k1[1]>0:
        k2=(k1[1], -k1[0])
    else:
        k2=(-k1[1], k1[0])

    if k2 not in D:
        ans=ans*pow(2, v1, mod)%mod
    else:
        v2=D[k2]
        m=(pow(2, v1, mod)+pow(2, v2, mod)-1)%mod
        ans=ans*m%mod
        D[k2]=0

print((ans+zz-1)%mod)

Submission status: Accepted

Solution code:
def gcd(a,b):
    if b==0 or a == 0  : return a + b
    return gcd(b, a%b)
N = int(input())
d1 = {}
d2 = {}
zero = 0
for _ in range(N):
    A,B = map(int, input().split())
    if A == 0 and B == 0 :
        zero += 1
        continue
    d = gcd(abs(A), abs(B))
    A,B = A//d, B//d
    if B < 0 or (B==0 and A < 0):
        A,B = -A,-B
    if A > 0 :
        if (A,B) not in d1:d1[(A,B)]=0
        d1[(A,B)]+=1
    else :
        if (A,B) not in d2:d2[(A,B)] = 0
        d2[(A,B)] += 1
ret = []
for (x,y),count in d1.items():
    if (-y, x) in d2 :
        ret.append((count, d2[(-y,x)]))
    else :
        ret.append((count, 0))
for (x,y),count in d2.items():
    if (y,-x) not in d1:
        ret.append((count, 0))
mod = 10 ** 9 + 7
ans = 1
for p,q in ret:
    if q == 0 :
        ans *= 2**p
        ans %= mod
    else :
        ans *= (2**p + 2**q -1 )
        ans %= mod
print( (ans - 1 + zero ) % mod )

Submission status: Accepted

Solution code:
def gcd(a,b):
    if b==0 or a == 0  : return a + b
    return gcd(b, a%b)
N = int(input())
d1 = {}
d2 = {}
zero = 0
for _ in range(N):
    A,B = map(int, input().split())
    if A == 0 and B == 0 :
        zero += 1
        continue
    d = gcd(abs(A), abs(B))
    A,B = A//d, B//d
    if B < 0 or (B==0 and A < 0):
        A,B = -A,-B
    if A > 0 :
        if (A,B) not in d1:d1[(A,B)]=0
        d1[(A,B)]+=1
    else :
        if (A,B) not in d2:d2[(A,B)] = 0
        d2[(A,B)] += 1
ret = []
for (x,y),count in d1.items():
    if (-y, x) in d2 :
        ret.append((count, d2[(-y,x)]))
    else :
        ret.append((count, 0))
for (x,y),count in d2.items():
    if (y,-x) not in d1:
        ret.append((count, 0))
mod = 10 ** 9 + 7
ans = 1
for p,q in ret:
    if q == 0 :
        ans *= 2**p
        ans %= mod
    else :
        ans *= (2**p + 2**q -1 )
        ans %= mod
print( (ans - 1 + zero + mod) % mod )

Submission status: Accepted

Solution code:
import math
import numpy as np
def main():
    mod = 1000000007
    N = int(input())
    mp = {}
    zero = 0
    for _ in range(N):
        x , y = map(int, input().split())
        if x == 0 and y == 0:
            zero += 1
        else:
            g = math.gcd(x, y)
            x //= g
            y //= g
            rot = 0
            if x == 0:
                y = 1
            else:
                if y == 0:
                    rot = 1
                    x = 0
                    y = 1
                else:
                    if x < 0 and y < 0:
                        x *= -1
                        y *= -1
                    elif x < 0:
                        rot = 1
                        x *= -1
                        x, y = y, x
                    elif y < 0:
                        rot = 1
                        y *= -1
                        x, y = y, x
            if (x, y) not in mp.keys():
                mp[x, y] = [0, 0]
                mp[x, y][rot] = 1
            else:
                mp[x, y][rot] += 1
        #print(mp)    
    #print(mp)
    ans = 1
    for (a, b) in mp.keys():
        now = 1
        #now += np.power(2, mp[a, b][0]) -1 
        #now += np.power(2, mp[a, b][1]) -1
        now += pow(2, mp[a, b][0], mod) -1 
        now += pow(2, mp[a, b][1], mod) -1
        ans *= now % mod
    ans += zero - 1
    print(ans % mod)
            
if __name__ == '__main__':
    main()