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: Time Limit Exceeded

Solution code:
from collections import defaultdict
from fractions import Fraction
def powmod(x, n,mod):
  if n == 0:
   return 1
  K = 1
  while n > 1:
   if n % 2 != 0:
    K = K * x%mod
    x = x ** 2%mod
    n = (n - 1) // 2
   else:
    x = x ** 2%mod
    n = n // 2%mod

  return K * x # 指数を割り続け n が 1 に至ったら終了
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 range(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:
  if Fraction(A,B)>0:
   dic[Fraction(A,B)][0]+=1
  else:
   dic[-1/Fraction(A,B)][1]+=1
ans=1
for k in dic:
 ans*=(powmod(2,dic[k][0],mod)+powmod(2,dic[k][1],mod) -1)
 ans%=mod
ans*=(powmod(2,c,mod)+powmod(2,d,mod)-1)
print((ans-1+e)%mod)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
from fractions import Fraction
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 range(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:
  if Fraction(A,B)>0:
   dic[Fraction(A,B)][0]+=1
  else:
   dic[-1/Fraction(A,B)][1]+=1
ans=1
for k in dic:
 ans*=(pow(2,dic[k][0],mod)+pow(2,dic[k][1],mod) -1)
 ans%=mod
ans*=(pow(2,c,mod)+pow(2,d,mod)-1)
print((ans-1+e)%mod)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
from fractions import Fraction

N = int(input())

MOD = 1000000007
d_plus = defaultdict(int)  # + or ∞
d_minus = defaultdict(int)  # - or 0
ans = 1
ans_00 = 0
for i in range(N):
    a, b = map(int, input().split())
    if a == 0 and b == 0:
        ans_00 += 1
    elif a == 0:
        d_minus[0] += 1
    elif b == 0:
        d_plus[float('inf')] += 1
    elif a * b > 0:
        d_plus[Fraction(a, b)] += 1
    else:
        d_minus[Fraction(a, b)] += 1


def pair(p):
    if p == 0:
        return float('inf')
    elif p == float('inf'):
        return 0
    else:
        return -1 / p


for m in d_minus:
    d_plus[pair(m)] += 0
for p in d_plus:
    ans *= (pow(2, d_plus[p], MOD) + pow(2, d_minus[pair(p)], MOD) - 1)
    ans %= MOD
print((ans - 1 + ans_00) % MOD)

Submission status: Time Limit Exceeded

Solution code:
def main():
  from fractions import Fraction
  from collections import defaultdict
  N = int(input())

  MOD = 10**9 + 7

  zero_zero_count = 0
  zero_one_count = 0
  one_zero_count = 0
  dd_ba = defaultdict(int, {})
  for _ in range(N):
    a,b = map(int,input().split())
    if (a==0)and(b==0):
      zero_zero_count += 1
    elif (a==0):
      zero_one_count += 1
    elif (b==0):
      one_zero_count += 1
    else:
      dd_ba[Fraction(-b, a)] += 1

  ans = (2**zero_one_count + 2**one_zero_count -1)
  flag_dd = defaultdict(bool, {})

  iterator = list(dd_ba.items())
  for key,value in iterator:
    if flag_dd[key]:
      continue
    x = Fraction(key.denominator, -(key.numerator))
    y = dd_ba[x]
    ans *= (2**y + 2**value - 1) % MOD
    ans %= MOD
    flag_dd[x] = True

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

if __name__=='__main__':
  main()

Submission status: Time Limit Exceeded

Solution code:
def main():
  from fractions import Fraction
  from collections import defaultdict
  N = int(input())
  AB = [list(map(int,input().split())) for _ in range(N)]

  MOD = 10**9 + 7

  zero_zero_count = 0
  zero_one_count = 0
  one_zero_count = 0
  dd_ba = defaultdict(int, {})
  for a,b in AB:
    if (a==0)and(b==0):
      zero_zero_count += 1
    elif (a==0):
      zero_one_count += 1
    elif (b==0):
      one_zero_count += 1
    else:
      dd_ba[Fraction(-b, a)] += 1

  ans = (2**zero_one_count + 2**one_zero_count -1)
  flag_dd = defaultdict(bool, {})

  iterator = list(dd_ba.items())
  for key,value in iterator:
    if flag_dd[key]:
      continue
    x = Fraction(key.denominator, -(key.numerator))
    y = dd_ba[x]
    ans *= (2**y + 2**value - 1) % MOD
    ans %= MOD
    flag_dd[x] = True

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

if __name__=='__main__':
  main()

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
from fractions import Fraction

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

MOD = 1000000007
d_plus = defaultdict(int)  # + or ∞
d_minus = defaultdict(int)  # - or 0
ans = 1
ans_00 = 0
for i, (a, b) in enumerate(X):
    if a == 0 and b == 0:
        ans_00 += 1
    elif a == 0:
        d_minus[0] += 1
    elif b == 0:
        d_plus[float('inf')] += 1
    elif a * b > 0:
        d_plus[Fraction(a, b)] += 1
    else:
        d_minus[Fraction(a, b)] += 1


def pair(p):
    if p == 0:
        return float('inf')
    elif p == float('inf'):
        return 0
    else:
        return -1 / p


for m in d_minus:
    d_plus[pair(m)] += 0
for p in d_plus:
    ans = ans * (pow(2, d_plus[p], MOD) + pow(2, d_minus[pair(p)], MOD) - 1)
    ans %= MOD
print((ans - 1 + ans_00) % MOD)

Submission status: Time Limit Exceeded

Solution code:
def main():
  N = int(input())
  AB = [list(map(int,input().split())) for _ in range(N)]

  MOD = 1000000007
  from collections import defaultdict
  from fractions import Fraction

  zero_zero_count = 0
  zero_one_count = 0
  one_zero_count = 0
  dd_ba = defaultdict(int,{})
  for a,b in AB:
    if (a==0)and(b==0):
      zero_zero_count += 1
    elif (a==0):
      zero_one_count += 1
    elif (b==0):
      one_zero_count += 1
    else:
      dd_ba[Fraction(-b, a)] += 1

  ans = (2**zero_one_count + 2**one_zero_count -1)
  flag_dd = defaultdict(bool,{})

  iterator = list(dd_ba.items())
  for key,value in iterator:
    if flag_dd[key]:
      continue
    x = Fraction(key.denominator, -(key.numerator))
    y = dd_ba[x]
    ans *= (2**y + 2**value - 1) % MOD
    ans %= MOD
    flag_dd[x] = True

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

main()

Submission status: Time Limit Exceeded

Solution code:
def main():
  N = int(input())
  AB = [list(map(int,input().split())) for _ in range(N)]

  MOD = 1000000007
  from collections import defaultdict
  from fractions import Fraction

  zero_zero_count = 0
  zero_one_count = 0
  one_zero_count = 0
  dd_ba = defaultdict(int,{})
  dd_ab = defaultdict(int,{})
  for a,b in AB:
    if (a==0)and(b==0):
      zero_zero_count += 1
    elif (a==0):
      zero_one_count += 1
    elif (b==0):
      one_zero_count += 1
    else:
      dd_ba[Fraction(-b, a)] += 1
      dd_ab[Fraction(a, b)] += 1


  ans = (2**zero_one_count + 2**one_zero_count -1)
  flag_dd = defaultdict(bool,{})

  for key,value in dd_ba.items():
    if flag_dd[key]:
      continue
    ans *= (2**dd_ab[key] + 2**value - 1) % MOD
    ans %= MOD
    flag_dd[Fraction(key.denominator, -(key.numerator))] = True

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

main()

Submission status: Time Limit Exceeded

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

MOD = 1000000007
from collections import defaultdict
from fractions import Fraction

zero_zero_count = 0
zero_one_count = 0
one_zero_count = 0
dd_ba = defaultdict(int,{})
dd_ab = defaultdict(int,{})
for a,b in AB:
  if (a==0)and(b==0):
    zero_zero_count += 1
  elif (a==0):
    zero_one_count += 1
  elif (b==0):
    one_zero_count += 1
  else:
    dd_ba[Fraction(-b, a)] += 1
    dd_ab[Fraction(a, b)] += 1
  

ans = (2**zero_one_count + 2**one_zero_count -1)
flag_dd = defaultdict(bool,{})
for key,value in dd_ba.items():
  if flag_dd[key]:
    continue
  ans *= (2**dd_ab[key] + 2**value - 1) % MOD
  ans %= MOD
  flag_dd[Fraction(key.denominator, -(key.numerator))] = True
  
ans += zero_zero_count - 1
print(ans%MOD)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
from fractions import Fraction
import sys
input = sys.stdin.readline
N=int(input())
mod=10**9+7
dic=defaultdict(int)
c=0
d=0
e=0
for i in range(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:
   dic[Fraction(A,B)]+=1
ans=1
for k in dic:
 if -1/k in dic:
  ans*=(pow(2,dic[k],mod)+pow(2,dic[-1/k],mod) -1)
  ans%=mod
  dic[k]=0
  dic[-1/k]=0
 else:
  ans*=pow(2,dic[k],mod)
  ans%=mod
ans*=(pow(2,c,mod)+pow(2,d,mod)-1)
print((ans-1+e)%mod)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
from fractions import Fraction
import sys
input = sys.stdin.readline
N=int(input())
mod=10**9+7
dic=defaultdict(int)
c=0
d=0
e=0
for i in range(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:
   dic[Fraction(A,B)]+=1
ans=1
for k in dic:
 if -1/k in dic:
  ans*=(pow(2,dic[k],mod)+pow(2,dic[-1/k],mod) -1)
  ans%=mod
  dic[k]=0
  dic[-1/k]=0
 else:
  ans*=pow(2,dic[k],mod)
  ans%=mod
ans*=(pow(2,c,mod)+pow(2,d,mod)-1)
print((ans-1+e)%mod)

Submission status: Time Limit Exceeded

Solution code:
from fractions import Fraction

n = int(input())
a = [list(map(int, input().split())) for i in range(n)]
d = {}
r = 0
for i in range(n):
    k = a[i][0]
    l = a[i][1]
    if k == 0 and l == 0:
        r += 1
    elif k == 0:
        if 0 in d:
            d[0][0] = d[0][0] +1
        else:
            d[0] = [1, 0]
    elif l == 0:
        if 0 in d:
            d[0][1] = d[0][1] +1
        else:
            d[0] = [0, 1]
    else:
        if k * l > 0:
            s = Fraction(k, l)
            if s in d:
                d[s][0] = d[s][0] +1
            else:
                d[s] = [1, 0]
        else:
            s = Fraction(-l, k)
            if s in d:
                d[s][1] = d[s][1] +1
            else:
                d[s] = [0, 1]
ans = 1
m = 0
for i in d:
    m += 1
    ans *= 2**d[i][0] + 2**d[i][1] - 1
    #if m != 1:
        #ans -= 1
    #print(ans)
ans -= 1
ans += r
ans = ans%1000000007
#print(d)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/python3

from fractions import Fraction

M = 1000000007

def normalize(v):
    if v > 0:
        return v
    else:
        return - 1 / v

n = int(input())

vs = {}
zc = 0
azc = 0
bzc = 0

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

    if a == 0:
        azc += 1
        continue

    if b == 0:
        bzc += 1
        continue

    v = Fraction(a, b)
    if v in vs:
        vs[v] += 1
    else:
        vs[v] = 1

wp = set()
for v in vs:
    if - 1 / v in vs:
        wp.add(normalize(v))

#print(zc, azc, bzc, vs, wp)
        
c = 1
if azc == 0 or bzc == 0:
    c = c * pow(2, azc + bzc, M) % M
else:
    c = c * (pow(2, azc, M) - 1 + pow(2, bzc, M) - 1 + 1) % M

r = n - azc - bzc
for p in wp:
    invp = -1 / p
    c = c * (pow(2, vs[p], M) - 1 + pow(2, vs[invp], M) - 1 + 1) % M
    r -= vs[p] + vs[invp]

r -= zc
c = c * pow(2, r, M) % M
c = (c + zc) % M
c = (c - 1) % M

print(c)

Submission status: Time Limit Exceeded

Solution code:
import math
mod = 1000000007
D = {}
X = []
Y = []
zero = 0
N = int(input())
for i in range(N):
    a,b = map(int,input().split())
    if (a,b) == (0,0):
        zero += 1
        continue
    if a < 0 :
        a = -a
        b = -b
    if a == 0:
        b = 1
    elif b == 0:
        a = 1
    else:
        g = math.gcd(a,b)
        a = a//g
        b = b//g
    Y.append([a,b])
    D[(a,b)] = 0
for [a,b] in Y:
    if D[(a,b)] == 0:
        X.append([a,b])
    D[(a,b)] += 1
    
n = N - zero
A = []
for [a,b] in X:
    c = b
    d = -a
    if c < 0:
        c = -c
        d = -d
    x = D[(a,b)]
    y = 0
    if [c,d] in X:
        y = D[(c,d)]
        X.remove([c,d])
    if y > 0:
        A.append([x,y])
        n = n - x - y
ans = 1
for [x,y] in A:
    z = (2**x + 2**y - 1)%mod
    ans *= z
    ans % mod
z = 2**n % mod
ans *= z
ans -= 1
ans %= mod
ans += zero
ans %= mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from fractions import Fraction

n = int(input())
a = [list(map(int, input().split())) for i in range(n)]
d = {}
r = 0
for i in range(n):
    if a[i][0] == 0 and a[i][1] == 0:
        r += 1
    elif a[i][0] == 0:
        if 0 in d:
            d[0][0] = d[0][0] +1
        else:
            d[0] = [1, 0]
    elif a[i][1] == 0:
        if 0 in d:
            d[0][1] = d[0][1] +1
        else:
            d[0] = [0, 1]
    else:
        if a[i][0] * a[i][1] > 0:
            s = Fraction(a[i][0], a[i][1])
            if s in d:
                d[s][0] = d[s][0] +1
            else:
                d[s] = [1, 0]
        else:
            s = Fraction(-a[i][1], a[i][0])
            if s in d:
                d[s][1] = d[s][1] +1
            else:
                d[s] = [0, 1]
ans = 1
m = 0
for i in d:
    m += 1
    ans *= 2**d[i][0] + 2**d[i][1] - 1
    #if m != 1:
        #ans -= 1
    #print(ans)
ans -= 1
ans += r
ans = ans%1000000007
#print(d)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math
mod = 1000000007
D = {}
X = []
zero = 0
N = int(input())
for i in range(N):
    a,b = map(int,input().split())
    if (a,b) == (0,0):
        zero += 1
        continue
    if a < 0 :
        a = -a
        b = -b
    if a == 0:
        b = 1
    else:
        g = math.gcd(a,b)
        a = a//g
        b = b//g
    c = b
    d = -a
    if c < 0:
        c = -c
        d = -d    
    if [a,b] in X:
        D[(a,b)] += 1
    else:
        D[(a,b)] = 1
        X.append([a,b])
n = N - zero
A = []
for [a,b] in X:
    c = b
    d = -a
    if c < 0:
        c = -c
        d = -d
    x = D[(a,b)]
    y = 0
    if [c,d] in X:
        y = D[(c,d)]
        X.remove([c,d])
    if y > 0:
        A.append([x,y])
        n = n - x - y
ans = 1
for [x,y] in A:
    z = (2**x + 2**y - 1)%mod
    ans *= z
    ans % mod
z = 2**n % mod
ans *= z
ans -= 1
ans %= mod
ans += zero
ans %= mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**7)

input = sys.stdin.readline


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

    iwashi = []

    ng_list = []

    iwashi0 = 0
    for i in range(N):
        ai, bi = [int(v) for v in input().split()]
        if ai == 0 and bi == 0:
            iwashi0 += 1
        else:
            iwashi.append((ai, bi))

    N = len(iwashi)
    for i in range(N):
        ng = 0
        ai, bi = iwashi[i]
        for j in range(i + 1, N):
            aj, bj = iwashi[j]
            if ai * aj + bi * bj == 0:
                ng |= 1 << j
        ng_list.append(ng)

    memo = [[{}, {}] for _ in range(N)]

    def search(i, closed, choice):
        if i >= N:
            return choice

        if closed in memo[i][choice]:
            return memo[i][choice][closed]

        count = search(i + 1, closed, choice)
        if (closed & (1 << i)) == 0:
            count += search(i + 1, closed | ng_list[i], 1)

        memo[i][choice][closed] = count
        return count

    count = search(0, 0, 0)
    print(iwashi0 + count)


main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/python3

from fractions import Fraction

M = 1000000007

def normalize(v):
    if v > 0:
        return v
    else:
        return - 1 / v

n = int(input())

vs = {}
wp = set()
zc = 0
azc = 0
bzc = 0

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

    if a == 0:
        azc += 1
        continue

    if b == 0:
        bzc += 1
        continue

    v = Fraction(a, b)
    if v in vs:
        vs[v] += 1
    else:
        vs[v] = 1

    if - 1 / v in vs:
        wp.add(normalize(v))

#print(zc, azc, bzc, vs, wp)
        
c = 1
if azc == 0 or bzc == 0:
    c = c * pow(2, azc + bzc, M) % M
else:
    c = c * (pow(2, azc, M) - 1 + pow(2, bzc, M) - 1 + 1) % M

r = n - azc - bzc
for p in wp:
    invp = -1 / p
    c = c * (pow(2, vs[p], M) - 1 + pow(2, vs[invp], M) - 1 + 1) % M
    r -= vs[p] + vs[invp]

r -= zc
c = c * pow(2, r, M) % M
c = (c + zc) % M
c = (c - 1) % M

print(c)

Submission status: Time Limit Exceeded

Solution code:
import math
mod = 1000000007
D = {}
X = []
zero = 0
N = int(input())
for i in range(N):
    a,b = map(int,input().split())
    if (a,b) == (0,0):
        zero += 1
        continue
    if a < 0 :
        a = -a
        b = -b
    elif a == 0:
        b = 1
    g = math.gcd(a,b)
    a = a//g
    b = b//g
    c = b
    d = -a
    if c < 0:
        c = -c
        d = -d    
    if [a,b] in X:
        D[(a,b)] += 1
    else:
        D[(a,b)] = 1
        X.append([a,b])
n = N - zero
A = []
for [a,b] in X:
    c = b
    d = -a
    if c < 0:
        c = -c
        d = -d
    x = D[(a,b)]
    y = 0
    if [c,d] in X:
        y = D[(c,d)]
        X.remove([c,d])
    if y > 0:
        A.append([x,y])
        n = n - x - y
ans = 1
for [x,y] in A:
    z = (2**x + 2**y - 1)%mod
    ans *= z
    ans % mod
z = 2**n % mod
ans *= z
ans -= 1
ans %= mod
ans += zero
ans %= mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from fractions import Fraction
import sys
input = sys.stdin.readline
N=int(input())
mod=10**9+7
dic={}
c=0
d=0
e=0
for i in range(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:
   x=Fraction(A,B)
   if x in dic:
    dic[x][0]+=1
   elif -1/x in dic:
    dic[-1/x][1]+=1
   else:
    dic[x]=[1,0]
ans=1
for k in dic:
 ans*=(pow(2,dic[k][0],mod)+pow(2,dic[k][1],mod) -1)
 ans%=mod
ans*=(pow(2,c,mod)+pow(2,d,mod)-1)
print((ans-1+e)%mod)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**7)

input = sys.stdin.readline


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

    iwashi = []

    ng_list = []

    for i in range(N):
        ai, bi = [int(v) for v in input().split()]
        iwashi.append((ai, bi))

    for i in range(N):
        ng = 0
        ai, bi = iwashi[i]
        for j in range(i + 1, N):
            aj, bj = iwashi[j]
            if ai * aj + bi * bj == 0:
                ng |= 1 << j
        ng_list.append(ng)

    memo = [[{}, {}] for _ in range(N)]

    def search(i, closed, choice):
        if i >= N:
            return choice

        if closed in memo[i][choice]:
            return memo[i][choice][closed]

        count = search(i + 1, closed, choice)
        if (closed & (1 << i)) == 0:
            count += search(i + 1, closed | ng_list[i], 1)

        memo[i][choice][closed] = count
        return count

    count = search(0, 0, 0)
    print(count)


main()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**7)

input = sys.stdin.readline


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

    iwashi = []

    ng_list = []

    for i in range(N):
        ai, bi = [int(v) for v in input().split()]
        iwashi.append((ai, bi))

    for i in range(N):
        ng = 0
        ai, bi = iwashi[i]
        for j in range(i + 1, N):
            aj, bj = iwashi[j]
            if ai * aj + bi * bj == 0:
                ng |= 1 << j
        ng_list.append(ng)

    memo = [[{}, {}] for _ in range(N)]

    def search(i, closed, choice):
        if i >= N:
            return 1 if choice else 0

        if closed in memo[i][1 if choice else 0]:
            return memo[i][1 if choice else 0][closed]

        count = search(i + 1, closed, choice)
        if (closed & (1 << i)) == 0:
            count += search(i + 1, closed | ng_list[i], True)

        memo[i][1 if choice else 0][closed] = count
        return count

    count = search(0, 0, False)
    print(count)


main()

Submission status: Time Limit Exceeded

Solution code:
from fractions import Fraction
import sys
input = sys.stdin.readline
N=int(input())
mod=10**9+7
dic={}
c=0
d=0
e=0
for i in range(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:
   if Fraction(A,B) in dic:
    dic[Fraction(A,B)]+=1
   else:
    dic[Fraction(A,B)]=1
ans=1
for k in dic:
 if  -1/k in dic:
  ans*=(pow(2,dic[k],mod)+pow(2,dic[-1/k],mod) -1)
  ans%=mod
  dic[k]=0
  dic[-1/k]=0
 else:
  ans*=pow(2,dic[k],mod)
  ans%=mod
ans*=(pow(2,c,mod)+pow(2,d,mod)-1)
print((ans-1+e)%mod)

Submission status: Time Limit Exceeded

Solution code:
from fractions import Fraction
import sys
input = sys.stdin.readline
N=int(input())
mod=10**9+7
dic={}
c=0
d=0
e=0
for i in range(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:
   x=Fraction(A,B)
   if x in dic:
    dic[x]+=1
   else:
    dic[x]=1
ans=1
for k in dic:
 if  -1/k in dic:
  ans*=(pow(2,dic[k],mod)+pow(2,dic[-1/k],mod) -1)
  ans%=mod
  dic[k]=0
  dic[-1/k]=0
 else:
  ans*=pow(2,dic[k],mod)
  ans%=mod
ans*=(pow(2,c,mod)+pow(2,d,mod)-1)
print((ans-1+e)%mod)

Submission status: Time Limit Exceeded

Solution code:
from fractions import Fraction
import sys
input = sys.stdin.readline
def powmod(x, n,mod):
  if n == 0:
   return 1
  K = 1
  while n > 1:
   if n % 2 != 0:
    K = K * x%mod
    x = x ** 2%mod
    n = (n - 1) // 2
   else:
    x = x ** 2%mod
    n = n // 2%mod

  return K * x # 指数を割り続け n が 1 に至ったら終了
N=int(input())
mod=10**9+7
dic={}
c=0
d=0
e=0
for i in range(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:
   x=Fraction(A,B)
   if x in dic:
    dic[x]+=1
   else:
    dic[x]=1
ans=1
for k in dic:
 if  -1/k in dic:
  ans*=(powmod(2,dic[k],mod)+powmod(2,dic[-1/k],mod) -1)
  ans%=mod
  dic[k]=0
  dic[-1/k]=0
 else:
  ans*=powmod(2,dic[k],mod)
  ans%=mod
ans*=(powmod(2,c,mod)+powmod(2,d,mod)-1)
print((ans-1+e)%mod)

Submission status: Time Limit Exceeded

Solution code:
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
 
from collections import defaultdict, deque
from sys import exit
import math
import copy
from bisect import bisect_left, bisect_right
from heapq import *
import sys
# sys.setrecursionlimit(1000000)
INF = 10 ** 17
MOD = 1000000007
 
from fractions import *
def inverse(f):
    # return Fraction(f.denominator,f.numerator)
    return 1/f
 
 
def combmod(n, k, mod=MOD):
    ret = 1
    for i in range(n - k + 1, n + 1):
        ret *= i
        ret %= mod
 
    for i in range(1, k + 1):
        ret *= pow(i, mod - 2, mod)
        ret %= mod
 
    return ret
 
def solve():
    n = getN()
    iwashis = []
    zz = 0
    fr = defaultdict(int)
    for i in range(n):
        iw = getList()
        if iw[0] == 0 and iw[1] == 0:
            zz += 1
            continue
        if iw[0] != 0:
            fr[Fraction(iw[1], iw[0])] += 1
            # fr[iw[1]/iw[0]] += 1
        else:
            fr["INF"] += 1
 
    used = defaultdict(int)
    ans = 1
    for k, v in fr.items():
        if k in used:
            continue
        if k == "INF":
            if 0 in fr:
                ans *= pow(2, v, MOD) + pow(2, fr[0], MOD) - 1
                ans %= MOD
            else:
                ans *= pow(2, v, MOD)
                ans %= MOD
            used[0] += 1
        elif k != 0:
            if - inverse(k) in fr:
                ans *= pow(2, v, MOD) + pow(2, fr[- inverse(k)], MOD) - 1
                ans %= MOD
            else:
                ans *= pow(2, v, MOD)
                ans %= MOD
            used[- inverse(k)] += 1
        elif k == 0:
            if "INF" in fr:
                ans *= pow(2, v, MOD) + pow(2, fr["INF"], MOD) - 1
                ans %= MOD
            else:
                ans *= pow(2, v, MOD)
                ans %= MOD
            used["INF"] += 1
        # print(k, v, ans, -inverse(k))
    # print(fr)
    print((ans-1+zz) % MOD)
    # print(Fraction(0, ???1) == 0)
    # print(10 / 10**18 == inverse(10**17))
    # print(1/2 == (5 * 10 ** 18) / 10 ** 19)
 
 
def main():
    n = getN()
    for _ in range(n):
        solve()
if __name__ == "__main__":
    solve()

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
from decimal import Decimal, ROUND_HALF_UP, ROUND_HALF_EVEN
from collections import deque
from bisect import bisect_left
from itertools import product
def I(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LI2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
#文字列を一文字ずつ数字に変換、'5678'を[5,6,7,8]とできる
def LSI(): return list(map(int, list(sys.stdin.readline().rstrip())))
def LSI2(N): return [list(map(int, list(sys.stdin.readline().rstrip()))) for i in range(N)]
#文字列として取得
def ST(): return sys.stdin.readline().rstrip()
def LST(): return sys.stdin.readline().rstrip().split()
def LST2(N): return [sys.stdin.readline().rstrip().split() for i in range(N)]
def FILL(i,h): return [i for j in range(h)]
def FILL2(i,h,w): return [FILL(i,w) for j in range(h)]
def FILL3(i,h,w,d): return [FILL2(i,w,d) for j in range(h)]
def FILL4(i,h,w,d,d2): return [FILL3(i,w,d,d2) for j in range(h)]
def sisha(num,digit): return Decimal(str(num)).quantize(Decimal(digit),rounding=ROUND_HALF_UP)
#'0.01'や'1E1'などで指定、整数に戻すならintをかます
MOD = 1000000007
INF = float("inf")
sys.setrecursionlimit(10**6+10)

from fractions import Fraction

N = I()
cnt = {}
pair = {}
bothzero = 0
for i in range(N):
    A,B = MI()
    if A==0 and B==0:
        bothzero += 1
    elif B==0:
        pair[0]=pair.get(0,0)+1
    elif A == 0:
        cnt[0]=cnt.get(0,0)+1
    elif A/B>0:
        frac = Fraction(A,B)
        cnt[frac]=cnt.get(frac,0)+1
    else:
        frac = Fraction(-B,A)
        pair[frac]=pair.get(frac,0)+1
res = N-bothzero
ans = 1
for v in cnt:
    if pair.get(v,0)==0:
        continue
    res -= (cnt[v]+pair[v])
    ans = ans*((pow(2,cnt[v],MOD)+pow(2,pair[v],MOD)-1)%MOD)
    ans = ans%MOD
ans = (ans*pow(2,res,MOD)-1)%MOD
ans = (ans+bothzero)%MOD
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
from fractions import Fraction
import sys

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

dict_F = {}
count_0 = 0

def insert(A,B,s): # A>=0, B>0, s=0or1
  if Fraction(A,B) not in dict_F.keys():
    dict_F[Fraction(A,B)] = [0,0]
  dict_F[Fraction(A,B)][s] += 1

def make_power2(N):
  result = 1
  list_result = [1]
  for _ in range(N):
    result = (2*result)%mod
    list_result.append(result)
  return list_result

for i in range(N):
  A,B = AB[2*i], AB[2*i+1]
  if A==0 and B==0:
    count_0 += 1
  elif A>=0 and B>0:
    insert(A,B,0)
  elif A>0 and B<=0:
    insert(-B,A,1)
  elif A<=0 and B<0:
    insert(-A,-B,0)
  elif A<0 and B>=0:
    insert(B,-A,1)

mod = 1000000007
power2 = make_power2(N)
answer = 1

for A,B in dict_F.values():
  answer = (answer*(power2[A]+power2[B]-1))%mod
answer = (answer+count_0-1)%mod

print(answer)

Submission status: Time Limit Exceeded

Solution code:
import sys
# import numpy as np

def I():
	return int(sys.stdin.readline().rstrip())

def IL():
	return list(map(int, sys.stdin.readline().rstrip().split()))

def dot(a, b):
	return a[0] * b[0] + a[1] * b[1]

def main():
	N = I()
	ab = [[0, 0] for _ in range(N)]
	bad_pairs = []
	for i in range(N):
		ab[i][0], ab[i][1] = IL()

	for i in range(N):
		for j in range(i+1, N):
			if dot(ab[i], ab[j]) == 0.0:
				bad_pairs.append([i, j])
	
	pairs = 0
	good_pairs = []
	for i in range(1, 2**N):
		bag = []
		for j in range(N):
			if (i>>j) & 1:
				bag.append(j)
		is_good = 1
		for bp in bad_pairs:
			if set(bp).issubset(set(bag)):
				is_good = 0
				break
		if is_good:
			pairs += 1
			good_pairs.append(bag)
	# print(good_pairs)
	print(pairs)

if __name__ == "__main__":
	main()

Submission status: Time Limit Exceeded

Solution code:
import sys; input = sys.stdin.buffer.readline
from collections import defaultdict
from fractions import gcd
con = 10 ** 9 + 7; INF = float("inf")

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

#処理内容
def main():
	N = int(input())
	AB = []
	D = defaultdict(int)
	DJ = defaultdict(int)
	d0x = 0; dx0 = 0; d00 = 0
	for i in range(N):
		A, B = getlist()
		if A == 0 and B == 0:
			d00 += 1
		elif A == 0:
			dx0 += 1
		elif B == 0:
			d0x += 1
		else:
			GCD = gcd(A, B)
			a = int(A // GCD)
			b = int(B // GCD)
			if a < 0:
				a = -a
				b = -b
			AB.append([a, b])
			D[(a, b)] += 1
			DJ[(a, b)] = 1

	ans = 1

	for a, b in AB:
		a2 = b; b2 = -a
		if a2 < 0:
			a2 = -a2; b2 = -b2
		if DJ[(a, b)] >= 0 and DJ[(a2, b2)] >= 0:
			DJ[(a, b)] = -1
			DJ[(a2, b2)] = -1
			X = D[(a, b)]
			Y = D[(a2, b2)]
			ans *= pow(2, X, con) + pow(2, Y, con) - 1
			ans %= con

	ans *= (pow(2, d0x, con) + pow(2, dx0, con)) - 1
	ans += d00
	ans %= con

	if ans == 0:
		print(10 ** 9  + 6)
	else:
		print(ans - 1)

if __name__ == '__main__':
	main()

Submission status: Time Limit Exceeded

Solution code:
import sys
import numpy as np

def I():
	return int(sys.stdin.readline().rstrip())

def IL():
	return list(map(int, sys.stdin.readline().rstrip().split()))

def main():
	N = I()
	ab = np.zeros((N, 2))
	bad_pairs = []
	for i in range(N):
		ab[i] = IL()

	for i in range(N):
		for j in range(i+1, N):
			if ab[i].dot(ab[j]) == 0.0:
				bad_pairs.append([i, j])
	
	pairs = 0
	good_pairs = []
	for i in range(1, 2**N):
		bag = []
		for j in range(N):
			if (i>>j) & 1:
				bag.append(j)
		is_good = 1
		for bp in bad_pairs:
			if set(bp).issubset(set(bag)):
				is_good = 0
				break
		if is_good:
			pairs += 1
			good_pairs.append(bag)
	# print(good_pairs)
	print(pairs)

if __name__ == "__main__":
	main()

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
li=[]
for _ in range(n):
    li.append(list(map(int, input().split())))

bad_set = set([(i,j) for i in range(n) for j in range(i+1, n) if li[i][0]*li[j][0]+li[i][1]*li[j][1]==0])
ans=2**n-1
add_set = bad_set.copy()
for cnt in range(n):
    bad2_set = bad_set.copy()
    if cnt%2==0:
        ans -= sum([2**(n-len(s)) for s in add_set])
    else:
        ans += sum([2**(n-len(s)) for s in add_set])
    add_set = set([])
    for a in bad_set:
        bad2_set.remove(a)
        for b in bad2_set:
            a, b = set(a), set(b)
            if a!=b and (tuple(a|b) not in bad_set):
                add_set.add(tuple(a|b))
    
    bad_set = (bad_set | add_set)
    if len(add_set)==0:
        break
print(ans)