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
sys.setrecursionlimit(1000000000)
import math
from math import gcd
def lcm(a, b): return a * b // gcd(a, b)
from itertools import count, permutations, chain
from functools import lru_cache
from collections import deque, defaultdict
from pprint import pprint
ii = lambda: int(input())
mis = lambda: map(int, input().split())
lmis = lambda: list(mis())
INF = float('inf')
N1097 = 10**9 + 7

def meg(f, ok, ng):
    while abs(ok-ng)>1:
        mid = (ok+ng)//2
        if f(mid):
            ok=mid
        else:
            ng=mid
    return ok

def get_inv(n, modp):
    return pow(n, modp-2, modp)

def factorials_list(n, modp):    # 10**6
    fs = [1]
    for i in range(1, n+1):
        fs.append(fs[-1] * i % modp)
    return fs

def invs_list(n, fs, modp):     # 10**6
    invs = [get_inv(fs[-1], modp)]
    for i in range(n, 1-1, -1):
        invs.append(invs[-1] * i % modp)
    invs.reverse()
    return invs

def comb(n, k, modp):
    num = 1
    for i in range(n, n-k, -1):
        num = num * i % modp
    den = 1
    for i in range(2, k+1):
        den = den * i % modp
    return num * get_inv(den, modp) % modp

def comb_from_list(n, k, modp, fs, invs):   
    return fs[n] * invs[n-k] * invs[k] % modp

#

class UnionFindEx:
    def __init__(self, size):
        #正なら根の番号、負ならグループサイズ
        self.roots = [-1] * size
    def getRootID(self, i):
        r = self.roots[i]
        if r < 0:   #負なら根
            return i
        else:
            r = self.getRootID(r)
            self.roots[i] = r
            return r
    def getGroupSize(self, i):
        return -self.roots[self.getRootID(i)]
    def connect(self, i, j):
        r1, r2 = self.getRootID(i), self.getRootID(j)
        if r1 == r2:
            return False
        if self.getGroupSize(r1) < self.getGroupSize(r2):
            r1, r2 = r2, r1
        self.roots[r1] += self.roots[r2]    #サイズ更新
        self.roots[r2] = r1
        return True

Yes = 'Yes'
No = 'No'


def main():
    from fractions import Fraction
    N=ii()
    zero = 0
    d = defaultdict(lambda : [0, 0])
    for _ in range(N):
        x, y = mis()
        if x == y == 0:
            zero += 1
            continue
        if y < 0 or (y==0 and x < 0):
            x, y = -x, -y
        g = gcd(x, y)
        x //= g
        y //= g
        if x<=0:
            rot = True
            c = (y, -x)
        else:
            rot = False
            c = (x, y)
        d[c][rot] += 1
    #
    N -= zero
    ans = 1
    for (q1, q2) in d.values():
        ans *= (pow(2, q1, N1097) - 1) + (pow(2, q2, N1097) - 1) + 1
        ans %= N1097
    ans -= 1
    ans %= N1097
    print(ans + zero)






main()

Submission status: Accepted

Solution code:
N=int(input())
from collections import defaultdict
import math
d = defaultdict(int)
MOD=10**9+7
for i in range(N):
  a,b=map(int,input().split())
  x=math.gcd(abs(a),abs(b))
  if a==0:
    if b==0:
      k=(0,0)
    else:
      k=(0,1)
  elif b==0:
    k=(1,0)
  else:
    if a<0:
      a,b=-a,-b
    if b<0:
      a,b=a//x,-((-b)//x)
    else:
      a,b=a//x,b//x
    k=(a,b)
  d[k]+=1

ind=defaultdict(int)
index=1
_ans=[1]
for a,b in list(d.keys()):
  if a==b==0:
    continue
  if b<=0:
    _k=(-b,a)
  else:
    _k=(b,-a)
  if d[_k]==0:
    _ans[0]*=pow(2,d[(a,b)])
  else:
    if ind[_k]==0:
      _ans.append(pow(2,d[(a,b)],MOD))
      ind[(a,b)]=index
      index+=1
    else:
      _ans[ind[_k]]+=pow(2,d[(a,b)],MOD)-1
ans=1
for a in _ans:
  ans=ans*a%MOD
print((d[(0,0)]+ans-1+MOD)%MOD)

Submission status: Accepted

Solution code:
import math

MOD = 10**9 + 7
n = int(input())
mp = {}
ans1 = 0


def process(lst):
	a = lst[0]
	b = lst[1]
	gcd = math.gcd(a, b)
	a //= gcd
	b //= gcd
	if b < 0:
		a *= -1
		b *= -1
	a = abs(a) if b == 0 else a
	b = abs(b) if a == 0 else b
	lst[0] = a
	lst[1] = b
	return lst


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

	a, b = process([a, b])
	mp.setdefault((a, b), 0)
	mp[(a, b)] += 1

	a, b = process([-b, a])
	y = mp.setdefault( (a, b), 0)

