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:
# -*- coding: utf-8 -*-

import itertools
# スペース区切りの整数の入力
#N, K = map(int, input().split())
# 文字列の入力
N = int(input())
#開業されたN個要素を受け付ける
#list = [input() for i in range(N)]
input_list = [list(map(int, input().split())) for i in range(N)]

bad_list = []
#print(input_list)
for i, input in enumerate(input_list):
    for j in range(i):
        #print(j, i)
        if input_list[i][0]*input_list[j][0] + input_list[i][1]*input_list[j][1] == 0:
            bad_list.append([j+1, i+1])

#print(bad_list)
ans = 0
num_list=[i+1 for i in range(N)]
#print(num_list)
flg=0
for i in range(N+1):
    if i == 0:
        continue
    c = list(itertools.combinations(num_list, i))
    for l in c:
        flg=0
        for j in bad_list:
            if (j[0] in l and j[1] in l):
                flg=1
        if flg==0:
            ans = ans+1

print(ans)

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()

"""
    12
    3 2
    3 2
    0 1
    2 -1
    -3 -9
    -8 12
    7 0
    8 1
    8 2
    8 4
    0 0
    0 0
"""

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 * (10 ** 19) + b] += 1
			DJ[a * (10 ** 19) + b] = 1


	ans = 1

	for a, b in AB:
		a2 = b; b2 = -a
		if a2 < 0:
			a2 = -a2; b2 = -b2
		if DJ[a * (10 ** 19) + b] >= 0 and DJ[a2 * (10 ** 19) + b2] >= 0:
			DJ[a * (10 ** 19) + b] = -1
			DJ[a2 * (10 ** 19) + b2] = -1
			X = D[a * (10 ** 19) + b]
			Y = D[a2 * (10 ** 19) + 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:
n = int(input())
ab = [list(map(int, input().split())) for _ in range(n)]

mod = 1000000007

from fractions import gcd

ratios = []
nzero = 0
for a, b in ab:
    if a != 0 and b != 0:
        g = gcd(a, b)
        ratios.append((a // g, b // g))
    elif a == 0 and b == 0:
        nzero += 1
    elif a == 0:
        ratios.append((0, 1))
    else:
        ratios.append((1, 0))

twos = [1]
for i in range(2 * 10 ** 5):
    tmp = twos[-1] * 2
    tmp %= mod
    twos.append(tmp)


from collections import Counter, defaultdict
c = Counter(ratios)
seen = Counter()

targets = []
for key in c:
    x, y = key
    xx = c[key]
    if y != 0:
        yy = seen[(-y, x)] + seen[(y, -x)]
    else:
        yy = seen[(-y, x)]
    if xx != 0 and yy != 0:
        targets.append((xx, yy))
    seen[key] = c[key]

n_frees = 0
for i, (x, y) in enumerate(ratios):
    n_bads = c[(-y, x)] + c[(y, -x)]
    if n_bads == 0:
        n_frees += 1

ans = twos[n_frees]

for x, y in targets:
    ans *= (twos[x] + twos[y] - 1) % mod

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

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])
minus_sum = 0
add_set = bad_set.copy()
for cnt in range(n):
    bad2_set = bad_set.copy()
    if cnt%2==0:
        minus_sum += sum([2**(n-len(s)) for s in add_set])
    else:
        minus_sum -= 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
ans = 2**n - minus_sum -1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from fractions import Fraction
n=int(input())

zero=0
plus=[]
minus=[]

for i in range(n):
    a,b=map(int,input().split())
    if(a*b>0):
        plus.append(Fraction(a,b))
    elif(a*b<0):
        minus.append(Fraction(-b,a))
    else:
        if(a==0 and b==0):
            zero+=1
        elif(a==0):
            plus.append(Fraction(0,1))
        else:
            minus.append(Fraction(0,1))

plus.sort()
minus.sort()

kazu=n-zero

pl=len(plus)
ml=len(minus)
#print(kazu)
#print(plus)
#print(minus)

#kyoutu=list(set(plus) & set(minus))
#kyoutu.sort()

kyoutu=[]

gen=0
start=0
for i in range(pl):
    start=gen
    for j in range(start,ml):
        if(plus[i]==minus[j]):
            kyoutu.append(plus[i])
        elif(plus[i]<minus[j]):
            break
        gen+=1

kyoutu=list(set(kyoutu))
kyoutu.sort()
#print(kyoutu)

tyohuku=[[0,0]for i in range(len(kyoutu))]

gen=0
start=0
for i in range(len(kyoutu)):
    #print("check",kyoutu[i],start)
    gen=start
    for j in range(gen,pl):
        #print(plus[j])
        
        if(plus[j]==kyoutu[i]):
            tyohuku[i][0]+=1
        elif(plus[j]>kyoutu[i]):
            break
        start+=1

gen=0
start=0
for i in range(len(kyoutu)):
    #print("check",kyoutu[i],start)
    gen=start
    for j in range(gen,ml):
        #print(minus[j])
        
        if(minus[j]==kyoutu[i]):
            tyohuku[i][1]+=1
        elif(minus[j]>kyoutu[i]):
            break
        start+=1

#print(tyohuku)

oks=[0]*len(kyoutu)

ruijo=[]

sosu=1000000007
temp=1
for i in range(kazu+1):
    ruijo.append(temp)
    temp*=2
    temp%=sosu

#print(ruijo)

nokori=kazu

for i in range(len(kyoutu)):
    nokori-=tyohuku[i][0]+tyohuku[i][1]
    oks[i]=ruijo[tyohuku[i][0]]+ruijo[tyohuku[i][1]]-1
    oks[i]%=sosu

ans=ruijo[nokori]

for o in oks:
    ans*=o
    ans%=sosu

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

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
n = int(input().strip())
mod = 10**9+7
ab = [list(map(int,input().split())) for _ in range(n)]
hate = [[] for _ in range(n)]
for i in range(n-1):
  a1,b1 = ab[i]
  for j in range(i+1,n):
    a2,b2 = ab[j]
    if a1*a2+b1*b2 == 0:
      hate[i].append(j)
      hate[j].append(i)
check = [False]*n
#hate_set = []
eok = n
ans = 1
for i in range(n):
  if not check[i]:
    h1 = len(hate[i])
    if len(hate[i])!=0:
      h2 = len(hate[hate[i][0]])
      #hate_set.append((h1,h2))
      ans *= 1+h1*(h1+1)//2+h2*(h2+1)//2
      eok -= h1+h2
      for j in hate[i]:
        check[j] = True
      for j in hate[hate[i][0]]:
        check[j] = True
print(ans*(2**eok)-1)

Submission status: Time Limit Exceeded

Solution code:
from fractions import Fraction
n=int(input())

zero=0
plus=[]
minus=[]

for i in range(n):
    a,b=map(int,input().split())
    if(a*b>0):
        plus.append(Fraction(a,b))
    elif(a*b<0):
        minus.append(Fraction(-b,a))
    else:
        if(a==0 and b==0):
            zero+=1
        elif(a==0):
            plus.append(Fraction(0,1))
        else:
            minus.append(Fraction(0,1))

plus.sort()
minus.sort()

kazu=n-zero

pl=len(plus)
ml=len(minus)
#print(kazu)
#print(plus)
#print(minus)

#kyoutu=list(set(plus) & set(minus))
#kyoutu.sort()

kyoutu=[]

gen=0
start=0
for i in range(pl):
    start=gen
    for j in range(start,ml):
        if(plus[i]==minus[j]):
            kyoutu.append(plus[i])
        elif(plus[i]<minus[j]):
            break
        gen+=1

kyoutu=list(set(kyoutu))
kyoutu.sort()
#print(kyoutu)

tyohuku=[[0,0]for i in range(len(kyoutu))]

gen=0
start=0
for i in range(len(kyoutu)):
    #print("check",kyoutu[i],start)
    gen=start
    for j in range(gen,pl):
        #print(plus[j])
        
        if(plus[j]==kyoutu[i]):
            tyohuku[i][0]+=1
        elif(plus[j]>kyoutu[i]):
            break
        start+=1

gen=0
start=0
for i in range(len(kyoutu)):
    #print("check",kyoutu[i],start)
    gen=start
    for j in range(gen,ml):
        #print(minus[j])
        
        if(minus[j]==kyoutu[i]):
            tyohuku[i][1]+=1
        elif(minus[j]>kyoutu[i]):
            break
        start+=1

#print(tyohuku)

oks=[0]*len(kyoutu)

ruijo=[]

sosu=1000000007
temp=1
for i in range(n+1):
    ruijo.append(temp)
    temp*=2
    temp%=sosu

#print(ruijo)

nokori=kazu

for i in range(len(kyoutu)):
    nokori-=tyohuku[i][0]+tyohuku[i][1]
    oks[i]=ruijo[tyohuku[i][0]]+ruijo[tyohuku[i][1]]-1
    oks[i]%=sosu

ans=ruijo[nokori]

for o in oks:
    ans*=o
    ans%=sosu

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

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
import itertools
N = int(input())
ab = [list(map(int, input().split())) for n in range(N)]

comb2 = list(itertools.combinations(range(N), 2))
badcomb = list()

for c in comb2:
  i = c[0]
  j = c[1]
  if ab[i][0]*ab[j][0]+ab[i][1]*ab[j][1] == 0:
    badcomb.append(c)
  

count = N + len(comb2) -len(badcomb)
for n in range(3, N+1):
  combn = list(itertools.combinations(range(N), n))
  prevc = count
  count += len(combn)
  for c in combn:
    for bc in badcomb:
      if set(bc) <= set(c):
        count -= 1
        break
  if count == prevc:
    break

r = count % 1000000007
print(r)

Submission status: Time Limit Exceeded

Solution code:
import sys
import io, os
input = io.BytesIO(os.read(0,os.fstat(0).st_size)).readline
from collections import Counter
from fractions import Fraction

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

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

def main():
    C=Counter()
    PLUS=0
    for a,b in S:
        if a==0 and b==0:
            PLUS+=1
        elif b!=0:
            C[Fraction(a,b)]+=1
        else:
            C[float("inf")]+=1
        
    ANS=1

    for x in list(C.keys()):
        if x!=float("inf") and x!=Fraction(0,1):
            n=x.numerator
            d=x.denominator

            ANS=ANS*(pow(2,C[x],mod)+pow(2,C[Fraction(-d,n)],mod)-1)%mod

            C[x]=0
            C[Fraction(-d,n)]=0
            
        else:
            ANS=ANS*(pow(2,C[float("inf")],mod)+pow(2,C[Fraction(0,1)],mod)-1)%mod

            C[float("inf")]=0
            C[Fraction(0,1)]=0

    print((ANS-1+PLUS)%mod)

main()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import itertools


def func(comb, ngList):
    _res = [False for ng in ngList if ng[0] in comb and ng[1] in comb]
    if len(_res) == 0:
        return True
    else:
        return False


n = int(input())
x = np.zeros((n, 2))
for i in range(n):
    _tmp = input()
    x[i, 0], x[i, 1] = [float(f) for f in _tmp.split(" ")]

counter = n
ngList = []
for i, j in itertools.combinations(np.arange(n), 2):
    res = x[i, 0] * x[j, 0] + x[i, 1] * x[j, 1]
    if res == 0:
        ngList.append([i, j])

for m in range(2, n + 1):
    res = [func(comb, ngList) for comb in itertools.combinations(np.arange(n), m)]

    counter += sum(res)

print(counter % 1000000007)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline

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

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

from collections import Counter
from fractions import Fraction
C=Counter()
PLUS=0
for a,b in S:
    if a==0 and b==0:
        PLUS+=1
    elif b!=0:
        C[Fraction(a,b)]+=1
    else:
        C[float("inf")]+=1
    
ANS=1

for x in list(C.keys()):
    if x!=float("inf") and x!=Fraction(0,1):
        n=x.numerator
        d=x.denominator

        ANS=ANS*(pow(2,C[x],mod)+pow(2,C[Fraction(-d,n)],mod)-1)%mod

        C[x]=0
        C[Fraction(-d,n)]=0
        
    else:
        ANS=ANS*(pow(2,C[float("inf")],mod)+pow(2,C[Fraction(0,1)],mod)-1)%mod

        C[float("inf")]=0
        C[Fraction(0,1)]=0

print((ANS-1+PLUS)%mod)

Submission status: Time Limit Exceeded

Solution code:
from fractions import Fraction
n=int(input())

zero=0
plus=[]
minus=[]

for i in range(n):
    a,b=map(int,input().split())
    if(a*b>0):
        plus.append(Fraction(a,b))
    elif(a*b<0):
        minus.append(Fraction(-b,a))
    else:
        if(a==0 and b==0):
            zero+=1
        elif(a==0):
            plus.append(Fraction(0,1))
        else:
            minus.append(Fraction(0,1))

plus.sort()
minus.sort()

kazu=n-zero

pl=len(plus)
ml=len(minus)
#print(kazu)
#print(plus)
#print(minus)

kyoutu=list(set(plus) & set(minus))
kyoutu.sort()


tyohuku=[[0,0]for i in range(len(kyoutu))]

gen=0
start=0
for i in range(len(kyoutu)):
    #print("check",kyoutu[i],start)
    gen=start
    for j in range(gen,pl):
        #print(plus[j])
        
        if(plus[j]==kyoutu[i]):
            tyohuku[i][0]+=1
        elif(plus[j]>kyoutu[i]):
            break
        start+=1

gen=0
start=0
for i in range(len(kyoutu)):
    #print("check",kyoutu[i],start)
    gen=start
    for j in range(gen,ml):
        #print(minus[j])
        
        if(minus[j]==kyoutu[i]):
            tyohuku[i][1]+=1
        elif(minus[j]>kyoutu[i]):
            break
        start+=1

#print(tyohuku)

oks=[0]*len(kyoutu)

ruijo=[]

sosu=1000000007
temp=1
for i in range(n+1):
    ruijo.append(temp)
    temp*=2
    temp%=sosu

#print(ruijo)

nokori=kazu

for i in range(len(kyoutu)):
    nokori-=tyohuku[i][0]+tyohuku[i][1]
    oks[i]=ruijo[tyohuku[i][0]]+ruijo[tyohuku[i][1]]-1
    oks[i]%=sosu

ans=ruijo[nokori]

for o in oks:
    ans*=o
    ans%=sosu

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

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])
minus_sum = 0
add_set = bad_set.copy()
for cnt in range(n):
    if cnt%2==0:
        minus_sum += sum([2**(n-len(s)) for s in add_set])
    else:
        minus_sum -= sum([2**(n-len(s)) for s in add_set])
    add_set = set([])
    for a in bad_set:   
        for b in bad_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
