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 sys import stdin
input = stdin.buffer.readline
from collections import defaultdict

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

MOD = 10 ** 9 + 7

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

rest = N
zero = 0
zero_left, zero_right = 0, 0
tmp = []
for a, b in AB:
    if a == b == 0:
        zero += 1
        rest -= 1
    elif a == 0:
        zero_left += 1
    elif b == 0:
        zero_right += 1
    else:
        gcd_ab = gcd(abs(a), abs(b))
        a, b = a // gcd_ab,  b // gcd_ab
        if a < 0: a, b = -a, -b
        tmp.append([a, b])
AB = tmp

cnt = defaultdict(int)
for a, b in AB:
    cnt[(a, b)] += 1

answer = 1
answer *= pow(2, zero_left + zero_right, MOD) - (pow(2, zero_left, MOD) - 1) * (pow(2, zero_right, MOD) - 1)
answer %= MOD
rest -= zero_right + zero_left
#print("answer:", answer)

check = defaultdict(int)
for a, b in AB:
    if b > 0 and check[(a, b)] == 0:
        check[(a, b)] = 1
        answer *= pow(2, cnt[(a, b)] + cnt[(b, -a)], MOD) - (pow(2, cnt[(a, b)], MOD) - 1) * (pow(2, cnt[(b, -a)], MOD) - 1) 
        answer %= MOD
        rest -= cnt[(a, b)] + cnt[(b, -a)]

answer *= pow(2, rest, MOD)
answer += zero - 1
answer %= MOD
print(answer)

Submission status: Accepted

Solution code:
from math import gcd
import sys
input = sys.stdin.readline
n=int(input())
dic={}
z=0
mod=10**9+7
for i in range(n):
    a,b=map(int,input().split())
    if a==b==0:
        z+=1
        continue
    k=gcd(a,b)
    a//=k
    b//=k
    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 dic:
            dic[(a,b)][0]+=1
        else:
            dic[(a,b)]=[1,0]
    else:
        if (a,b) in dic:
            dic[(a,b)][1]+=1
        else:
            dic[(a,b)]=[0,1]
ans=1
for x in dic:
    v=dic[x]
    s = v[0]
    t = v[1]
    ans*=pow(2,s,mod)+pow(2,t,mod)-1
    ans%=mod
print((z-1+ans)%mod)

Submission status: Accepted

Solution code:
def ii():return int(input())
def iim():return map(int,input().split())
def iil():return list(map(int,input().split()))
def ism():return map(str,input().split())
def isl():return list(map(str,input().split()))

from math import gcd

mod = int(1e9+7)
n = ii()
cnd = {}
azero = 0
bzero = 0
allzero = 0
for _ in range(n):
    a,b = iim()
    if a*b == 0:
        if a == 0 and b != 0:
            azero += 1
        elif a != 0 and b == 0:
            bzero += 1
        else:
            allzero += 1
    else:
        g = gcd(a,b)
        a //= g
        b //= g
        if a<0:
            a *= -1
            b *= -1
        before = cnd.get((a,b),False)
        if b > 0:
            check = cnd.get((b,-a),False)
        else:
            check = cnd.get((-b,a),False)
        if before:
            cnd[(a,b)] = [before[0]+1,before[1]]
        elif check:
            if b > 0:
                cnd[(b,-a)] = [check[0],check[1]+1]
            else:
                cnd[(-b,a)] = [check[0],check[1]+1]
        else:
            cnd[(a,b)] = [1,0]

cnd[0] = [azero,bzero]
noreg = 0
ans = 1
#print(cnd)
for item in cnd.values():
    if item[0] == 0  or item[1] == 0:
        noreg += max(item[0],item[1])
    else:
        ans *= (2**item[0]+2**item[1]-1)
        ans %= mod
print((ans*((2**noreg)%mod)-1+allzero)%mod)

Submission status: Accepted

Solution code:
def ggcd(a,b):
    if(b==0):
        return a
    return ggcd(b,a%b)