ans = 1

taken = {}

for a, b in mp:
	if taken.get((a, b), 0):
		continue
	taken.setdefault((a, b), 0)
	taken[(a, b)] = 1

	x = mp.get( (a, b), 0)

	# print(a, b, x, end=" + ")
	a, b = process([-b, a])
	y = mp.get( (a, b), 0)

	taken.setdefault((a, b), 0)
	taken[(a, b)] = 1

	# print(a, b, y)
	ans = (ans * ( pow(2, x, MOD) + pow(2, y, MOD) - 1 + MOD) % MOD ) % MOD
	# print(ans)


ans = ( ans - 1 + ans1 + MOD ) % MOD
print(ans)

Submission status: Accepted

Solution code:
mod = 1000000007
n = int(input())

ab00 = 0
abx0 = 0
ab0x = 0
p = []
m = []

from math import gcd
for _ in range(n):
    i, j = map(int, input().split())
    if i == 0:
        if j == 0:
            ab00 += 1
        else:
            ab0x += 1
        continue
    elif j == 0:
        abx0 += 1
        continue
    k = gcd(i, j)
    i //= k
    j //= k
    if i > 0:
        if j > 0:
            p.append((i, j))
        else:
            m.append((-j, i))
    elif j > 0:
        m.append((j, -i))
    else:
        p.append((-i, -j))

m.sort()
p.sort()

ans = pow(2, ab0x, mod) + pow(2, abx0, mod) - 1
ans %= mod

mi = 0
pi = 0
while mi < len(m) and pi < len(p):
    if m[mi] == p[pi]:
        mi += 1
        mnum = 1
        while mi < len(m) and m[mi] == m[mi-1]:
            mi += 1
            mnum += 1
        pi += 1
        pnum = 1
        while pi < len(p) and p[pi] == p[pi-1]:
            pi += 1
            pnum += 1
        ans *= pow(2, mnum, mod) + pow(2, pnum, mod) - 1
        ans %= mod

    elif m[mi] < p[pi]:
        mi += 1
        mnum = 1
        while mi < len(m) and m[mi] < p[pi]:
            mi += 1
            mnum += 1
        ans *= pow(2, mnum, mod)
        ans %= mod
    
    else:
        pi += 1
        pnum = 1
        while pi < len(p) and p[pi] < m[mi]:
            pi += 1
            pnum += 1
        ans *= pow(2, pnum, mod)
        ans %= mod

ans *= pow(2, len(p) - pi, mod)
ans %= mod
ans *= pow(2, len(m) - mi, mod)
ans %= mod
ans = (ans - 1 + ab00) % mod
print(ans)

Submission status: Accepted

Solution code:
import math
from collections import deque

N = int(input())

a = []
b = []
for i in range(N):
    i1, i2 = map(int, input().split())
    g = math.gcd(i1,i2)
    if g == 0:
        a.append(i1)
        b.append(i2)
        continue
    x = i1 // g
    y = i2 // g
    if x < 0:
        x = - x
        y = - y 
    a.append(x)
    b.append(y)

P = {}
for i in range(N):
    if b[i] < 0:
        tmp = b[i]
        b[i] = a[i]
        a[i] = - tmp
        sgn = 1
    elif a[i] == 0 and b[i] != 0:
        a[i] = b[i]
        b[i] = 0
        sgn = 1
    else :
        sgn = 0

    if (a[i],b[i]) in P:
        P[(a[i],b[i])][sgn]=P[(a[i],b[i])][sgn] + 1
    elif sgn == 0 :
        P[(a[i],b[i])]=[1,0]
    else :
        P[(a[i],b[i])]=[0,1]


MOD = 1000000007
a1 = 1 
ans0=0
for k in P:
    if k == (0,0):
        ans0 = P[k][0]
    else:
        a1 = a1*(pow(2,P[k][0],MOD)+pow(2,P[k][1],MOD) - 1) % MOD

if ans0 != 0:
    ans = ans0 + a1 -1
else:
    ans = a1 -1
print(ans%MOD)

Submission status: Accepted

Solution code:
import math
from collections import Counter

MOD = 10**9 + 7
N = int(input())