ans = 2**n - minus_sum -1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
M = 1000000007

from fractions import Fraction

N = int(input())

ab_zero_count = 0
a_zero_count = 0
b_zero_count = 0

fish_list = []
for _ in range(N):
	a, b = map(int, input().split())
	if a == 0 and b == 0:
		ab_zero_count += 1
	elif a == 0:
		a_zero_count += 1
	elif b == 0:
		b_zero_count += 1
	else:
		fish_list.append(Fraction(a, b))

#print(fish_list)

fish_table = {}
for f in fish_list:
	if f in fish_table:
		fish_table[f] += 1
	else:
		fish_table[f] = 1

fish_count_list = list(fish_table.items())
fish_index_table = {}
for i, (f, c) in enumerate(fish_count_list):
	fish_index_table[(f.numerator, f.denominator)] = i

#print(fish_count_list)

singles = 0
pair_list = []
checked = [False] * N

for i, (f, c) in enumerate(fish_count_list):
	x = -1 / f
	key = (x.numerator, x.denominator)
	if key in fish_index_table:
		j = fish_index_table[key]
		if checked[j] == False:
			f2, c2 = fish_count_list[j]
			pair_list.append((c, c2))
			checked[i] = True
	else:
		singles += c

if a_zero_count > 0 and b_zero_count > 0:
	pair_list.append((a_zero_count, b_zero_count))