import math
import fractions
import collections
import itertools
import pprint
N=int(input())
l1=[]
adivb=[]
bis0=0
bdiva=[]
ais0=0
both0=0
p=10**9+7
fish=[list(map(int,input().split())) for _ in range(N)]
fishcomp=[]
d={}
for i in range(N):
    #イメージ的にはa/bを格納していく感じ
    #ai/bi==-bj/ajならダメ
    a=fish[i][0]
    b=fish[i][1]
    g=ggcd(a,b)
    if g!=0:        #ggcdの定義よりa=b=0なら0になりそう(a=0,b!=0ならb,逆もしかり)、つまり(a,0)(0,b)は(1,0)(0,1)にmapされる
        a=a//g
        b=b//g
    #ここらへんで、a,bをそのgcdで割ることによる正規化が完了しているはず
    if b<0:     #b<0の時に強制的にbを正の値に変換しても影響はない(これを噛ませると後々嬉しい)
        a=-a
        b=-b
    if (a!=0)or(b!=0):          #a=b=0でない時は(a,b)(-b,a)といった組みをなすことで仲が悪くなる。よって、(a,b)の連想配列を組んでそのペアを探す下準備
        if d.get(a)==None:
            d[a]={}
            d[a][b]=1
        else:
            if d[a].get(b)==None:
                d[a][b]=1
            else:
                val=d[a].get(b)
                d[a][b]=val+1
        fishcomp.append([a, b])
    else:                       #a=b=0の時は、単体でいてもダメなので、別カウント
        both0=both0+1
#print(d)
#print(fishcomp)
fishcomp=list(map(list,set(map(tuple,fishcomp))))   #二次元配列のset(地味にreferenceがないやつ)
#print(fishcomp)
length=N-both0                                      #とりあえずどっちも0なやつは制約なしには使えないので引く
#print(both0)
sets=[]
#以下ではai/bi==-bj/ajの組みを探している。d[a][b]の個数とd[-b][a]及びd[b][-a]の個数のみ探せば良い、ただ一方のみフォーカスして取ればok
#(a,b)のkeyにて(-b,a)のkeyを取れるか探すことをf(a,b)=(-b,a)としてmapするとf(f(a,b))=(-a,-b)となり、b>0より-b<0のキーは必ず存在しない
#一方f(a,b)=(b,-a)としてもf(f(a,b))=(-a,-b)より、逆方向のキーは存在せず、取れるときは一方向にしか取れない
#(ここでb>0が生きる)
#
for i in fishcomp:
    a=i[0]
    b=i[1]
    val1=d[a][b]
    #print(a,b,val1)
    if d.get(-b)!=None:
        if d[-b].get(a)!=None:
            val2=d[-b][a]               #(a,b)とペアにして都合の悪いものの個数
            sets.append([val1,val2])    #[(a,b)の個数,(-b,a)の個数]のペア
            length=length-(val2+val1)   #((a,b)の個数+(-b,a)の個数)個は自由に扱えなくなりました
#print(sets,length)
pro=1
for i in sets:
    #都合が悪いペアについては、(a,b)同士のみまたは(-b,a)同士のみしか含めることができない
    #よって都合が悪くなるペアごとに、(a,b)の方のみにフォーカスして使う/使わないをbinaryに考えたpow(2,#(a,b))こ、
    #(-b,a)の方のみにフォーカスして使う/使わないをbinaryに考えたpow(2,#(-b,a))こ、そこからどちらとも考えている空集合を1つひいて
    #P(ai,bi)=pow(2,#(ai,bi))+pow(2,#(-bi,ai))-1こが、あるペアP(ai,bi)のイワシを使って仲良くできる組み合わせ数である。
    #この組み合わせ数はペアごとに独立に決まるため、Π(i for allpairs)P(ai,bi)が制約あるイワシ同士で捻出できる選び方である
    pro=(pro*(pow(2,i[0],p)+pow(2,i[1],p)-1))%p
#print(pro)
print((pow(2,length,p)*pro-1+both0)%p)          #制約のないイワシの個数はlengthこで、その自由な選び方はpow(2,length)通り
#(制約のないイワシの選び方)*(都合の悪くなりうるイワシの選び方)で良いが、
#考察から除外した(0 0)のイワシは単体でのみいられるため、1匹につき1count増やし、(0匹)*(0匹)となる1通りを除外し、
#よってpow(2,length)*Π(i for allpairs)P(ai,bi)+both0-1が解である

Submission status: Accepted

Solution code:
from collections import defaultdict


def fraction(a, b):
    """a/b を既約分数 numer/denom として求める
    denom は必ず非負整数
    numer = denom = 0 のときは numer/denom = 0/0
    numer = 0 のときは numer/denom = 0/1
    denom = 0 のときは numer/denom = 1/0
    """
    numer, denom = a, b
    if numer == denom == 0:
        return 0, 0
    elif numer == 0:
        return 0, 1
    elif denom == 0:
        return 1, 0

    # GCD(a, b) を計算して約分する
    while b:
        a, b = b, a % b
    gcd_ab = a
    numer = numer // gcd_ab
    denom = denom // gcd_ab

    if denom < 0:  # denom は必ず非負整数
       numer, denom = -numer, -denom
    return numer, denom
  

