Problem p02679 (python)

Fixed submission:
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)

Buggy submission (verdict: Runtime Error):
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 = memo[(0, 1)]
        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)

Buggy submission (verdict: Runtime Error):
class Combination:
    """階乗とその逆元のテーブルをO(N)で事前作成し、組み合わせの計算をO(1)で行う"""
    def __init__(self, n, MOD):
        self.fact = [1]
        for i in range(1, n + 1):
            self.fact.append(self.fact[-1] * i % MOD)
        self.inv_fact = [0] * (n + 1)
        self.inv_fact[n] = pow(self.fact[n], MOD - 2, MOD)
        for i in reversed(range(n)):
            self.inv_fact[i] = self.inv_fact[i + 1] * (i + 1) % MOD
        self.MOD = MOD

    def factorial(self, k):
        """k!を求める O(1)"""
        return self.fact[k]

    def inverse_factorial(self, k):
        """k!の逆元を求める O(1)"""
        return self.inv_fact[k]

    def permutation(self, k, r):
        """kPrを求める O(1)"""
        if k < r:
            return 0
        return (self.fact[k] * self.inv_fact[k - r]) % self.MOD

    def combination(self, k, r):
        """kCrを求める O(1)"""
        if k < r:
            return 0
        return (self.fact[k] * self.inv_fact[k - r] * self.inv_fact[r]) % self.MOD

    def combination2(self, k, r):
        """kCrを求める O(r) kが大きいが、r <= nを満たしているときに使用"""
        if k < r:
            return 0
        res = 1
        for l in range(r):
            res *= (k - l)
            res %= self.MOD
        return (res * self.inv_fact[r]) % self.MOD


def compress(string):
    string.append(-2)
    n = len(string)
    begin, end, cnt = 0, 1, 1
    ans = []
    while end < n:
        if string[begin] == string[end]:
            end, cnt = end + 1, cnt + 1
        else:
            ans.append((string[begin], cnt))
            begin, end, cnt = end, end + 1, 1
    return ans

  
from collections import defaultdict


n = int(input())
info = [list(map(int, input().split())) for i in range(n)]
MOD = 10 ** 9 + 7
comb = Combination(10 ** 6, MOD)
res1 = []
res2 = []
ind = []
cnt_00 = 0
cnt_a0 = 0
cnt_b0 = 0
for i in range(n):
    a, b = info[i]
    if a == 0 and b == 0:
        cnt_00 += 1
        continue
    if a == 0:
        cnt_a0 += 1
        continue
    if b == 0:
        cnt_b0 += 1
        continue
    res1.append(a / b)
    res2.append(- b / a)
    ind.append(i)

memo_r = defaultdict(int)
memo_l = defaultdict(int)

for i in range(len(res1)):
    l, r = res1[i], res2[i]
    memo_r[r] += 1
    memo_l[l] += 1

ans = 1
used = set()
for r in memo_r:
    if r in used:
        continue
    cnt_r = memo_r[r]
    cnt_l = 0
    if r in memo_l:
        cnt_l += memo_l[r]
    if r == 1.0:
        print(re)
        tmp = cnt_l + cnt_r + 1
    else:
        tmp = (pow(2, cnt_l, MOD) - 1) + (pow(2, cnt_r, MOD) - 1) + 1
    ans *= tmp
    used.add(-1 / r)

ans = ans + ans * cnt_a0 + ans * cnt_b0  + cnt_b0 * cnt_a0 * ans + cnt_00
print((ans - 1) % MOD)

Buggy submission (verdict: Runtime Error):
class Combination:
    """階乗とその逆元のテーブルをO(N)で事前作成し、組み合わせの計算をO(1)で行う"""
    def __init__(self, n, MOD):
        self.fact = [1]
        for i in range(1, n + 1):
            self.fact.append(self.fact[-1] * i % MOD)
        self.inv_fact = [0] * (n + 1)
        self.inv_fact[n] = pow(self.fact[n], MOD - 2, MOD)
        for i in reversed(range(n)):
            self.inv_fact[i] = self.inv_fact[i + 1] * (i + 1) % MOD
        self.MOD = MOD

    def factorial(self, k):
        """k!を求める O(1)"""
        return self.fact[k]

    def inverse_factorial(self, k):
        """k!の逆元を求める O(1)"""
        return self.inv_fact[k]

    def permutation(self, k, r):
        """kPrを求める O(1)"""
        if k < r:
            return 0
        return (self.fact[k] * self.inv_fact[k - r]) % self.MOD

    def combination(self, k, r):
        """kCrを求める O(1)"""
        if k < r:
            return 0
        return (self.fact[k] * self.inv_fact[k - r] * self.inv_fact[r]) % self.MOD

    def combination2(self, k, r):
        """kCrを求める O(r) kが大きいが、r <= nを満たしているときに使用"""
        if k < r:
            return 0
        res = 1
        for l in range(r):
            res *= (k - l)
            res %= self.MOD
        return (res * self.inv_fact[r]) % self.MOD


def compress(string):
    string.append(-2)
    n = len(string)
    begin, end, cnt = 0, 1, 1
    ans = []
    while end < n:
        if string[begin] == string[end]:
            end, cnt = end + 1, cnt + 1
        else:
            ans.append((string[begin], cnt))
            begin, end, cnt = end, end + 1, 1
    return ans

  
from collections import defaultdict


n = int(input())
info = [list(map(int, input().split())) for i in range(n)]
MOD = 10 ** 9 + 7
comb = Combination(10 ** 6, MOD)
res1 = []
res2 = []
ind = []
cnt_00 = 0
cnt_a0 = 0
cnt_b0 = 0
for i in range(n):
    a, b = info[i]
    if a == 0 and b == 0:
        cnt_00 += 1
        continue
    if a == 0:
        cnt_a0 += 1
        continue
    if b == 0:
        cnt_b0 += 1
        continue
    res1.append(a / b)
    res2.append(- b / a)
    ind.append(i)

memo_r = defaultdict(int)
memo_l = defaultdict(int)

for i in range(len(res1)):
    l, r = res1[i], res2[i]
    memo_r[r] += 1
    memo_l[l] += 1

ans = 1
used = set()
for r in memo_r:
    if r in used:
        continue
    cnt_r = memo_r[r]
    cnt_l = 0
    if r in memo_l:
        cnt_l += memo_l[r]
    if r == -1.0 or r == 1.0:
        tmp = cnt_l + cnt_r + 1
    else:
        tmp = (pow(2, cnt_l, MOD) - 1) + (pow(2, cnt_r, MOD) - 1) + 1
    ans *= tmp
    used.add(-1 / r)

if cnt_00 >= 1:
    print(re)
ans += cnt_00 + ans * (cnt_a0 + cnt_b0)
print((ans - 1) % MOD)