else:
	singles += a_zero_count + b_zero_count

count = pow(2, singles, M)

#print(singles, pair_list, a_zero_count, b_zero_count)

for c1, c2 in pair_list:
	count = (count * (pow(2, c1, M) + pow(2, c2, M) - 1)) % M

count += ab_zero_count
count -= 1

print(count % M)

Submission status: Time Limit Exceeded

Solution code:
import itertools

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

for com in itertools.combinations(list(range(N)),2):
    if ABs[com[0]][0]*ABs[com[1]][0] + ABs[com[0]][1]*ABs[com[1]][1] == 0:
        hate.append(list(com))

cnt = 0
for p in itertools.product([0,1],repeat = N):
    if sum(p)==0:
        continue
    for h in hate:
        if p[h[0]]==p[h[1]]==1:
            break
    else:
        cnt += 1
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import itertools

n = int(input())
x = np.zeros((n, 2))
for i in range(n):
    _tmp = input()
    x[i, 0], x[i, 1] = [float(f) for f in _tmp.split(" ")]

counter = n
ngList = []
for i, j in itertools.combinations(np.arange(n), 2):
    res = x[i, 0] * x[j, 0] + x[i, 1] * x[j, 1]
    if res == 0:
        ngList.append([i, j])

for m in range(2, n + 1):
    for comb in itertools.combinations(np.arange(n), m):
        res = [False for ng in ngList if ng[0] in comb and ng[1] in comb]
        if len(res) == 0:
            counter += 1

