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:
from fractions import gcd

N=int(input())
d={}
#l=[]
MOD = 1000000007
nz=0
for _ in range(N):
    a,b=map(int,input().split())
    if a==0 and b==0:
        nz+=1
        #p=(0,0)
        continue
    elif a==0:
        p=(0,1)
    elif b==0:
        p=(1,0)
    else:
        c=gcd(a,b)
        a,b=a//c,b//c
        if b > 0:
            p=(a,b)
        else: # b < 0
            p=(-a,-b)
    
    #l.append(p)
    if p in d:
        d[p]+=1
    else:
        d[p] = 1

ans=1
#for p in l:
while len(d) > 0:
    p,np=d.popitem()
    if p==(1,0):
        q=(0,1)
    elif p==(0,1):
        q=(1,0)
    else:
        pa,pb=p
        if pa > 0:
            q=(-pb,pa)
        else: #pa < 0
            q=(pb,-pa)
    if q in d:
        nq=d.pop(q)
    else:
        nq=0
    
    ans *= ((2**np + 2**nq - 1) % MOD)
    ans %= MOD

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

Submission status: Accepted

Solution code:
import math
 
n = int(input())
mod = 10 ** 9 + 7
 
ab = {}
for i in range(n):
    a, b = map(int, input().split())
    if a == 0 and b == 0:
        pass
    elif a == 0:
        b = 1
    else:
        gcd = math.gcd(a, b)
        a //= gcd
        b //= gcd
        if a < 0:
            a, b = -a, -b
    num = (a, b)
    ab.setdefault(num, 0)
    ab[num] += 1
ans = 0
if (0, 0) in ab.keys():
    temp2 = ab[(0, 0)]
    ans += temp2
    n -= temp2
s = set(ab.keys())
pairs = []
for i in ab.keys():
    if i == (0, 0):
        continue
    else:
        a, b = i[0], i[1]
        if (-b, a) in s:
            pairs.append([ab[(a, b)], ab[(-b, a)]])
temp3 = 1
for i in range(len(pairs)):
    num2 = pairs[i][0]
    num3 = pairs[i][1]
    temp3 *= (pow(2, num2, mod) + pow(2, num3, mod) - 1)
    n = n- num2 - num3
    temp3 %= mod
temp3 *= pow(2, n, mod)
temp3 -= 1
temp3 %= mod
ans += temp3
ans %= mod
print(ans)

Submission status: Accepted

Solution code:
import sys
from math import gcd
from collections import Counter
MOD = 10**9 + 7
def main():
    input = sys.stdin.readline
    N = int(input())
    V = []
    z = 0
    for _ in range(N):
        A, B = map(int, input().split())
        g = gcd(A, B)
        if g == 0:
            z += 1
            continue
        A, B = A // g, B // g
        if A == 0: V.append((0, 1))
        elif A < 0: V.append((-A, -B))
        else: V.append((A, B))
    C = Counter(V)
    ans = Mint(1)
    used = set()
    for k, V in C.items():
        if k in used: continue
        a, b = k
        v = (0, 1) if b == 0 else (b, -a) if b > 0 else (-b, a)
        t = Mint(1)
        t += pow(2, V, MOD) - 1
        t += pow(2, C[v], MOD) - 1
        ans *= t
        used.add(v)
    print(ans - 1 + z)