n = int(input())
info = [list(map(int, input().split())) for i in range(n)]
MOD = 10 ** 9 + 7

memo = defaultdict(int)
for i in range(n):
    a, b = info[i]
    memo[fraction(a, b)] += 1

cnt_00 = 0
cnt_n0 = 0 
cnt_d0 = 0
ans = 1
used = set()
for frac in memo:
    numer, denom = frac
    if numer == 0 and denom == 0:
        cnt_00 += memo[frac]
        continue
    if frac in used:
        continue
    if numer == 0 or denom == 0:
        cnt1, cnt2 = 0, 0
        if (0, 1) in memo:
            cnt1 = memo[(0, 1)]
        if (1, 0) in memo:
            cnt2 = memo[(1, 0)]
        tmp = pow(2, cnt1, MOD) + pow(2, cnt2, MOD) - 1
        ans *= tmp
        used.add((0, 1))
        used.add((1, 0))
        continue

    rev_num, rev_den = -denom, numer
    if rev_den < 0:
        rev_num, rev_den = -rev_num, -rev_den

    cnt1 = memo[frac]
    cnt2 = 0
    if (rev_num, rev_den) in memo:
        cnt2 = memo[(rev_num, rev_den)]
    tmp = pow(2, cnt1, MOD) + pow(2, cnt2, MOD) - 1
    ans *= tmp
    ans %= MOD
    used.add((rev_num, rev_den))

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

Submission status: Accepted

Solution code:
from collections import defaultdict
import math
import sys
 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

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

def main():
    MOD = 1000000007
    N = int(readline())
    m = map(int, read().split())
    A, B = zip(*zip(m, m))
    # Ai * Aj + Bi * Bj = 0
    # -> Ai * Aj = -Bi * Bj
    # -> (Ai/Bi) = -(Aj/Bj)
    # のとき、そのイワシ同士は入れられない

    # そこで、 Ci = Ai/Bi を約分したもの（かつBi>0としておく）
    # を覚えておき、Ci = -Cj となるようなペア同士を数えていく

    C = defaultdict(int)
    n00 = 0
    for a, b in zip(A, B):
        # (0, 0) はどのイワシとも仲が悪いので、考慮の対象から外して置き、
        # 後で(0, 0)のイワシの本数分足す
        if a == 0 and b == 0:
            n00 += 1
            continue

        # Bが0の場合、Aが0のイワシであればなんでも仲が悪くなるので、
        # C = -1 / 0 で統一する。
        if b == 0:
            C[(-1, 0)] += 1
            continue
        # Aが0の場合、Bが0のイワシであればなんでも仲が悪くなるので、
        # C = 0 / 1 で統一する。
        elif a == 0:
            C[(0, 1)] += 1
            continue
        # A / B を約分して、同じ値のイワシの個数を数え上げる
        g = math.gcd(a, b)
        a = a // g
        b = b // g
        # bは常に0以上にする
        if b < 0:
            b = -b
            a = -a
        C[(a, b)] += 1
    
    C = dict(C)
    flag = {k: False for k in C.keys()}

    ans = 1
    for c, nc in C.items():
        a, b = c
        a2, b2 = (-b, a) if a >= 0 else (b, -a)
        # 仲の悪いイワシの個数
        nBad = C.get((a2, b2), 0)
        # 仲の悪いイワシがいなければ、
        # この中からイワシを選ぶ時のすべての組み合わせ（全て選択しない場合を含む）の数を考える
        # = 2^nc  = 1 << nc
        if nBad == 0:
            k = 1 << nc
        else:
            # (-2, 3) (3, 2) があるとき、それぞれで組み合わせを考えると重複するので、
            # 片方しか数えないようにする
            if flag[(a2, b2)]:
                continue

            # 仲の悪いイワシがいる場合、
            # あるCのイワシがnc本、それと中の悪いイワシがnBad本あるとする。
            # nc + nBad 本のイワシのうち、OKな組み合わせの個数は
            # [nc本から1本以上選ぶ組み合わせ] + [nc本から1本以上選ぶ組み合わせ] + [イワシを全て選択しない場合]
            # (2^nc - 1) + (2^nBad - 1) + 1 = 2^nc + 2^nBad - 1
            k = (1 << nc) + (1 << nBad) - 1
        
        ans = (ans * k) % MOD
        flag[c] = True

    # 上の数え上げだと、イワシを1本も選ばない場合も含まれているので、
    # そのパターンを除外するため-1する。
    # -1 するついでに(0, 0) のイワシから1本以上選ぶ場合の数も足しておく
    ans = (ans + n00 - 1) % MOD
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from math import gcd