print(counter % 1000000007)

Submission status: Time Limit Exceeded

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

li = np.array(li)
bad_set = set([(i,j) for i in range(n) for j in range(i+1, n) if np.dot(li[i],li[j])==0])
cnt = 0
minus_sum = 0
add_set = bad_set.copy()
while True:
    if cnt%2==0:
        minus_sum += sum([2**(n-len(s)) for s in add_set])
    else:
        minus_sum -= sum([2**(n-len(s)) for s in add_set])
    add_set = set([])
    for a in bad_set:   
        for b in bad_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)
    cnt += 1
    if len(add_set)==0:
        break
ans = 2**n - minus_sum -1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-

mod = 1000000007

N = int(input())

A_list = [0 for n in range(N)]
B_list = [0 for n in range(N)]
iwashi_aishou = [[True for n in range(N)] for n in range(N)]
for n in range(N):
    A_list[n], B_list[n] = map(int, input().split())

for n in range(N):
    for i in range(n):
        if (A_list[n]*A_list[i])+(B_list[n]*B_list[i]) == 0:
            iwashi_aishou[n][i] = False

def baaino_kazu(idx_list):
    if len(idx_list) == 1:
        return 2
    else:
        max_idx = idx_list[-1]
        # max_idxを入れない場合
        kazu_without_maxidx = baaino_kazu(idx_list[:-1])
        # max_idxを入れる場合
        waru_aishou = [i for i in range(max_idx) if iwashi_aishou[max_idx][i] == False]
        waru_aishou.append(max_idx)
        nokori = list(set(idx_list) - set(waru_aishou))
        nokori.sort()
        kazu_with_maxidx = baaino_kazu(nokori)

        return (kazu_with_maxidx+kazu_without_maxidx)%mod