class Mint:
    def __init__(self, value=0):
        self.value = value % MOD
        if self.value < 0: self.value += MOD

    @staticmethod
    def get_value(x): return x.value if isinstance(x, Mint) else x

    def inverse(self):
        a, b = self.value, MOD
        u, v = 1, 0
        while b:
            t = a // b
            b, a = a - t * b, b
            v, u = u - t * v, v
        if u < 0: u += MOD
        return u

    def __repr__(self): return str(self.value)
    def __eq__(self, other): return self.value == other.value
    def __neg__(self): return Mint(-self.value)
    def __hash__(self): return hash(self.value)
    def __bool__(self): return self.value != 0

    def __iadd__(self, other):
        self.value = (self.value + Mint.get_value(other)) % MOD
        return self

    def __add__(self, other):
        new_obj = Mint(self.value)
        new_obj += other
        return new_obj
    __radd__ = __add__

    def __isub__(self, other):
        self.value = (self.value - Mint.get_value(other)) % MOD
        if self.value < 0: self.value += MOD
        return self

    def __sub__(self, other):
        new_obj = Mint(self.value)
        new_obj -= other
        return new_obj

    def __rsub__(self, other):
        new_obj = Mint(Mint.get_value(other))
        new_obj -= self
        return new_obj

    def __imul__(self, other):
        self.value = self.value * Mint.get_value(other) % MOD
        return self

    def __mul__(self, other):
        new_obj = Mint(self.value)
        new_obj *= other
        return new_obj
    __rmul__ = __mul__

    def __ifloordiv__(self, other):
        other = other if isinstance(other, Mint) else Mint(other)
        self *= other.inverse()
        return self

    def __floordiv__(self, other):
        new_obj = Mint(self.value)
        new_obj //= other
        return new_obj

    def __rfloordiv__(self, other):
        new_obj = Mint(Mint.get_value(other))
        new_obj //= self
        return new_obj


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6) #再帰関数の上限
import math
from copy import copy, deepcopy
from operator import itemgetter
from bisect import bisect_left, bisect, bisect_right#2分探索
#bisect_left(l,x), bisect(l,x)#aはソート済みである必要あり。aの中からx未満の要素数を返す。rightだと以下
from collections import deque 
#deque(l), pop(), append(x), popleft(), appendleft(x)
##listでqueの代用をするとO(N)の計算量がかかってしまうので注意
from collections import Counter#文字列を個数カウント辞書に、
#S=Counter(l),S.most_common(x),S.keys(),S.values(),S.items()
from itertools import accumulate#累積和
#list(accumulate(l))
from heapq import heapify,heappop,heappush
#heapify(q),heappush(q,a),heappop(q) #q=heapify(q)としないこと、返り値はNone
#import fractions#古いatcoderコンテストの場合GCDなどはここからimportする


def input(): return sys.stdin.readline()[:-1]
def printl(li): print(*li, sep="\n")
def argsort(s, return_sorted=False): 
    inds=sorted(range(len(s)), key=lambda k: s[k])
    if return_sorted: return inds, [s[i] for i in inds]
    return inds
def alp2num(c,cap=False): return ord(c)-97 if not cap else ord(c)-65
def num2alp(i,cap=False): return chr(i+97) if not cap else chr(i+65)

class modint():#add:和,mul:積,pow:累乗,div:商(modと互いに素であること)
    def __init__(self,x,mod=1000000007): self.x, self.mod=x, mod
    def add(self,a): self.x=(self.x+a%self.mod)%self.mod
    def mul(self,c): self.x=(self.x*(c%self.mod))%self.mod
    def pow(self,p): self.x=pow(self.x,p,self.mod)
    def div(self,d):
        u,v,a,b=1,0,d,self.mod
        while b:
            t=a//b
            a-=t*b
            a,b,u,v=b,a,v,u-t*v
        if a!=1: print("not 素")
        self.x=(self.x*(u%self.mod))%self.mod

def main():
    mod = 1000000007
    #w.sort(key=itemgetter(1),reversed=True)  #二個目の要素で降順並び替え

    N = int(input())
    #N, K = map(int, input().split())
    #A = tuple(map(int, input().split())) #1行ベクトル
    #L = tuple(int(input()) for i in range(N)) #改行ベクトル
    #S = tuple(tuple(map(int, input().split())) for i in range(N)) #改行行列

    d=dict()
    m=10**18+100
    for i in range(N):
        A, B = map(int, input().split())
        if A==0 and B==0:
            d[-m]=d.get(-m,0)+1
        elif B==0:
            d[m]=d.get(m,0)+1
        elif A==0:
            d[0]=d.get(0,0)+1
        else:
            sa=sb=1
            if A<0:
                sa=-1
                A*=-1
            if B<0:
                sb=-1
                B*=-1

            g=math.gcd(A,B)
            A=A//g
            B=B//g
            if sa==-1 and sb==-1:
                t=(A,B)
            elif sb==-1:
                t=(-A,B)
            else:
                t=(sa*A,sb*B)
            d[t]=d.get(t,0)+1
    
        
    #print(d)
    ks=set(d.keys())
    alis=[]
    tot=modint(1)
    for i, k in enumerate(ks):
        if d[k]==-1.0:
            continue
        if k==-m:
            continue
        if k==m:
            ik=0
        elif k==0:    
            ik=m
        elif k[0]<0:
            ik=(k[1],-k[0])
        else:
            ik=(-k[1],k[0])
        #print(ik)
        if ik in ks:
            d1,d2=d[k],d[ik]
            tot.mul((pow(2,d1,mod)-1)+(pow(2,d2,mod)-1)+1)
            d[ik]=-1

        else:
            tot.mul(pow(2,d[k],mod))

    tot.add(-1)
    tot.add(d.get(-m,0))
    
    print(tot.x)




