Problem p02679 (python)

Fixed submission:
import sys
import math
from math import gcd

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

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

Buggy submission (verdict: Runtime Error):
import sys
import math
from collections import Counter

mod = 1000000007
 
N = int(sys.stdin.readline().strip())
fishes = []
zero = 0
zero_l = 0
zero_r = 0
rest = N
for _ in range(N):
    a, b = map(int, sys.stdin.readline().strip().split())
    # 角度だけが重要なので座標圧縮して良い
    if a == 0 and b == 0:
        # fishes.append((0, 0))
        zero += 1
        rest -= 1
    elif a == 0:
        # fishes.append((0, 1))
        zero_l += 1
    elif b == 0:
        # fishes.append((1, 0))
        zero_r += 1
    else:
        gcd = math.gcd(a, b)
        fishes.append((a // gcd, b // gcd))

# print(fishes)

# (a, b)ごとにカウント
counter = Counter(fishes)
# print(counter)

calculated = set()
ans = 1
# 組み合わせを計算
for ((a, b), count) in counter.items():
    # if a == 0 or b == 0:
    #     continue
    # 計算済みの場合
    if (a, b) in calculated:
        continue

    # 仲が悪いイワシの数
    bad_count = 0
    # 90度異なるものがダメ
    for (a_k, b_k) in ((-1, 1), (1, -1)):
        bad_pair = (b * a_k, a * b_k)
        if bad_pair in counter:
            bad_count += counter[bad_pair]
            calculated.add(bad_pair)

    if bad_count != 0:
        # good か bad からしか選ばないものは駄目
        ans *= pow(2, count + bad_count, mod) - (pow(2, count, mod) - 1) * (pow(2, bad_count, mod) - 1) 
        ans %= mod

        rest -= count + bad_count

# どちらかが0になっているもの
ans *= pow(2, zero_r + zero_l, mod) - (pow(2, zero_l, mod) - 1) * (pow(2, zero_r, mod) - 1)
ans %= mod
rest -= zero_r + zero_l

# 仲が悪いものが存在しないイワシの組み合わせ
ans *= pow(2, rest, mod)

# 全部選ばないものは駄目
ans += zero - 1
ans %= mod

print(ans)

Buggy submission (verdict: Runtime Error):
import sys
import math
from collections import Counter

mod = 1000000007
 
N = int(sys.stdin.readline().strip())
fishes = []
zero = 0
zero_l = 0
zero_r = 0
rest = N
for _ in range(N):
    a, b = map(int, sys.stdin.readline().strip().split())
    # 角度だけが重要なので座標圧縮して良い
    if a == 0 and b == 0:
        # fishes.append((0, 0))
        zero += 1
        rest -= 1
    elif a == 0:
        # fishes.append((0, 1))
        zero_l += 1
    elif b == 0:
        # fishes.append((1, 0))
        zero_r += 1
    else:
        gcd = math.gcd(a, b)
        fishes.append((a // gcd, b // gcd))

# print(fishes)

# (a, b)ごとにカウント
counter = Counter(fishes)
# print(counter)

calculated = set()
ans = 1
# 組み合わせを計算
for ((a, b), count) in counter.items():
    # if a == 0 or b == 0:
    #     continue
    # 計算済みの場合
    if (a, b) in calculated:
        continue

    # 仲が悪いイワシの数
    bad_count = 0
    # 90度異なるものがダメ
    for (a_k, b_k) in ((-1, 1), (1, -1)):
        bad_pair = (b * a_k, a * b_k)
        if bad_pair in counter:
            bad_count += counter[bad_pair]
            calculated.add(bad_pair)

    # 仲が悪いイワシがいない場合
    if bad_count == 0:
        ans *= 2**count
        ans %= mod
    else:
        # 仲が良いものだけの組み合わせ
        good = 2**count
        
        # 仲が悪いものだけの組み合わせ
        bad = 2**bad_count

        # 全て選ばない場合は許容しないので1を引いておく
        ans *= good + bad - 1
        ans %= mod

    rest -= count + bad_count

if (1,0) not in counter:
    counter[(1,0)] = 0
if (0,1) not in counter:
    counter[(0,1)] = 0
if (0,0) not in counter:
    counter[(0,0)] = 0
ans *= 2**counter[(1, 0)] + 2**counter[(0, 1)] - 1
ans %= mod
rest -= zero_r + zero_l

# 仲が悪いものが存在しないイワシの組み合わせ
ans *= pow(2, rest, mod)

# 全部選ばないものは駄目
ans += zero - 1
ans %= mod


print(ans)

Buggy submission (verdict: Runtime Error):
import sys
import math
from collections import Counter

mod = 1000000007
 
def modinv(a, mod=10**9+7):
    return pow(a, mod-2, mod)

N = int(sys.stdin.readline().strip())

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

# math.factroialでは速度が足りない
def nCr(n, r, mod=10**9+7):
    if n < 0 or r < 0 or n < r:
        return 0

    if n == 0 or r == 0:
        return 1

    """
    a = math.factorial(n) % mod
    b = math.factorial(r) % mod
    c = math.factorial(n - r) % mod
    """
    a = fact[n]
    b = fact[r]
    c = fact[n-r]

    inv = modinv(b*c, mod)
    ans = a * inv

    return ans % mod

fishes = []
for _ in range(N):
    a, b = map(int, sys.stdin.readline().strip().split())
    # 角度だけが重要なので座標圧縮して良い
    gcd = math.gcd(a, b)
    fishes.append((a // gcd, b // gcd))

# print(fishes)

# (a, b)ごとにカウント
counter = Counter(fishes)

calculated = set()
ans = 0
# 全組み合わせ
for i in range(1, N+1):
    ans += nCr(N, i)
    ans %= mod
# print("all", ans)

# 除外すべき組み合わせを計算
for ((a, b), count) in counter.items():
    # 計算済みの場合
    if (a, b) in calculated:
        continue

    # 仲が悪いイワシの数
    bad_count = 0
    # 90度異なるものがダメ
    for (a_k, b_k) in ((-1, 1), (1, -1)):
        bad_pair = (b * a_k, a * b_k)
        if bad_pair in counter:
            bad_count += counter[bad_pair]
            calculated.add(bad_pair)

    # 仲が良いものだけの組み合わせ
    good = 0
    for i in range(1, count+1):
        good += nCr(count, i)
        good %= mod
        
    # 仲が悪いものだけの組み合わせ
    bad = 0
    for i in range(1, bad_count+1):
        bad += nCr(bad_count, i)
        bad %= mod

    others = 0
    others_count = N - count - bad_count 
    for i in range(others_count + 1):
        others += nCr(others_count, i)

    # goodから1匹以上、othersから0匹以上、badから1匹以上の組み合わせを除外
    bad_choices = good * others * bad
    # print(good, others, bad, bad_choices)
    ans -= bad_choices
    # print(ans)
    ans %= mod

print(ans)