print(baaino_kazu([i for i in range(N)])-1)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())

count = 0
iwashi = []
for i in range(n):
    iwashi.append(list(map(int, input().split())))

ng = []
for i in range(n - 1):
    for j in range(i + 1, n):
        if iwashi[i][0] * iwashi[j][0] + iwashi[i][1] * iwashi[j][1] == 0:
            ng.append([i, j])

count = 0
for i in range(3, 2 ** n):
    for j in ng:
        if (i >> j[0]) & 1 and (i >> j[1]) & 1:
            count += 1
            break

print((2 ** n - 1 - count) % 1000000007)

Submission status: Time Limit Exceeded

Solution code:
M = 1000000007

from fractions import Fraction
from bisect import bisect_left

N = int(input())

ab_zero_count = 0
a_zero_count = 0
b_zero_count = 0

fish_list = []
for _ in range(N):
	a, b = map(int, input().split())
	if a == 0 and b == 0:
		ab_zero_count += 1
	elif a == 0:
		a_zero_count += 1
	elif b == 0:
		b_zero_count += 1
	else:
		fish_list.append(Fraction(a, b))

#print(fish_list)

fish_table = {}
for f in fish_list:
	if f in fish_table:
		fish_table[f] += 1
	else:
		fish_table[f] = 1