if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from math import gcd

N = int(input())
AB = [map(int, input().split()) for _ in range(N)]

t = []
d = {}
d[0] = {}
d[0][0] = 0
for a, b in AB:
    i = gcd(a, b)
    if i != 0:
        a //= i
        b //= i
    t.append((a, b))
    d.setdefault(a, {})
    d[a].setdefault(b, 0)
    d[a][b] += 1
t = set(t)
if (0, 0) in t:
    t.remove((0, 0))

used = set()
result = 1
for a, b in t:
    if (a, b) in used:
        continue
    used.add((a, b))
    i = d[a][b]
    j, k, l = 0, 0, 0
    if -a in d and -b in d[-a]:
        j = d[-a][-b]
        used.add((-a, -b))
    if -b in d and a in d[-b]:
        k = d[-b][a]
        used.add((-b, a))
    if b in d and -a in d[b]:
        l = d[b][-a]
        used.add((b, -a))
    result *= pow(2, i + j, 1000000007) + pow(2, k + l, 1000000007) - 1
    result %= 1000000007
result += d[0][0] - 1
result %= 1000000007
print(result)

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, gcd, atan2
from itertools import accumulate, permutations, combinations, product, groupby, combinations_with_replacement
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N = INT()
AB = [LIST() for _ in range(N)]

zero = 0
tmp = []
dic = defaultdict(lambda: [0, 0])

for x, y in AB:
	if x == 0 and y == 0:
		zero += 1
	else:
		g = gcd(x, y)
		x //= g
		y //= g
		if y < 0: x *= -1; y *= -1
		if y == 0 and x < 0: x *= -1; y *= -1

		rot90 = (x <= 0)
		if rot90:
			x, y = y, -x
		if rot90:
			dic[(x, y)][0] += 1
		else:
			dic[(x, y)][1] += 1

ans = 1
for l in dic.values():
	ans *= (pow(2, l[0], mod)-1 + pow(2, l[1], mod)-1 + 1)
	ans %= mod

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

Submission status: Accepted

Solution code:
import math