MOD = 10**9+7
N = int(input())
d = {}
zero = 0
for i in range(N):
    a, b = map(int, input().split())
    if a == 0 and b == 0:
        zero += 1
        continue

    # cosで単位円を考える
    # 第一象限に来るまでの90度回転回数
    flip = 0
    while not (a >= 0 and b > 0):
        a, b = -b, a
        flip ^= 1

    g = gcd(a, b)
    a //= g
    b //= g
    if not (a, b) in d:
        d[(a, b)] = [0, 0]
    d[(a, b)][flip] += 1

ans = 1
for (v1, v2) in d.values():
    ans *= pow(2, v1, MOD) + pow(2, v2, MOD)-1
    ans %= MOD
ans -= 1
ans += zero
ans %= MOD
print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(700000)

def s_in():
    return input()

def n_in():
    return int(input())

def l_in():
    return list(map(int, input().split()))

MOD = 1000000007

def mod_add(a, b):
  return (a+b)%MOD

def mod_sub(a, b):
  return (a+MOD-b)%MOD

def mod_mul(a, b):
  return a*b%MOD

#互いに素なa,bについて、a*x+b*y=1の一つの解
def extgcd(a,b):
    r = (1,0,a)
    w = (0,1,b)
    while w[2]!=1:
        q = r[2]//w[2]
        r2 = w
        w2 = [r[0]-q*w[0],r[1]-q*w[1],r[2]-q*w[2]]
        r = r2
        w = w2
    return (w[0],w[1])

def mod_inv(a):
    x,_  = extgcd(a, MOD)
    return (MOD+x%MOD)%MOD

def mod_div(a, b):
    return a*mod_inv(b)%MOD

def mod_pow(a, b):
    res = 1
    while b > 0:
        if b & 1:
            res = res * a % MOD
        a = a * a % MOD
        b >>= 1
    return res

from collections import Counter
from fractions import Fraction

n = n_in()
c = Counter()
iab = []
for i, _ in enumerate(range(n)):
    a,b=l_in()
    if a == 0 and b == 0:
        c[(0,0)] += 1
        continue
    if b == 0:
        c[(1,0)] += 1
        continue
    if a == 0:
        c[(0,1)] += 1
        continue

    f = Fraction(a,b)
    c[(f.numerator, f.denominator)] += 1

res = 1
vis = set()

for (a,b),s in c.items():
    if (a,b) in vis:
        continue
    if (a,b) == (0,0):
        continue

    tupl = (0,0)
    if b == 0:
        tupl = (0,1)
    elif a == 0:
        tupl = (1,0)
    else:
        f = Fraction(-b,a)            
        tupl = (f.numerator, f.denominator)

    vis.add(tupl)
    t = c[tupl]

    tmp = mod_add(mod_sub(mod_pow(2,s),1), mod_sub(mod_pow(2,t),1))
    tmp = mod_add(tmp,1)

    res = mod_mul(res, tmp)

res = mod_sub(res,1)
res = mod_add(res, c[(0,0)])
print(res)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
from collections import Counter, defaultdict, deque
import math

import sys
# sys.setrecursionlimit(10**6)
# buff_readline = sys.stdin.buffer.readline
buff_readline = sys.stdin.readline
readline = sys.stdin.readline

INF = 2**62-1


def read_int():
    return int(buff_readline())


def read_int_n():
    return list(map(int, buff_readline().split()))


def read_float():
    return float(buff_readline())


def read_float_n():
    return list(map(float, buff_readline().split()))


def read_str():
    return readline().strip()


def read_str_n():
    return readline().strip().split()

def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


def f(a, b):
    if a == 0 and b == 0:
        return (1, 0, 0)
    if b == 0:
        return (1, 1, 0)
    g = math.gcd(a, b)
    a //= g
    b //= g
    if a == 0 and b < 0:
        s = 1
    else:
        s = 1 if a * b >= 0 else -1
    a = abs(a)
    b = abs(b)
    return s, a, b