I = []
zz = 0
sz = 0
tz = 0
for _ in range(N):
    a,b = map(int, input().split())

    # (a, b) = (0, 0)
    if a == 0 and b == 0:
        zz += 1
        continue
    # (a, b) = (0, #)
    if a == 0:
        sz += 1
        continue
    # (a, b) = (#, 0)
    if b == 0:
        tz += 1
        continue

    gcd = math.gcd(a, b)
    if b < 0:
        a *= -1
        b *= -1
    I.append((a//gcd,b//gcd))

S = []
T = []
C = Counter(I)
for a, b in C.keys():
    if a > 0:
        S.append(C[(a,b)])
        T.append(C[(-b,a)])
    else:
        if C[(b,-a)] == 0:
            S.append(0)
            T.append(C[(a,b)])

ans = 1
ans *= 2**sz + 2**tz - 1
ans %= MOD
for i in range(len(S)):
    ans *= 2**S[i] + 2**T[i] - 1
    ans %= MOD
ans += zz  # (0, 0)
ans -= 1
print(ans % MOD)

Submission status: Accepted

Solution code:
from math import gcd


MOD = 10**9 + 7

n = int(input())

cnt = {}

zero_cnt = 0
for i in range(n):
    a, b = map(int, input().split())
    if (a,b) == (0,0):
        zero_cnt += 1
        continue
    g = gcd(abs(a), abs(b))
    a //= g
    b //= g
    rotate = 0
    while not (a >= 0 and b > 0):
        a,b = -b,a
        rotate += 1
    if (a,b) not in cnt:
        cnt[(a,b)] = [0,0]

    cnt[(a,b)][rotate % 2] += 1

ans = 1
    
for key in cnt:
    A, B = cnt[key]
    ans *= 1 + pow(2, A, MOD) - 1 + pow(2, B, MOD) - 1
    ans %= MOD

ans += zero_cnt
ans -= 1
print(ans % MOD)

Submission status: Accepted

Solution code:
## coding: UTF-8
import math
MOD = 10**9+7
N = int(input())
#A = []
#for i in range(N):
    #A.append(list(map(int,input().split()))) 
d = dict()
'''
def bisection(a, n, p):
    #二分累乗法によるO(log p)計算
    bin_str = format(n, 'b')
    res = 1
    tmp = a
    for i in range(1, len(bin_str)+1):
        if(bin_str[(-1)*i] == '1'):
            res = res * tmp % p
        tmp = tmp * tmp % p
    return res
'''
d['a'] = 0
d['b'] = 0
d['c'] = 0

for i in range(N):
    #l = list(map(int,input().split()))
    #l = A[i]
    a,b=map(int,input().split())
    #if(l[0] == 0):
    if(a == 0):
        #if(l[1] == 0):
        if(b == 0):
            d['c'] += 1
        else:
            d['b'] += 1
    #elif(l[1] == 0):
    elif(b == 0):
        d['a'] += 1
    else:
        #g = math.gcd(l[0], l[1])
        g = math.gcd(a, b)
        #a = int(l[0]/g)
        #b = int(l[1]/g)
        a = a//g
        b = b//g
        if(a<0):
            p = (-1*a, -1*b)
        else:
            p = (a, b)
        if p in d:
            d[p] += 1
        else:
            d[p] = 1
    #print('i:{}, l[0]:{}, l[1]:{}, d:{}'.format(i, l[0], l[1], d))

#res = 1
a = d.pop('a')
b = d.pop('b')
#あとで二分累乗法に変換する4 
#if(a > 0 and b > 0):
    #a, b>=0 より、a+b>=0, よってa==0 and b == 0でなければ、a >0 or b> 0
    #ma = bisection(2, a, MOD)
    #mb = bisection(2, b, MOD)
    #res *= ma + mb -1
res = pow(2, a, MOD) + pow(2, b, MOD) - 1
res %= MOD

#elif(a == 0 and b > 0):
    #mb = bisection(2, b, MOD)
    #res *= mb
    #res %= MOD
#elif(a > 0 and b == 0):
    #ma = bisection(2, a, MOD)
    #res *= ma
    #res %= MOD
c = d.pop('c')

#print('a:{}, b:{}, c:{}'.format(a,b,c))
#print('d:{}, len(d):{}'.format(d, len(d)))
#print('res', res)

while len(d) > 0:
    s, v = d.popitem()
    if(s[1] < 0):
        opposite = (-1*s[1], s[0])
    else:
        opposite = (s[1], -1*s[0])
    if opposite in d:
        t = d.pop(opposite)
        #print('s:{}, v:{}, opposite:{}, t:{}, d:{}, len(d):{}'.format(s, v, opposite, t, d, len(d)))
        #mv = bisection(2, v, MOD)
        #mt = bisection(2, t, MOD)        
        #res *= mv + mt - 1
        res *= pow(2, v, MOD) + pow(2, t, MOD) - 1
        res %= MOD
    else:
        #print('s:{}, v:{}, opposite:{},       d:{}, len(d):{}'.format(s, v, opposite, d, len(d)))
        #mv = bisection(2, v, MOD)        
        #res *= mv
        res *= pow(2, v, MOD)
        res %= MOD
    #print('res', res)


res += c
res = (res + MOD - 1) % MOD

print(res)

Submission status: Accepted

Solution code:
from math import gcd
n=int(input())
mod=10**9+7
d1=dict()
d2=dict()
zero=0
zeroa=0
zerob=0
for _ in range(n):
    a,b=map(int,input().split())
    if a==0 and b==0:
        zero+=1
    elif a==0 and b!=0:
        zeroa+=1
    elif a!=0 and b==0:
        zerob+=1
    else:
        g=gcd(abs(a),abs(b))
        na=a//g
        nb=b//g
        if na<0:
            na=-na
            nb=-nb
        if (na,nb) not in d1 and (na,nb) not in d2:
            d1[(na,nb)]=1
            d2[(-nb,na)]=0
            d2[(nb,-na)]=0
        elif (na,nb) in d1:
            d1[(na,nb)]+=1
        else:
            d2[(na,nb)]+=1
#print(d1)
#print(d2)
d1=list(d1.items())
ans=pow(2,zeroa,mod)+pow(2,zerob,mod)-1
ans%=mod
for (a,b),cnt1 in d1:
  cnt2=0
  cnt2+=d2[(-b,a)]
  cnt2+=d2[(b,-a)]
  ans*=pow(2,cnt1,mod)+pow(2,cnt2,mod)-1
  ans%=mod
ans+=zero
ans=(ans+mod-1)%mod
print(ans)
#print(zeroa,zerob)

Submission status: Accepted

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


def select_num(a, b, mod=1000000007):
    sum = pow(2, a, mod) + pow(2, b, mod) - 1
    return sum % mod


def dict_count(d, a, b):
    this = a / b
    pair = b / a
    if not d.get(this, False):
        d[this] = {"num": 0, "pair": pair}
    d[this]["num"] += 1


def main():
    MOD = 1000000007
    n = int(input())

    d = defaultdict(lambda: [0] * 2)
    zero = 0
    for i in range(n):
        a, b = map(int, input().split())
        if a == 0 or b == 0:
            if a == b == 0:
                n -= 1
                zero += 1
            elif a == 0:
                d[0][True] += 1
            elif b == 0:
                d[0][False] += 1

        else:
            gcd = math.gcd(a, b)
            a //= gcd
            b //= gcd

            if b < 0:
                a, b = -a, -b

            rot = False
            if a < 0:
                b, a = -a, b
                rot = True
            d[(a, b)][rot] += 1

    ans = 1
    for k, v in d.items():
        ans *= select_num(v[0], v[1], MOD)
        ans %= MOD

    ans += zero - 1
    ans %= MOD
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import defaultdict
from math import gcd

MOD=10**9+7

n=int(input())
L=[]
for i in range(n):
	l=list(map(int,input().split()))
	L.append(l)

def kikaku(a,b):
	g=gcd(a,b)
	a//=g
	b//=g
	if a<0:
		return -a,-b
	return a,b
#aもbも正の場合Dposでカウント。
Dpos=defaultdict(int)
#aが正bが負の場合Dnegでカウント。
Dneg=defaultdict(int)

zerozero=0
azero=0
bzero=0

for l in L:
	a=l[0]
	b=l[1]
	if a==b==0:
		zerozero+=1
		continue
	if a==0:
		azero+=1
		continue
	if b==0:
		bzero+=1
		continue
	a,b=kikaku(a,b)
	if b>0:
		Dpos[(a,b)]+=1
	else:
		Dneg[(a,-b)]+=1
		Dpos[(-b,a)]+=0

r=1
for k,v in Dpos.items():
	a,b=k
	j=Dneg[(b,a)]
	r*=pow(2,v,MOD)+pow(2,j,MOD)-1
	#print(a,b,v,j,r)
	r%=MOD

r*=pow(2,azero,MOD)+pow(2,bzero,MOD)-1
r%=MOD
r-=1
r%=MOD

ans=r+zerozero
ans%=MOD
print(ans)
#print(Dpos)
#print(Dneg)

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

import sys
sys.setrecursionlimit(10**7)
from pprint import pprint as pp
from pprint import pformat as pf
# @pysnooper.snoop()
#import pysnooper # debug

import math
#from sortedcontainers import SortedList, SortedDict, SortedSet # no in atcoder
import bisect
from fractions import Fraction
from collections import defaultdict

def is_same_sign(a, b):
    if a > 0 and b > 0:
        return True
    if a < 0 and b < 0:
        return True
    return False

def fraction_taple(a, b):
    g = math.gcd(a, b)
    if is_same_sign(a, b):
        s = 1
    else:
        s = -1
    a = abs(a) // g
    b = abs(b) // g
    return (s, a, b)

def mode(a, b):
    # retrun dict_key, arr_key
    if a == 0 and b == 0:
        return 0, 0
    if a == 0:
        return 'ab', 0
    if b == 0:
        return 'ab', 1
    x = fraction_taple(a, b)
    y = fraction_taple(-1 * b, a)
    if x > y:
        return x, 0
    else:
        return y, 1

MOD = 1000000007

if __name__ == '__main__':

    n = int(input())

    d = defaultdict(lambda: [0, 0])
    zero = 0
    for _ in range(n):
        a, b = list(map(int, input().split()))
        dkey, akey = mode(a, b)
        if dkey == 0:
            zero += 1
        else:
            d[dkey][akey] += 1
    #print('d') # debug
    #pp(d) # debug

    ans = 1
    for pair in d.values():
        tmp = pow(2, pair[0], MOD) - 1 + pow(2, pair[1], MOD) - 1 + 1
        ans *= tmp
    ans += zero - 1
    ans %= MOD
    #print('ans') # debug
    print(ans)

    #print('\33[32m' + 'end' + '\033[0m') # debug

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
#E

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

"""
[本番中]
全体から引くことを考えていたが, 考えることが多く解けなかった

[解説AC]
Ai=0かつBi=0は他の全てと仲が悪いので, 単体で用いるしかない(最後に足す)

Ai*Aj + Bi*Bj = 0の式から内積が思い浮かぶ
仲が悪いペアはAi*Bi >= 0 と Aj*Bj <= 0の場合しかないことがわかる
X: Ai*Bi > 0の場合の(|Ai|, |Bi|)の数
y: Ai*Bi < 0の場合の(|Bi|, |Ai|)の数とすると, 
xとyで同じ(A, B)のペアがあると仲が悪い可能性がある
この場合, 以下の3通りのみ使用できる
xのみで使用(少なくとも1つ) or yのみで使用(少なくとも1つ) or xもyも使用しない
つまり, 2**x[(A, B)] - 1 + 2**y[(A, B)] -1 + 1 = 2**x[(A, B)] + 2**y[(A, B)] - 1
これらの積をとり, 最後に全て使用しなかった場合の1を引いた値が答え(最後に(A,B)=(0,0)を足す必要がある)
"""

n = I()
ab = [LI() for _ in range(n)]

x = defaultdict(lambda : 0)
y = defaultdict(lambda : 0)
z = defaultdict(lambda : 0)
tmp = 0
for a, b in ab:
    if a == 0 and b == 0:
        tmp += 1
    elif a == 0:
        x[0] += 1
        z[0] = 1
    elif b == 0:
        y[0] += 1
        z[0] = 1
    else:
        if a * b > 0:
            g = math.gcd(a, b)
            a //= g
            b //= g
            x[(abs(a), abs(b))] += 1
            z[(abs(a), abs(b))] = 1
        else:
            g = math.gcd(a, b)
            a //= g
            b //= g
            y[(abs(b), abs(a))] += 1
            z[(abs(b), abs(a))] = 1

ans = 1
for i in z.keys():
    ans *= (2**x[i] + 2**y[i] - 1)
    ans %= mod
ans -= 1
ans += tmp
ans %= mod
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
#E

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

def comb(n, r):
    return fact[n]*pow(fact[n-r], mod-2, mod)*pow(fact[r], mod-2, mod) % mod
n = I()
ab = [LI() for _ in range(n)]

fact = [1]*(n+1)
for i in range(1, n+1):
    fact[i] = i * fact[i-1]
    fact[i] %= mod

x = defaultdict(lambda : 0)
y = defaultdict(lambda : 0)
z = defaultdict(lambda : 0)
tmp = 0
for a, b in ab:
    if a == 0 and b == 0:
        tmp += 1
    elif a == 0:
        x[0] += 1
        z[0] = 1
    elif b == 0:
        y[0] += 1
        z[0] = 1
    else:
        if a * b > 0:
            g = math.gcd(a, b)
            a //= g
            b //= g
            x[(abs(a), abs(b))] += 1
            z[(abs(a), abs(b))] = 1
        else:
            g = math.gcd(a, b)
            a //= g
            b //= g
            y[(abs(b), abs(a))] += 1
            z[(abs(b), abs(a))] = 1

ans = 1
for i in z.keys():
    ans *= (2**x[i] + 2**y[i] - 1)
    ans %= mod
ans -= 1
ans += tmp
ans %= mod
print(ans)

Submission status: Accepted

Solution code:
# 約分して、互いに素な(1,3) (3,1)のようなペアを作りカウントする
# 正のグループと負のグループを別々に管理
# 正のグループの相手が負のグループに存在した場合、
# どちらかのグループから好きなだけ選ぶか、どちらも選ばないかしかない
# 誰ともペアにならなかったグループの個数を全て足してP個だとして、2^P通りを掛ける
# (0,0)については、その中から1つ選ぶか、選ばないかしかない

import sys
readline = sys.stdin.readline

N = int(readline())
import math

zeropair = 0
zeroa = 0
zerob = 0
from collections import defaultdict
pluspair = defaultdict(int)
minuspair = defaultdict(int)
for i in range(N):
  a,b = map(int,readline().split())
  if a == 0 and b == 0:
    zeropair += 1
    continue
  if a == 0:
    zeroa += 1
    continue
  if b == 0:
    zerob += 1
    continue
  absa = abs(a)
  absb = abs(b)
  g = math.gcd(absa,absb)
  absa,absb = absa//g,absb//g
  if a * b > 0:
    pluspair[(absa,absb)] += 1
  else:
    minuspair[(absa,absb)] += 1

DIV = 1000000007
ans = 1
# zeroa,zerobから選ぶパターンは、どちらから好きなだけ選ぶか、どちらも選ばないか
ans *= (pow(2,zeroa,DIV) + pow(2,zerob,DIV) - 1) % DIV
ans %= DIV

# 誰とでもペアになれるものをカウント
allcnt = 0

# plusから選ぶパターンで、minusにある対応ペアを探す
for item in pluspair.items():
  a,b = item[0]
  cnt = item[1]
  if (b,a) in minuspair:
    ans *= (pow(2,cnt,DIV) + pow(2,minuspair[(b,a)]) - 1) % DIV
    ans %= DIV
    del minuspair[(b,a)]
  else:
    allcnt += cnt

for val in minuspair.values():
  allcnt += val

ans = (ans * pow(2,allcnt,DIV)) % DIV
# zeropairから選んだ場合、今までのパターンとは独立
ans += zeropair
print((ans - 1) % DIV)

Submission status: Accepted

Solution code:
import sys
import collections
import fractions
import math
def input():
    return sys.stdin.readline()[:-1]
n=int(input())
zero = 0
dic = {}
mod = 10**9+7
for i in range(n):
    a,b = map(int,input().split())
    rt =0
    if a==0 and b==0:
        zero+=1
        continue
    g = math.gcd(a,b)
    a = a//g
    b = b//g
    if b<0:
        a=-a
        b=-b
    if a<0 and b==0:
        a=-a
        b=-b
    if a<=0:
        rt=1
        a,b = b,-a

    if (a,b) not in dic:
        if rt==0:
            dic[(a,b)] = [1,0]
        else:
            dic[(a,b)] = [0,1]
    else:
        if rt==0:
            dic[(a,b)][0] += 1
        else:
            dic[(a,b)][1] += 1

ans = 1
for i,j in dic.values():
    tmp = pow(2,i,mod) - 1
    tmp2 = pow(2,j,mod) - 1
    su = (tmp+tmp2+1)%mod
    ans = (ans*su)%mod

ans = (ans-1+zero)%mod

print(ans)

Submission status: Accepted

Solution code:
import sys, bisect, collections, math
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = 10**20
MOD = 1000000007
def I(): return int(input())
def F(): return float(input())
def S(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LS(): return input().split()

def resolve():
    N = I()
    AB = [LI() for _ in range(N)]

    # A, Bを標準化 互いに疎でAは正
    def normalize(AB):
        A = AB[0]
        B = AB[1]
        if A==B==0:
            return (0, 0)
        elif A==0:
            return(0, 1)
        elif B==0:
            return(1, 0)
        else:
            gcd = math.gcd(A, B)
            A //= gcd
            B //= gcd
            if A<0:
                A, B = -A, -B
            return (A, B)
    
    def orthogonal(AB):
        A = AB[0]
        B = AB[1]
        if B>0:
            return (B, -A)
        else:
            return(-B, A)

    AB_n = [normalize(i) for i in AB]
    counter = collections.Counter(AB_n)

    # 場合の数を求める
    used = set()
    ans = 1
    # (0, 0)以外について
    for A, B in AB_n:
        if not (A, B) in used:
            if (A, B)!=(0, 0):
                ans *= pow(2, counter[(A, B)], MOD) + pow(2, counter[orthogonal((A, B))], MOD) - 1
                ans %= MOD
                used.add((A, B))
                used.add(orthogonal((A, B)))
    ans -= 1
    # (0, 0)について
    ans += counter[(0, 0)]
    ans %= MOD

    print(ans)

if __name__ == '__main__':
    resolve()

Submission status: Accepted

Solution code:
from math import gcd

n = int(input())
MOD = 10**9 + 7
cnt = {}
zero_cnt = 0
ans = 1

for i in range(n):
    a, b = map(int, input().split())
    if (a,b) == (0,0):
        zero_cnt += 1
        continue
    g = gcd(abs(a), abs(b))
    a //= g
    b //= g
    rotate = 0
    while not (a >= 0 and b > 0):
        a,b = -b,a
        rotate += 1
    if (a,b) not in cnt:
        cnt[(a,b)] = [0,0]
    cnt[(a,b)][rotate % 2] += 1
 
for key in cnt:
    A, B = cnt[key]
    ans *= 1 + pow(2, A, MOD) - 1 + pow(2, B, MOD) - 1
    ans %= MOD
 
ans += zero_cnt
ans -= 1
print(ans % MOD)

Submission status: Accepted

Solution code:
from math import gcd

mod = 10**9 +7
N = int(input())
dic = {}

zero = 0
for _ in range(N):
    a,b = map(int, input().split())
    if  a ==0 and b == 0:
        zero += 1
        continue
    elif a == 0:
        key = (0,1)
    elif b == 0:
        key = (1,0)
    else:
        if a<0:
            a=-a 
            b=-b
        g = gcd(a,abs(b))
        key = (a//g,b//g)
    
    if key not in dic:
        dic[key]=0

    dic[key] +=1

ans = 1
for k1, v1 in dic.items():
    if v1 ==0:
        continue

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

    if k2 not in dic:
        ans *= 2**v1
        ans %= mod
    else:
        ans *= ((2**v1-1) %mod) + ((2**dic[k2]-1) %mod) +1
        ans %= mod
        dic[k2]=0

ans = (ans + zero -1 )%mod
print(ans)

Submission status: Accepted

Solution code:
import collections

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

mod=10**9+7
n=int(input())
dic=collections.defaultdict(int)
cnt=0
for _ in range(n):
  a,b=map(int,input().split())
  if a!=0 and b!=0:
    g=gcd(abs(a),abs(b))
    if a*b>0:
      dic[(abs(a)//g,abs(b)//g)]+=1
    else:
      dic[(-abs(a)//g,abs(b)//g)]+=1
  else:
    if a==0 and b==0:
      cnt+=1
    elif a==0:
      dic[(0,1)]+=1
    elif b==0:
      dic[(1,0)]+=1
ans=1
s=set()
for a,b in dic.keys():
  if (a,b) in s:
    continue
  s.add((a,b))
  if a>0:
    s.add((-b,a))
    cnt1=dic[(a,b)]
    if (-b,a) in dic:
      cnt2=dic[(-b,a)]
    else:
      cnt2=0
    ans*=(pow(2,cnt1,mod)+pow(2,cnt2,mod)-1)%mod
    ans%=mod
  else:
    s.add((b,-a))
    cnt1=dic[(a,b)]
    if (b,-a) in dic:
      cnt2=dic[(b,-a)]
    else:
      cnt2=0
    ans*=(pow(2,cnt1,mod)+pow(2,cnt2,mod)-1)%mod
    ans%=mod
print((ans+cnt-1)%mod)

Submission status: Accepted

Solution code:
import collections

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

mod=10**9+7
n=int(input())
dic=collections.defaultdict(int)
cnt=0
for _ in range(n):
  a,b=map(int,input().split())
  if a!=0 and b!=0:
    g=gcd(abs(a),abs(b))
    if a*b>0:
      dic[(abs(a)//g,abs(b)//g)]+=1
    else:
      dic[(-abs(a)//g,abs(b)//g)]+=1
  else:
    if a==0 and b==0:
      cnt+=1
    elif a==0:
      dic[(0,1)]+=1
    elif b==0:
      dic[(1,0)]+=1
ans=1
s=set()
for a,b in dic.keys():
  if (a,b) in s:
    continue
  s.add((a,b))
  if a!=0 and b!=0:
    if a>0:
      s.add((-b,a))
      cnt1=dic[(a,b)]
      if (-b,a) in dic:
        cnt2=dic[(-b,a)]
      else:
        cnt2=0
      ans*=(pow(2,cnt1,mod)+pow(2,cnt2,mod)-1)%mod
      ans%=mod
    elif a<0:
      s.add((b,-a))
      cnt1=dic[(a,b)]
      if (b,-a) in dic:
        cnt2=dic[(b,-a)]
      else:
        cnt2=0
      ans*=(pow(2,cnt1,mod)+pow(2,cnt2,mod)-1)%mod
      ans%=mod
  else:
    s.add((b,a))
    cnt1=dic[(a,b)]
    if (b,a) in dic:
      cnt2=dic[(b,a)]
    else:
      cnt2=0
    ans*=(pow(2,cnt1,mod)+pow(2,cnt2,mod)-1)%mod
    ans%=mod
print((ans+cnt-1)%mod)

Submission status: Accepted

Solution code:
from math import gcd
 
N = int(input())
mod = 10 ** 9 + 7 # 1000000007
 
d = dict()
zeros = 0
for _ in range(N):
  a, b = map(int, input().split()) # Ai, Bi
  # どちらか一方でも0であれば特殊なケースとなる
  # 下記のd[p]でd[(0, 0)]のような形になるため分ける(zeros)
  # d[(0, 0)]同士では組み合わせが作れないため、単純に+1していく
  if not any((a,b)):
    zeros += 1
    continue
  if all((a, b)):
    g = gcd(a, b) * (a//abs(a)) # //は切り捨て除算
  elif a:
    g = a
  else:
    g = b
  p = a//g, b//g # p is (tuple)
  d[p] = d.get(p, 0) + 1 # count

ans = 1 # 掛け算するため0ではなく1としておき、最後の出力時に1を引くようにする
done = set()
for (a,b), val in d.items():
  if (-b, a) in done or (b, -a) in done: # if already counted, then continue
    continue
  done.add((a, b))
  w = d.get((-b, a), 0) + d.get((b, -a), 0)
  # (a, b)とそれに垂直な(-b, a), (b, -a)のそれぞれの組み合わせを足す
  # そして何も選ばなかったときの場合を引くため、最後に-1とする
  ans *= (pow(2, val) + pow(2, w) -1)
  ans %= mod

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

Submission status: Accepted

Solution code:
from math import gcd

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

d=dict()
zeros=0
for _ in range(n):
  a,b=map(int,input().split())
  if not any((a,b)):
    zeros+=1
    continue
  if all((a,b)):
    g=gcd(a,b)*(a//abs(a))
  elif a:
    g = a
  else:
    g = b
  p=a//g,b//g
  d[p]=d.get(p,0)+1

ans=1
done=set()
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)
  ans *=(pow(2,v)+pow(2,w)-1)
  ans %= mod
print((ans+zeros-1)%mod)

Submission status: Accepted

Solution code:
from math import gcd
mod = 1000000007
n = int(input())
zero = 0
bad = {} # 仲が悪い者同士をグループ化
for i in range(n):
    x, y = map(int, input().split())
    if x == 0 and y == 0:
        zero += 1 # (A,B) = (0,0) の計数をとる
        continue
    g = gcd(x, y)
    x //= g # ベクトルを整数の範囲で最小化し、
    y //= g # 傾きを既約分数 (y'/x') の形にする
    # ベクトルを0≦θ＜πの範囲に変換する
    if y < 0: x, y = -x, -y # 第3~4象限のベクトルはπ回転
    if y==0 and x<0: x, y = -x, -y # θ=πのベクトルはθ=0へ
    # π/2≦θ＜πは、π/2回転して同じキーにする
    is_rotate90 = (x <= 0)
    if is_rotate90: x, y = y, -x # π/2回転
    if not (x, y) in bad: bad[x, y] = [0, 0]
    # π/2回転したもの、してないものは別に計数をとる
    bad[x, y][is_rotate90] += 1

ans = 1 # 組み合わせを掛けていくので 1 から
for x, y in bad:
    c1, c2 = bad[x, y]
    # c1, c2 両方選択は仲が悪いのでできない
    # c1 の側のみを 1 個以上選択する
    # c2 の側のみを 1 個以上選択する
    # c1, c2 どちらも選択しない
    c3 = (pow(2, c1, mod) - 1) + (pow(2, c2, mod) - 1) + 1
    ans *= c3
    ans %= mod

# (A,B)=(0,0)は、単独でしか選択できないので、+zero する
# 全て未選択はできないので、-1 する
ans += zero - 1
ans = (ans + mod) % mod # 負数対応
print(ans)

Submission status: Accepted

Solution code:
from math import gcd
mod = 1000000007
n = int(input())
zero = 0
bad = {}
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: x, y = -x, -y
    if y==0 and x<0: x, y = -x, -y
    is_rotate90 = (x <= 0)
    if is_rotate90: x, y = y, -x
    if not (x, y) in bad: bad[x, y] = [0, 0]
    bad[x, y][is_rotate90] += 1

ans = 1
for x, y in bad:
    c1, c2 = bad[x, y]
    c3 = (pow(2, c1, mod) - 1) + (pow(2, c2, mod) - 1) + 1
    ans *= c3
    ans %= mod

ans += zero - 1
ans = (ans + mod) % mod
print(ans)

Submission status: Accepted

Solution code:
from math import gcd
mod = 1000000007
n = int(input())
zero = 0
bad = {}
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: x, y = -x, -y
    if y==0 and x<0: x, y = -x, -y
    is_rotate90 = (x <= 0)
    if is_rotate90:
        x, y = y, x
        y = -y
    if not (x, y) in bad:
        bad[x, y] = [0, 0]
    if is_rotate90:
        bad[x, y][0] += 1
    else:
        bad[x, y][1] += 1

# print(bad)

cnt = 1
for x, y in bad:
    c1, c2 = bad[x, y]
    c3 = 1
    c3 += pow(2, c1, mod) - 1
    c3 += pow(2, c2, mod) - 1
    cnt = cnt * c3 % mod

ans = (cnt + zero - 1) % mod

# print('cnt',cnt)
# print('zero',zero)
# print('ans',ans)
print((ans+mod) % mod)