fish_count_list = list(fish_table.items())
fish_count_list.sort()
fish_count_only_list = [f for f, c in fish_count_list]

#print(fish_count_list)

singles = 0
pair_list = []
checked = [False] * N

for i, (f, c) in enumerate(fish_count_list):
	x = -1 / f
	j = bisect_left(fish_count_only_list, x)
	if j != len(fish_count_only_list) and fish_count_only_list[j] == x:
		if checked[j] == False:
			f2, c2 = fish_count_list[j]
			pair_list.append((c, c2))
			checked[i] = True
	else:
		singles += c

if a_zero_count > 0 and b_zero_count > 0:
	pair_list.append((a_zero_count, b_zero_count))
else:
	singles += a_zero_count + b_zero_count

count = pow(2, singles, M)

#print(singles, pair_list, a_zero_count, b_zero_count)

for c1, c2 in pair_list:
	count = (count * (pow(2, c1, M) + pow(2, c2, M) - 1)) % M

count += ab_zero_count
count -= 1

print(count % M)

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()]
        ng = 0
        for j, (aj, bj) in enumerate(iwashi):
            if ai * aj + bi * bj == 0:
                ng |= 1 << j
        iwashi.append((ai, bi))
        ng_list.append(ng)

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

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

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


main()

Submission status: Time Limit Exceeded

Solution code:
n = int(input())

count = 0
iwashi = []
for i in range(n):
    iwashi.append(list(map(int, input().split())))

ng = []
for i in range(n - 1):
    for j in range(i + 1, n):
        if iwashi[i][0] * iwashi[j][0] + iwashi[i][1] * iwashi[j][1] == 0:
            ng.append([i, j])

count = 0
for i in range(3, 2 ** n):
    for j in ng:
        if (i >> j[0]) & 1 and (i >> j[1]) & 1:
            count += 1
            break

print(2 ** n - 1 - count)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
from fractions import Fraction
MOD = 10 ** 9 + 7
N = int(input())
ct = Counter()
Azero = 0
Bzero = 0
Allzero = 0
for _ in range(N):
    a, b = map(int, input().split())
    if a == b == 0:
        Allzero += 1
    elif a == 0:
        Azero += 1
    elif b == 0:
        Bzero += 1
    else:
        f = Fraction(a, b)
        ct[f] += 1
ans = pow(2, Azero, MOD) + pow(2, Bzero, MOD) - 1
ans %= MOD
visited = set()
for f in ct.keys():
    if f in visited:
        continue
    inv = Fraction(-f.denominator, f.numerator)
    visited.add(f)
    visited.add(inv)
    tmp = pow(2, ct[f], MOD) + pow(2, ct[inv], MOD) - 1
    ans *= tmp
    ans %= MOD
ans += Allzero
print((ans-1) % MOD)

Submission status: Time Limit Exceeded

Solution code:
# ABC168 E ∙ (Bullet)
import itertools

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

ng_list = []

for i in range(n):
    for j in range(i+1,n,1):
        if ab_list[i][0] * ab_list[j][0] + ab_list[i][1] * ab_list[j][1] == 0:
            ng_list.append([i,j])

_iter = itertools.product([0,1],repeat=n)
ans = 0
for _ in _iter:
    for _l in ng_list:
        if _[_l[0]] + _[_l[1]] == 2:
            break
    else:
        ans += 1
        