class Mod:
    def __init__(self, m):
        self.m = m

    def add(self, a, b):
        return (a + b) % self.m

    def sub(self, a, b):
        return (a - b) % self.m

    def mul(self, a, b):
        return ((a % self.m) * (b % self.m)) % self.m

    def div(self, a, b):
        return self.mul(a, pow(b, self.m-2, self.m))

    def pow(self, a, b):
        return pow(a, b, self.m)


@mt
def slv(N, AB):
    adb = Counter()
    for a, b in AB:
        s, a, b = f(a, b)
        adb[(s*a, b)] += 1
    M = Mod(1000000007)
    ans = 1
    done = set()
    for k, v in adb.items():
        if k in done:
            continue
        if k == (0, 0):
            continue
        a, b = k
        if a < 0:
            s = 1
            a = abs(a)
        elif a == 0:
            s = 1
        else:
            s = -1
        n = adb[(s*b, a)]
        done.add(k)
        done.add((s*b, a))
        t = M.sub(M.pow(2, v) + M.pow(2, n), 1)
        ans = M.mul(ans, t)

    return M.add(M.sub(ans, 1), adb[(0, 0)])


def main():
    N = read_int()
    AB = [read_int_n() for _ in range(N)]
    print(slv(N, AB))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
from collections import Counter, defaultdict, deque
import math

import sys
# sys.setrecursionlimit(10**6)
# buff_readline = sys.stdin.buffer.readline
buff_readline = sys.stdin.readline
readline = sys.stdin.readline

INF = 2**62-1


def read_int():
    return int(buff_readline())


def read_int_n():
    return list(map(int, buff_readline().split()))


def read_float():
    return float(buff_readline())


def read_float_n():
    return list(map(float, buff_readline().split()))


def read_str():
    return readline().strip()


def read_str_n():
    return readline().strip().split()

def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


def f(a, b):
    if a == 0 and b == 0:
        return (1, 0, 0)
    if b == 0:
        return (1, 1, 0)
    g = math.gcd(a, b)
    a //= g
    b //= g
    if a == 0 and b < 0:
        s = 1
    else:
        s = 1 if a * b >= 0 else -1
    a = abs(a)
    b = abs(b)
    return s, a, b


class Mod:
    def __init__(self, m):
        self.m = m

    def add(self, a, b):
        return (a + b) % self.m

    def sub(self, a, b):
        return (a - b) % self.m

    def mul(self, a, b):
        return ((a % self.m) * (b % self.m)) % self.m

    def div(self, a, b):
        return self.mul(a, pow(b, self.m-2, self.m))

    def pow(self, a, b):
        return pow(a, b, self.m)


@mt
def slv(N, AB):
    adb = Counter()
    for a, b in AB:
        s, a, b = f(a, b)
        adb[(s*a, b)] += 1
    error_print(adb)
    M = Mod(1000000007)
    ans = 1
    done = set()
    for k, v in adb.items():
        if k in done:
            continue
        if k == (0, 0):
            continue
        a, b = k
        if a < 0:
            s = 1
            a = abs(a)
        elif a == 0:
            s = 1
        else:
            s = -1
        n = adb[(s*b, a)]
        done.add(k)
        done.add((s*b, a))
        t = M.sub(M.pow(2, v) + M.pow(2, n), 1)
        ans = M.mul(ans, t)

    return M.add(M.sub(ans, 1), adb[(0, 0)])


def main():
    N = read_int()
    AB = [read_int_n() for _ in range(N)]
    print(slv(N, AB))


if __name__ == '__main__':
    main()

Submission status: Accepted

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