n = int(input())
mod = 1000000007
ab = [list(map(int,input().split())) for _ in range(n)]
dic = {}
z = 0
nz,zn = 0,0
for a,b in ab:
    if a == 0 and b == 0:
        z += 1
        continue
    elif a == 0:
        zn += 1
        continue
    elif b == 0:
        nz += 1
    if a< 0:
        a = -a
        b = -b
    g = math.gcd(a,b)
    tp = (a//g,b//g)
    if tp not in dic:
        dic[tp] = 1
    else:
        dic[tp] += 1
    
ans = 1
nn = n - z - zn - nz
for tp,v in dic.items():
    if v == 0:
        continue
    vt = (tp[1],-1*tp[0])
    if vt in dic:
        w = dic[vt]
        #print(tp)
        e = pow(2,v,mod) + pow(2,w,mod) - 1
        ans *= e
        ans %= mod
        nn -= v + w 
        dic[tp] = 0
        dic[vt] = 0
ans *= pow(2,nn,mod)
if zn == 0:
    ans *= pow(2,nz,mod)
elif nz == 0:
    ans *= pow(2,zn,mod)
else:
    ans *= pow(2,nz,mod) + pow(2,zn,mod) - 1
ans += z - 1
print(ans%mod)
#print(dic)

Submission status: Accepted

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

mod = 10 ** 9 + 7

n = int(input())
ab = [list(map(int, input().split())) for _ in range(n)]

d = {}
z = 0

pow_2 = [1]

for i in range(n):
    pow_2.append(pow_2[-1] * 2 % mod)

for a, b in ab:
    if a == 0 and b == 0:
        z += 1
        continue

    if a == 0 and b != 0:
        key = (0, 1)
    elif a * b > 0:
        g = gcd(a, b)
        key = (abs(a // g), abs(b // g))
    else:
        continue

    if key not in d:
        d[key] = [0, 0]
    d[key][0] += 1

for a, b in ab:
    if a != 0 and b == 0:
        key = (0, 1)
    elif a * b < 0:
        g = gcd(a, b)
        key = (abs(b // g), abs(a // g))
    else:
        continue
    
    if key in d:
        d[key][1] += 1


lo = n - z

ans = 1

for x, xi in d.values():
    if x * xi > 0:
        ans *= ((pow_2[x] - 1) + (pow_2[xi] - 1) + 1)
        ans %= mod
        lo -= x + xi

ans = (ans * pow_2[lo] + z - 1) % mod   

print(ans)

Submission status: Accepted

Solution code:
from math import gcd

n = int(input())
ab = [map(int, input().split()) for _ in range(n)]
mod = 1000000007

pair = []
d = {}
d[0] = {}
d[0][0] = 0

for a, b in ab:
   x = gcd(a, b)
   if x != 0:
      a //= x
      b //= x
   pair.append((a, b))

   d.setdefault(a, {})
   d[a].setdefault(b, 0)
   d[a][b] += 1
used = set()
ans = 1
for a, b in pair:
   if (a, b) in used:
      continue
   used.add((a, b))

   if a == 0 and b == 0:
      continue

   i = d[a][b]
   j, k, l = 0, 0, 0
   if -a in d and -b in d[-a]:
      j = d[-a][-b]
      used.add((-a, -b))
   if -b in d and a in d[-b]:
      k = d[-b][a]
      used.add((-b, a))
   if b in d and -a in d[b]:
      l = d[b][-a]
      used.add((b, -a))

   ans *= pow(2, i+j, mod) + pow(2, k+l, mod) - 1
   ans %= mod

ans += d[0][0] - 1
ans %= mod
print(ans)

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict
from math import gcd
def input(): return sys.stdin.readline().strip()
mod = 1000000007

def main():
    N = int(input())
    fish = defaultdict(int)

    """
    b / aで値を管理するのは浮動小数点誤差が怖いので、
    g = gcd(a, b) として(a//g, b//g)のタプルで管理するのが良い。
    """

    zero = 0
    for _ in range(N):
        a, b = map(int, input().split())
        if a == 0 and b == 0: zero += 1
        elif a == 0: fish[(0, 1)] += 1
        elif b == 0: fish[(1, 0)] += 1
        else:
            g = gcd(a, b)
            if a < 0: a, b = -a, -b
            fish[(a // g, b // g)] += 1
    #print(fish)
    
    """
    仲の悪い組を(S1, T1), (S2, T2),...とすれば(Si, Ti)からの魚の選び方と
    (Sj, Tj)からの魚の選び方は独立じゃん。
    なぜ気づかなかったのか。。。
    """
    
    ans = 1
    finished = set([])
    for a, b in fish:
        if (a, b) in finished: continue
        finished.add((a, b))
        s = fish[(a, b)]
        if b > 0:
            t = fish[(b, -a)] if (b, -a) in fish else 0
            finished.add((b, -a))
        else:
            t = fish[(-b, a)] if (-b, a) in fish else 0
            finished.add((-b, a))
        ans *= pow(2, s, mod) + pow(2, t, mod) - 1
        ans %= mod
        #print("(a, b)=({}, {}) -> s={}, t={}, val={}".format(a, b, s, t, pow(2, s, mod) + pow(2, t, mod) - 1))
    print((ans + zero - 1) % mod)



if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# E - ∙ (Bullet)
import sys
from collections import defaultdict
from math import gcd

readline = sys.stdin.readline
MOD = 1000000007
N = int(readline())

# イワシの傾きをA/Bとする。
# A/Bは予めgcdで割って約分し、同じ傾きのものを揃えておく。
# このとき、仲の悪い組合せは(A, B)に対して(B, -A)となるもの。 
# 前者をS、後者をTとして考える。
d_S = defaultdict(int)
d_T = defaultdict(int)

'''
def gcd(x, y):
    if x == 0:
        return y
    else:
        return gcd(y%x, x)
'''

pow2_mod = [1] + [0] * (N + 10)
for i in range(1, N + 10):
    pow2_mod[i] = pow2_mod[i-1] * 2 % MOD

zeros = 0
for i in range(N):
    A, B = map(int, readline().split())
    # (0, 0)のイワシは他の全てのイワシと仲が悪いため、
    # 1匹のみでしか選ぶことができない。最後にこの数を足す。
    if A == 0 and B == 0:
        zeros += 1
    # (?, 0),(0, ?)のイワシは、?がどのような数字であろうとも
    # この組合せであれば仲が悪い。一律、(1,0)(0,-1)として考える。
    elif A == 0:
        d_S[(1, 0)] += 0
        d_T[(0, -1)] += 1
    elif B == 0:
        d_S[(1, 0)] += 1
        #d_T[(0, -1)] += 0
    else:
        g = gcd(A, B)
        A //= g
        B //= g
        if A < 0:
            A *= -1
            B *= -1
        if A * B > 0:
            d_S[(A, B)] += 1
            #d_T[(B, -A)] += 0
        else:
            d_S[(-B, A)] += 0
            d_T[(A, B)] += 1

ans = 1
for (si, sj), s_cnt in d_S.items():
    t_cnt = d_T[(sj, -1*si)]
    tmp = 0
    tmp += pow2_mod[s_cnt] - 1 # Sから1匹以上選ぶ組合せ
    tmp += pow2_mod[t_cnt] - 1 # Tから1匹以上選ぶ組合せ
    tmp += 1 # どちらも選ばない組合せ
    ans = (ans * tmp)%MOD

ans -= 1 # 最終的に1匹も選ばない組合せ
ans += zeros # (0, 0)のイワシの数

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

Submission status: Accepted

Solution code:
# E - ∙ (Bullet)
import sys
from collections import defaultdict

readline = sys.stdin.readline
MOD = 1000000007
N = int(readline())

# イワシの傾きをA/Bとする。
# A/Bは予めgcdで割って約分し、同じ傾きのものを揃えておく。
# このとき、仲の悪い組合せは(A, B)に対して(B, -A)となるもの。 
# 前者をS、後者をTとして考える。
d_S = defaultdict(int)
d_T = defaultdict(int)

def gcd(x, y):
    if x == 0:
        return y
    else:
        return gcd(y%x, x)

pow2_mod = [1] + [0] * (N + 10)
for i in range(1, N + 10):
    pow2_mod[i] = pow2_mod[i-1] * 2 % MOD

zeros = 0
for i in range(N):
    A, B = map(int, readline().split())
    # (0, 0)のイワシは他の全てのイワシと仲が悪いため、
    # 1匹のみでしか選ぶことができない。最後にこの数を足す。
    if A == 0 and B == 0:
        zeros += 1
    # (?, 0),(0, ?)のイワシは、?がどのような数字であろうとも
    # この組合せであれば仲が悪い。一律、(1,0)(0,-1)として考える。
    elif A == 0:
        d_S[(1, 0)] += 0
        d_T[(0, -1)] += 1
    elif B == 0:
        d_S[(1, 0)] += 1
        #d_T[(0, -1)] += 0
    else:
        g = gcd(A, B)
        A //= g
        B //= g
        # いずれもマイナスの場合、傾きはプラスになる
        if A < 0 and B < 0:
            A *= -1
            B *= -1
        if A * B > 0:
            d_S[(A, B)] += 1
            #d_T[(B, -A)] += 0
        # 片方がマイナスの場合、必ずAがマイナスになるよう揃える
        else:
            if A > B:
                A, B = B, A
            d_S[(-A, B)] += 0
            d_T[(B, A)] += 1

ans = 1
for (si, sj), s_cnt in d_S.items():
    t_cnt = d_T[(sj, -1*si)]
    tmp = 0
    tmp += pow2_mod[s_cnt] - 1 # Sから1匹以上選ぶ組合せ
    tmp += pow2_mod[t_cnt] - 1 # Tから1匹以上選ぶ組合せ
    tmp += 1 # どちらも選ばない組合せ
    ans = (ans * tmp)%MOD

ans -= 1 # 最終的に1匹も選ばない組合せ
ans += zeros # (0, 0)のイワシの数

print(ans%MOD)

Submission status: Accepted

Solution code:
# E - ∙ (Bullet)
import sys
from collections import defaultdict

readline = sys.stdin.readline
MOD = 1000000007
N = int(readline())

# イワシの傾きをA/Bとする。
# A/Bは予めgcdで割って約分し、同じ傾きのものを揃えておく。
# このとき、仲の悪い組合せは(A, B)に対して(B, -A)となるもの。 
# 前者をS、後者をTとして考える。
d_S = defaultdict(int)
d_T = defaultdict(int)

def gcd(x, y):
    if x == 0:
        return y
    else:
        return gcd(y%x, x)

pow2_mod = [1] + [0] * (N * 2)
for i in range(1, N * 2):
    pow2_mod[i] = pow2_mod[i-1] * 2 % MOD

zeros = 0
for i in range(N):
    A, B = map(int, readline().split())
    # (0, 0)のイワシは他の全てのイワシと仲が悪いため、
    # 1匹のみでしか選ぶことができない。最後にこの数を足す。
    if A == 0 and B == 0:
        zeros += 1
    # (?, 0),(0, ?)のイワシは、?がどのような数字であろうとも
    # この組合せであれば仲が悪い。一律、(1,0)(0,-1)として考える。
    elif A == 0:
        d_S[(1, 0)] += 0
        d_T[(0, -1)] += 1
    elif B == 0:
        d_S[(1, 0)] += 1
        d_T[(0, -1)] += 0
    else:
        g = gcd(A, B)
        A //= g
        B //= g
        # いずれもマイナスの場合、傾きはプラスになる
        if A < 0 and B < 0:
            A *= -1
            B *= -1
        if A * B > 0:
            d_S[(A, B)] += 1
            d_T[(B, -A)] += 0
        # 片方がマイナスの場合、必ずAがマイナスになるよう揃える
        else:
            if A > B:
                A, B = B, A
            d_S[(-A, B)] += 0
            d_T[(B, A)] += 1

ans = 1
for (si, sj), s_cnt in d_S.items():
    t_cnt = d_T[(sj, -1*si)]
    tmp = 0
    tmp += pow2_mod[s_cnt] - 1 # Sから1匹以上選ぶ組合せ
    tmp += pow2_mod[t_cnt] - 1 # Tから1匹以上選ぶ組合せ
    tmp += 1 # どちらも選ばない組合せ
    ans = (ans * tmp)%MOD

ans -= 1 # 最終的に1匹も選ばない組合せ
ans += zeros # (0, 0)のイワシの数

print(ans%MOD)

Submission status: Accepted

Solution code:
from collections import defaultdict
from math import gcd


def normal(x, y):
    if x == 0:
        return (0, 1)
    elif y == 0:
        return (1, 0)
    g = gcd(x, y)
    x, y = x // g, y // g
    if x < 0:
        x, y = -x, -y
    return (x, y)


def orthogonal(T):
    if T[0] == 0:
        return (1, 0)
    elif T[1] == 0:
        return (0, 1)
    if T[1] > 0:
        return (T[1], -T[0])
    else:
        return (-T[1], T[0])


N = int(input())
C = defaultdict(int)
z = 0
for i in range(N):
    Ai, Bi = map(int, input().split())
    if Ai == Bi == 0:
        z += 1
        continue
    n = normal(Ai, Bi)
    C[n] += 1

MOD = 1000000007
B = [1] * (N + 1)
for i in range(1, N + 1):
    B[i] = B[i - 1] * 2 % MOD

ans = 1
calc = set()
for n, c in C.items():
    if n in calc:
        continue
    a = B[c]
    calc.add(n)
    no = orthogonal(n)
    if no in C:
        co = C[no]
        a += B[co] - 1
        calc.add(no)
    ans *= a
    ans %= MOD
print((ans - 1 + z) % MOD)

Submission status: Accepted

Solution code:
# E - ∙ (Bullet)
import sys
from collections import defaultdict

readline = sys.stdin.readline
MOD = 1000000007
N = int(readline())

# イワシの傾きをA/Bとする。
# A/Bは予めgcdで割って約分し、同じ傾きのものを揃えておく。
# このとき、仲の悪い組合せは(A, B)に対して(B, -A)となるもの。 
# 前者をS、後者をTとして考える。
d_S = defaultdict(int)
d_T = defaultdict(int)

def gcd(x, y):
    if x == 0:
        return y
    else:
        return gcd(y%x, x)

zeros = 0
for i in range(N):
    A, B = map(int, readline().split())
    # (0, 0)のイワシは他の全てのイワシと仲が悪いため、
    # 1匹のみでしか選ぶことができない。最後にこの数を足す。
    if A == 0 and B == 0:
        zeros += 1
    # (?, 0),(0, ?)のイワシは、?がどのような数字であろうとも
    # この組合せであれば仲が悪い。一律、(1,0)(0,-1)として考える。
    elif A == 0:
        d_S[(1, 0)] += 0
        d_T[(0, -1)] += 1
    elif B == 0:
        d_S[(1, 0)] += 1
        d_T[(0, -1)] += 0
    else:
        g = gcd(A, B)
        A //= g
        B //= g
        # いずれもマイナスの場合、傾きはプラスになる
        if A < 0 and B < 0:
            A *= -1
            B *= -1
        if A * B > 0:
            d_S[(A, B)] += 1
            d_T[(B, -A)] += 0
        # 片方がマイナスの場合、必ずAがマイナスになるよう揃える
        else:
            if A > B:
                A, B = B, A
            d_S[(-A, B)] += 0
            d_T[(B, A)] += 1

ans = 1
for (si, sj), s_cnt in d_S.items():
    t_cnt = d_T[(sj, -1*si)]
    tmp = 0
    tmp += pow(2, s_cnt, MOD) - 1
    tmp += pow(2, t_cnt, MOD) - 1
    tmp += 1
    ans = (ans * tmp)%MOD

ans -= 1
ans += zeros

print(ans%MOD)

Submission status: Accepted

Solution code:
import math
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 9)

def main():
    n = int(input())
    mod = 10 ** 9 + 7
    h = {}
    zero = 0
    for i in range(n):
        a, b = map(int, input().split())
        if a == 0 and b == 0:
            zero += 1
            continue
        m = (0, 0)
        if b == 0:
            m = (1, 0)
        elif b > 0:
            g = math.gcd(a, b)
            m = (a // g, b // g)
        else:
            g = math.gcd(a, b)
            m = (-1 * (a // g), -1 * (b // g))
        if m not in h:
            h[m] = set()
        h[m].add(i)
    h2 = {}
    for m in h:
        mi1 = (-1 * m[1], m[0])
        if mi1 in h and mi1 not in h2:
            h2[m] = mi1
        mi2 = (m[1], -1 * m[0])
        if mi2 in h and mi2 not in h2:
            h2[m] = mi2
    ans = 1
    left = n - zero
    for k, v in h2.items():
        s1 = len(h[k])
        s2 = len(h[v])
        # print(s1, s2)
        r = (pow(2, s1 + s2, mod) - (pow(2, s1, mod) - 1) * (pow(2, s2, mod) - 1)) % mod
        ans *= r
        ans %= mod
        left -= (s1 + s2)
    ans *= pow(2, left, mod)
    ans -= 1
    ans += zero
    print(ans % mod)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from math import gcd
from collections import defaultdict

N = int(input())
AB = [tuple(map(int, input().split())) for _ in range(N)]
MOD = 10**9 + 7

d = defaultdict(int)#defaultdictで数えあげ
cnt_00 = 0
cnt_0b = 0
cnt_a0 = 0
for a,b in AB:
    if a == b == 0:
        cnt_00 += 1
    elif a == 0:
        cnt_a0 += 1
    elif b == 0:
        cnt_0b += 1
    else:
        num_gcd = gcd(a,b)
        grad = 1 if a * b > 0 else -1
        a //= num_gcd
        b //= num_gcd
        d[(grad, abs(a), abs(b))] += 1

ans = 1
for k in d.keys():
    if d[k] == 0:
        continue
    
    grad, a, b = k[0], k[1], k[2]
    if (-grad, b, a) in d:
        
        # 傾き a/bのものを一つ以上選ぶ場合（-b/aは選ばない） + -b/aから一つ以上選ぶ場合（a/bは選ばない） + どちらからも選ばない場合
        ans *= (pow(2, d[(grad, a, b)], MOD)-1) + (pow(2, d[(-grad, b, a)], MOD)-1) + 1
        ans %= MOD
        d[(grad, a, b)] = 0
        d[(-grad, b, a)] = 0
    else:
        # a/bから0個以上選ぶ場合
        ans *= pow(2, d[(grad, a, b)], MOD)
        ans %= MOD
        d[(grad, a, b)] = 0

# a,bの一方のみ0の場合 + どちらからも選ばない場合
ans *= (pow(2, cnt_a0, MOD)-1) + (pow(2, cnt_0b, MOD)-1) + 1
ans %= MOD

# 0,0のみを１つだけ入れる場合
ans += cnt_00
# なにも選ばない場合を除く
ans -= 1

ans %= MOD

print(ans)

Submission status: Accepted

Solution code:
import math
import copy

def main():
    N=int(input())
    zero_fish=0

    Pair={}

    for i in range(N):
        A,B=map(int,input().split())

        if A==0 and B==0:
            zero_fish+=1
            continue
        if B==0:
            bunsi=1
            bunbo=0
        elif B>0:
            bunsi=A//math.gcd(A,B)
            bunbo=B//math.gcd(A,B)
        else:
            bunsi=-1*A//math.gcd(A,B)
            bunbo=-1*B//math.gcd(A,B)

        key = str(bunsi) + "/" + str(bunbo)

        if bunsi == 0 or bunbo == 0:
            rev_bunsi = bunbo
            rev_bunbo = bunsi
        elif bunsi < 0:
            rev_bunsi = bunbo
            rev_bunbo = -1 * bunsi
        else:
            rev_bunsi = -1 * bunbo
            rev_bunbo = bunsi
        rev_key = str(rev_bunsi) + "/" + str(rev_bunbo)

        if (key in Pair.keys()):
            Pair[key][0]+=1
        elif (rev_key in Pair.keys()):
            Pair[rev_key][1]+=1
        else:
            Pair[key]=[1,0]

    res=1
    mod=1000000007
    for p in Pair.values():
        if p[1]==0:
            temp=pow(2,p[0],mod)
        else:
            temp=(pow(2,p[0],mod)+pow(2,p[1],mod)-1)%mod
        res=(res*temp)%mod
    res+=zero_fish-1

    print(res%mod)

if __name__=="__main__":
    main()

Submission status: Accepted

Solution code:
import sys
import math
from math import gcd

mod = 1000000007
 
N = int(sys.stdin.readline().strip())
zero = 0
mp = {}
for _ in range(N):
    a, b = map(int, sys.stdin.readline().strip().split())

    if a == 0 and b == 0:
        zero += 1
        continue
 
    g = gcd(a, b)
    a = a // g
    b = b // g
 
    if b < 0:
        a = -a
        b = -b
    if b == 0 and a < 0:
        a = -a
    if a <= 0:
        a, b = b, -a
        if (a, b) in mp:
            mp[(a, b)][0] += 1
        else:
            mp[(a, b)] = [1, 0]
    else:
        if (a, b) in mp:
            mp[(a, b)][1] += 1
        else:
            mp[(a, b)] = [0, 1]
 
ans = 1
for key in mp:
    s, t = mp[key]
    ans *= pow(2, s, mod) + pow(2, t, mod) - 1
    ans %= mod
print((zero - 1 + ans) % mod)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
mod = 10**9 + 7
n = int(input())
ab = [[int(x) for x in input().split()] for _ in range(n)]
from collections import defaultdict, Counter
import math

double_zero_cnt = 0 # [0, 0]の個数
a_b = [] # a/bを、約分した形で保持(a/gcd(a, b), b/gcd(a, b), 符号)
for a, b in ab:
    if a == 0 and b == 0: 
        double_zero_cnt += 1
        continue
    g = math.gcd(a, b)
    a //= g
    b //= g
    sign = 1 if a*b > 0 else -1 if a*b < 0 else 0
    a_b.append((abs(a), abs(b), sign))

c = Counter(a_b) # ベクトルごとにグループ分け
key_list = list(c.keys())

d = defaultdict(list) # [a, b] あるngなペアのそれぞれの要素の個数
for key in key_list:
    a, b, sign = key
    if d[(b, a, -sign)]: # ダブルカウントしないように
        continue 
    if c[(b, a, -sign)] != 0:
        d[(a, b, sign)] = [c[(a, b, sign)], c[(b, a, -sign)]]

ans = 1 # 積算の単位元
used_cnt = double_zero_cnt # 組めないものがあるイワシの個数(計算で使用したらカウント)
for key in d.keys():
    if d[key] == []: # 前のループで調べると[]が生まれてしまう
        continue
    x, y = d[key]
    used_cnt += (x + y)
    mul = (pow(2, x, mod) + pow(2, y, mod) - 1) % mod # このグループからは、片方ずつからしか出せない。何も選ばないがダブルカウントになる。
    ans *= mul
    ans %= mod

ans *= pow(2, n - (used_cnt), mod) # まだ使われていないイワシは好きな組み合わせ可能
ans += double_zero_cnt # 両方0のものは1つにつき自分のみの1通り
ans -= 1 # 0匹は選べない
ans %= mod
print(ans)

Submission status: Accepted

Solution code:
import math
mod = 10**9+7
N = int(input())

iwashi01 = 0
iwashi10 = 0
iwashi00 = 0
iwashi = dict()
for i in range(N):
    a, b = map(int, input().split())
    if a == 0 and b == 0:
        iwashi00 += 1
    elif a == 0:
        iwashi01 += 1
    elif b == 0:
        iwashi10 += 1            
    else:
        g = math.gcd(abs(a), abs(b))
        a //= g; b //= g
        if a*b > 0:
            if a < 0 and b < 0:
                a *= -1
                b *= -1
            iwashi.setdefault((a, b), [0, 0])
            iwashi[(a, b)][0] += 1
        if a*b < 0:
            if a < 0 and b > 0:
                a *= -1
                b *= -1
            a, b = -b, a
            iwashi.setdefault((a, b), [0, 0])
            iwashi[(a, b)][1] += 1

r = 2**iwashi01 % mod - 1 + 2**iwashi10 % mod - 1 + 1
for s, t in iwashi.values():
    r *= 2**s % mod -1 + 2**t % mod -1 + 1
    r %= mod
print((r + iwashi00 - 1) % mod)

Submission status: Accepted

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