print(ans-1)

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):
        A, B = [int(v) for v in input().split()]
        iwashi.append((A, B))

    for i in range(N):
        ng = 0
        a = iwashi[i]
        for j in range(i):
            b = iwashi[j]
            if a[0] * b[0] + a[1] * b[1] == 0:
                ng |= 1 << j
        ng_list.append(ng)

    def is_ok(i, closed):
        return ng_list[i] & closed == 0

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

        count = search(i + 1, closed)
        if is_ok(i, closed):
            count += search(i + 1, closed | (1 << i))
        return count

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


main()

Submission status: Time Limit Exceeded

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


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

    iwashi = []

    ng_list = []

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

    def is_ng(i, j):
        a = iwashi[i]
        b = iwashi[j]
        return a[0] * b[0] + a[1] * b[1] == 0

    for i in range(N):
        ng = 0
        for j in range(i):
            a = iwashi[i]
            b = iwashi[j]
            if a[0] * b[0] + a[1] * b[1] == 0:
                ng |= 1 << j
        ng_list.append(ng)

    def is_ok(i, closed):
        return ng_list[i] & closed == 0

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

        count = search(i + 1, closed)
        if is_ok(i, closed):
            count += search(i + 1, closed | (1 << i))
        return count

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


main()

Submission status: Time Limit Exceeded

Solution code:
import sys
from fractions import Fraction
mod = 1000000007

def solve():
    input = sys.stdin.readline
    N = int(input())
    F = [[int(i) for i in input().split()] for _ in range(N)]
    D = dict()
    zero, inf, ng = 0, 0, 0
    for x, y in F:
        if x == 0 and y == 0: ng += 1
        elif x == 0: inf += 1
        elif y == 0: zero += 1
        else: 
            tan = Fraction(y, x)
            if tan in D: D[tan] += 1
            else: D[tan] = 1

    ans = 1
    ans *= (pow(2, zero, mod) + pow(2, inf, mod) - 1) % mod
    ans %= mod
    used = set()
    for key in D:
        if key not in used:
            this = D[key]
            used |= {key}
            ne, de = key.numerator, key.denominator
            op = (0 if Fraction(-de, ne) not in D else D[Fraction(-de, ne)])
            used |= {Fraction(-de, ne)}
            select = (pow(2, this, mod) + pow(2, op, mod) - 1) % mod
            ans *= select
            ans %= mod
    ans += ng
    ans %= mod
    ans = (ans - 1 + mod) % mod
    #print(D)
    print(ans)
    return 0

if __name__ == "__main__":
    solve()

Submission status: Time Limit Exceeded

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

N = int(input())

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 _ in range(N):
  A,B = map(int, sys.stdin.readline().split())
  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
input = sys.stdin.readline

from fractions import gcd


MOD = 10**9+7
N = int(input())
F = []
zero_v = 0
inf = 0
zero = 0
for _ in range(N):
  x,y = map(int,input().split())
  if x==0 and y==0:
    zero_v += 1
  elif x==0:
    inf += 1
  elif y==0:
    zero += 1
  else:
    G = gcd(abs(x),abs(y))
    F.append((x//G,y//G))

all_keys = set()

for x,y in F:
  if x*y >0:
    if x>0:
      all_keys.add((x,y))
    else:
      all_keys.add((-x,-y))
  x,y = -y,x
  if x*y >0:
    if x>0:
      all_keys.add((x,y))
    else:
      all_keys.add((-x,-y))

all_dic = {k:[0,0] for k in all_keys}

for x,y in F:
  if x*y > 0:
    if x>0:
      all_dic[(x,y)][0] += 1
    else:
      all_dic[(-x,-y)][0] += 1
  else:
    if x>0:
      all_dic[(-y,x)][1] += 1
    else:
      all_dic[(y,-x)][1] += 1

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

for k in all_keys:
  P,N = all_dic[k]
  ans *= (pow(2,P,MOD)) + (pow(2,N,MOD))-1
  ans %= MOD


ans += zero_v-1

print(ans%MOD)