import sys
# import time
from math import gcd
# import numpy as np
# import scipy.sparse.csgraph as cs            # csgraph_from_dense(ndarray, null_value=inf), bellman_ford(G, return_predecessors=True), dijkstra, floyd_warshall
# import random                                # random, uniform, randint, randrange, shuffle, sample
# import string                                # ascii_lowercase, ascii_uppercase, ascii_letters, digits, hexdigits
# import re                                    # re.compile(pattern) => ptn obj; p.search(s), p.match(s), p.finditer(s) => match obj; p.sub(after, s)
# from bisect import bisect_left, bisect_right # bisect_left(a, x, lo=0, hi=len(a)) returns i such that all(val<x for val in a[lo:i]) and all(val>-=x for val in a[i:hi]).
# from collections import deque                # deque class. deque(L): dq.append(x), dq.appendleft(x), dq.pop(), dq.popleft(), dq.rotate()
from collections import defaultdict          # subclass of dict. defaultdict(facroty)
# from collections import Counter              # subclass of dict. Counter(iter): c.elements(), c.most_common(n), c.subtract(iter)
# from datetime import date, datetime          # date.today(), date(year,month,day) => date obj; datetime.now(), datetime(year,month,day,hour,second,microsecond) => datetime obj; subtraction => timedelta obj
# from datetime.datetime import strptime       # strptime('2019/01/01 10:05:20', '%Y/%m/%d/ %H:%M:%S') returns datetime obj
# from datetime import timedelta               # td.days, td.seconds, td.microseconds, td.total_seconds(). abs function is also available.
# from copy import copy, deepcopy              # use deepcopy to copy multi-dimentional matrix without reference
# from functools import reduce                 # reduce(f, iter[, init])
# from functools import lru_cache              # @lrucache ...arguments of functions should be able to be keys of dict (e.g. list is not allowed)
# from heapq import heapify, heappush, heappop # built-in list. heapify(L) changes list in-place to min-heap in O(n), heappush(heapL, x) and heappop(heapL) in O(lgn).
# from heapq import nlargest, nsmallest        # nlargest(n, iter[, key]) returns k-largest-list in O(n+klgn).
# from itertools import count, cycle, repeat   # count(start[,step]), cycle(iter), repeat(elm[,n])
# from itertools import groupby                # [(k, list(g)) for k, g in groupby('000112')] returns [('0',['0','0','0']), ('1',['1','1']), ('2',['2'])]
# from itertools import starmap                # starmap(pow, [[2,5], [3,2]]) returns [32, 9]
# from itertools import product, permutations  # product(iter, repeat=n), permutations(iter[,r])
# from itertools import combinations, combinations_with_replacement
# from itertools import accumulate             # accumulate(iter[, f])
# from operator import itemgetter              # itemgetter(1), itemgetter('key')
# from fractions import gcd                    # for Python 3.4 (previous contest @AtCoder)



def main():
    mod = 1000000007                # 10^9+7
    inf = float('inf')              # sys.float_info.max = 1.79...e+308
    # inf = 2 ** 64 - 1             # (for fast JIT compile in PyPy) 1.84...e+19
    sys.setrecursionlimit(10**6)    # 1000 -> 1000000
    def input(): return sys.stdin.readline().rstrip()
    def ii():    return int(input())
    def mi():    return map(int, input().split())
    def mi_0():  return map(lambda x: int(x)-1, input().split())
    def lmi():   return list(map(int, input().split()))
    def lmi_0(): return list(map(lambda x: int(x)-1, input().split()))
    def li():    return list(input())


    def standardization(a, b):
        """
        (a, b) で表される方向ベクトルをシンプルな整数ペアの方向ベクトルへ変換する
        処理後は第一、第四象限に方向ベクトルが集中する
        """
        assert (a != 0 or b != 0)
        if a == 0:
            return (0, 1)
        if b == 0:
            return (1, 0)
        g = gcd(a, b)
        a //= g
        b //= g
        # 第一項は正になるように
        # 原点対照にしてもベクトルの直行性は変わらない
        return (a, b) if a > 0 else (-a, -b)

    
    n = ii()
    L = [lmi() for _ in range(n)]

    dict_b_pos = defaultdict(int)
    dict_b_neg = defaultdict(int)
    origin = 0
    for a, b in L:
        if a == 0 and b == 0:
            origin += 1
            continue
        a, b = standardization(a, b)
        if b <= 0:
            dict_b_neg[(a, b)] += 1
        else:
            dict_b_pos[(b, -a)] += 1    # 対応するものはこれ
            dict_b_neg[(b, -a)] += 0    # 対応するスロットだけ作っておきループが回るようにする
    
    # print(dict_b_neg)
    # print(dict_b_pos)
    ans = origin
    tmp = 1
    for key, u in dict_b_neg.items():
        v = dict_b_pos[key]
        tmp = (tmp * (1 + pow(2, u, mod) - 1 + pow(2, v, mod) - 1)) % mod
    ans += tmp
    ans -= 1    # 全部使わないパターンを除く

    print(ans % mod)


if __name__ == "__main__":
    main()

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 + MOD - 1) % MOD)

Submission status: Accepted

Solution code:
def main():
    import math
    import collections
    N = int(input())

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

    d = collections.defaultdict(set)
    i = 0
    ans2 = 0
    for a, b in AB:
        if a == 0 and b == 0:
            N -= 1
            ans2 += 1
            continue
        g = math.gcd(a, b)
        if g != 0:
            a = a // g
            b = b // g

        d[(a, b)].add(i)
        i += 1

    ans = 0
    r = set()

    dd = [1]
    for i in range(1, N+1):
        dd.append(dd[i-1]*2 % mod)

    r = set()
    ans = 1
    for a, b in d:
        if (a, b) in r:
            continue
        s1 = d[(a, b)]
        if (-a, -b) in d:
            s1 |= d[(-a, -b)]
        l1 = len(s1)
        r.add((-a, -b))
        if l1:
            s2 = set()
            if (-b, a) in d:
                s2 |= d[(-b, a)]
            if (b, -a) in d:
                s2 |= d[(b, -a)]
            s2 -= s1
            l2 = len(s2)
            if l2:
                ans *= dd[l1] + dd[l2] - 1
                N -= l1 + l2
                ans %= mod
                r.add((-b, a))
                r.add((b, -a))
            else:
                continue
    if N:
        ans *= dd[N]
    ans += ans2
    ans -= 1
    print(ans % mod)


main()

Submission status: Accepted

Solution code:
def ii():return int(input())
def iim():return map(int,input().split())
def iil():return list(map(int,input().split()))
def ism():return map(str,input().split())
def isl():return list(map(str,input().split()))

#from fractions import Fraction
from math import gcd

mod = int(1e9+7)
n = ii()
cnd = {}
azero = 0
bzero = 0
allzero = 0
for _ in range(n):
    a,b = iim()
    if a == 0:
        if b != 0:
            azero += 1
        else:
            allzero += 1
    elif b == 0:
        bzero += 1            
    else:
        '''
        ratio = Fraction(a,b)
        before = cnd.get(ratio,False)
        if before:
            cnd[ratio] = [before[0]+1,before[1]]
        else:
            invratio = Fraction(-b,a)
            check = cnd.get(invratio,False)
            if check:
                cnd[invratio] = [check[0],check[1]+1]
            else:
                cnd[ratio] = [1,0]
        '''
        g = gcd(a,b)
        a //= g
        b //= g
        if a < 0:
            a *= -1
            b *= -1
        cnd[(a,b)] = cnd.get((a,b),0)+1


noreg = 0
if azero == 0 or bzero == 0:
    noreg += max(azero,bzero)
    ans = 1
else:
    ans = (2**azero%mod + 2**bzero%mod - 1)%mod
#print('ans block')
#print(ans,noreg)
#print(cnd)
for k,item in cnd.items():
    a,b = k
    if b>0:
        m = cnd.get((b,-a),False)
        if m:
            ans *= (2**item%mod+2**m%mod-1)%mod
        else:
            noreg += item
    else:
        m = cnd.get((-b,a),False)
        if not m:
            noreg += item
#print('hoge')
print(int((ans*((2**noreg)%mod)-1+allzero)%mod))

Submission status: Accepted

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

def gcd(a, b):
    while b:
        a, b = b, a%b
    return a

N = int(input())
zero1 = 0
zero2 = 0
zero3 = 0
cnt = defaultdict(int)
MOD = 10**9+7

for _ in range(N):
    A, B = map(int, input().split())
    
    if A==0 and B==0:
        zero1 += 1
    elif A>0 and B>0:
        G = gcd(A, B)
        A //= G
        B //= G
        cnt[(A, B)] += 1
    elif A>0 and B<0:
        B *= -1
        G = gcd(A, B)
        A //= G
        B //= G
        cnt[(-A, B)] += 1
    elif A<0 and B>0:
        A *= -1
        G = gcd(A, B)
        A //= G
        B //= G
        cnt[(-A, B)] += 1
    elif A<0 and B<0:
        A *= -1
        B *= -1
        G = gcd(A, B)
        A //= G
        B //= G
        cnt[(A, B)] += 1
    elif A==0:
        zero2 += 1
    elif B==0:
        zero3 += 1

s = set()
ans = 1

for k in cnt.keys():
    if k in s:
        continue
    
    k2 = (-k[1], k[0])
    
    if k2[0]<0 and k2[1]<0:
        k2 = (-k2[0], -k2[1])
        
    a = cnt[k]
    
    if k2 not in cnt:
        ans *= pow(2, a, MOD)
        ans %= MOD
    else:
        b = cnt[k2]
        ans *= pow(2, a, MOD)+pow(2, b, MOD)-1
        ans %= MOD
        s.add(k2)

ans *= pow(2, zero2, MOD)+pow(2, zero3, MOD)-1
ans += zero1
ans %= MOD
ans -= 1
ans %= MOD

print(ans)

Submission status: Accepted

Solution code:
import bisect
import collections
import functools
import heapq
import math
from collections import deque
from collections import defaultdict
MOD = 10**9+7

N = int(input())
A = [0]*N
B = [0]*N
C = [[0]*2 for _ in range(N)]
zero = 0
no_inf = 0
inf = 0
for i in range(N):
    A[i],B[i] = map(int,(input().split()))
    if A[i] == 0 and B[i] == 0:
        C[i] = (0,0)
        zero += 1
    elif A[i] == 0:
        C[i] = (0,0)
        no_inf += 1
    elif B[i] == 0:
        C[i] = (0,0)
        inf += 1
    elif B[i] > 0:
        g = math.gcd(A[i],B[i])
        C[i] = (A[i]//g,B[i]//g)
    else:
        g = math.gcd(A[i],B[i])
        C[i] = (-A[i]//g,-B[i]//g)

d = defaultdict(int)

for i in range(N):
    if C[i] != (0,0):
        d[C[i]] += 1

ans = 1
for k in d.keys():
    if k[0] > 0:
        if (-k[1],k[0]) in d:
            ans *= pow(2,d[k],MOD) + pow(2,d[(-k[1],k[0])],MOD) -1
            d[k],d[(-k[1],k[0])] = 0,0
        else:
            ans *= pow(2,d[k],MOD)
    else:
        if (k[1],-k[0]) in d:
            ans *= pow(2,d[k],MOD) + pow(2,d[(k[1],-k[0])],MOD) -1
            d[k],d[(k[1],-k[0])] = 0,0
        else:
            ans *= pow(2,d[k],MOD)

ans *= pow(2,no_inf,MOD) + pow(2,inf,MOD) -1
print((ans+zero-1)%MOD)

Submission status: Accepted

Solution code:
from collections import defaultdict
from math import gcd
import sys
input = sys.stdin.readline
N=int(input())
mod=10**9+7
dic=defaultdict(lambda: [0,0])
c=0
d=0
e=0
for i in [0]*N:
 A,B = map(int,input().split())
 if A==0 and B==0:
  e+=1
 elif A==0:
  c+=1
 elif B==0:
  d+=1
 else:
  g=gcd(A,B)
  A//=g
  B//=g
  if A*B>0:
   dic[(abs(A),abs(B))][0]+=1
  else:
   dic[(abs(B),abs(A))][1]+=1
ans=1
for k in dic:
 ans=ans*(pow(2,dic[k][0],mod)+pow(2,dic[k][1],mod) -1)
ans=ans*(pow(2,c,mod)+pow(2,d,mod)-1)
print((ans-1+e)%mod)

Submission status: Accepted

Solution code:
mod = 10 ** 9 + 7
from math import gcd
N = int(input())
from collections import defaultdict
X = defaultdict(lambda: [0, 0])
x = 0
y = 0
z = 0
for i in range(N):
  a, b = map(int, input().split())
  g = abs(gcd(a, b))
  if a * b > 0:
    X[(abs(a) // g, abs(b) // g)][0] += 1
  elif a * b < 0:
    X[(abs(b) // g, abs(a) // g)][1] += 1
  else:
    if a:
      x += 1
    elif b:
      y += 1
    else:
      z += 1
ans = 1
pow2 = [1]
for i in range(N):
  pow2 += [pow2[-1] * 2 % mod]
for i in X.values():
  ans *= pow2[i[0]] + pow2[i[1]]- 1
  ans %= mod
ans *= pow2[x] + pow2[y] - 1
ans += z - 1
ans %= mod
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict

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

mod = 10 ** 9 + 7
N = int(input())
X = defaultdict(lambda: [0, 0])
# X = dict()
x = 0
y = 0
z = 0
for i in range(N):
    a, b = map(int, input().split())
    g = abs(gcd(a, b))
    if a * b > 0:
        X[(abs(a) // g, abs(b) // g)][0] += 1
    elif a * b < 0:
        X[(abs(b) // g, abs(a) // g)][1] += 1
    else:
        if a:
            x += 1
        elif b:
            y += 1
        else:
            z += 1
# suppose we have a super head point which can put togother with every point.
ans = 1
pow2 = [1]
for i in range(N):
    pow2 += [pow2[-1] * 2 % mod]
for i in X.values():
    ans *= pow2[i[0]] + pow2[i[1]]- 1
    ans %= mod
ans *= pow2[x] + pow2[y] - 1
print((ans+z-1)%mod)