Problem p02609 (python)

Fixed submission:
N = int(input())
B = input()

B_1 = B.count("1") # pc
mod_p1 = int(B, 2) % (B_1 + 1) # pc + 1
if B_1 != 1:
    mod_m1 = int(B, 2) % (B_1 - 1) # pc - 1

# 小さい数字は直接計算しても一瞬
def calc_small(n, count):
    count += 1
    mod = n % bin(n).count("1")
    if mod == 0:
        return count
    else:
        return calc_small(mod, count)

for i in range(N):
    if B_1 == 1 and int(B[i]) == 1:
        print(0)
        continue

    # はBiが1か0かで，元のmodから差分計算できる
    if B[i] == '1':
        # 反転して-する場合 (mod PC - 1)
        mod = (mod_m1 - pow(2, N - i - 1, B_1 - 1)) % (B_1 - 1)
    else:
        # 反転して+する場合 (mod PC + 1)
        mod = (mod_p1 + pow(2, N - i - 1, B_1 + 1)) % (B_1 + 1)
    count = 1
    if mod == 0:
        print(count)
    else:
        print(calc_small(mod, count))

Buggy submission (verdict: Runtime Error):
from sys import stdin
from sys import setrecursionlimit
from collections import Counter, deque, defaultdict
from math import floor, ceil
from bisect import bisect_left
from itertools import combinations
import random
setrecursionlimit(100000)

INF = int(1e10)
MOD = int(1e9 + 7)

# popcount table
popcount = {}
popcount[0] = 0
def gpc(n):
    if n not in popcount:
        popcount[n] = bin(n).count("1")
    return popcount[n]

# mem rec
solutions = {}
def sol(Xk):
    # pc = popcount[Xk]
    pc = gpc(Xk)
    # print("Call {}, {}".format(Xk, pc))
    if Xk == 0:
        solutions[(Xk, 0)] = 0
        return 0
    elif (Xk, pc) in solutions:
        return solutions[Xk, pc]
    else:
        count = 1 + sol(Xk % pc)
        solutions[Xk, pc] = count
        return count

def main():
    from builtins import int, map
    N = int(input())
    X = input()
    
    # 余りが0からN - 1
    Xpc = X.count("1")
    iX = int(X, 2)
    rem_groups = [0] * N
    for k in range(1, N):
        rem_groups[k] = sol(k)

    # ans = [-1] * (N + 1)
    for k in range(N - 1, -1, -1):
        Xk = iX ^ (1 << k)
        Xkpc = Xpc
        if Xk & (1 << k) == (1 << k):
            Xkpc += 1
        else:
            Xkpc -= 1
        if Xk % Xkpc == 0:
            ans = 1
        else:
            ans = 1 + rem_groups[Xk % Xkpc]
        # ans_sol = sol(Xk)
        # print(bin(Xk), Xk, Xkpc, Xk % Xkpc, ans, ans_sol, ans == ans_sol)
        print(ans)


if __name__ == '__main__':
    main()

Buggy submission (verdict: Runtime Error):
from sys import stdin
from sys import setrecursionlimit
from collections import Counter, deque, defaultdict
from math import floor, ceil
from bisect import bisect_left
from itertools import combinations
import random

INF = int(1e10)
MOD = int(1e9 + 7)

def main():
    from builtins import int, map
    N = int(input())
    X = input()
    
    # 余りが0からN - 1
    Xpc = X.count("1")
    iX = int(X, 2)
    rem_groups = [0] * (200_001)
    for k in range(1, N):
        rem_groups[k] = k % bin(k).count("1")

    # ans = [-1] * (N + 1)
    for k in range(N - 1, -1, -1):
        # f(k)を計算
        Xk = iX ^ (1 << k)
        Xkpc = Xpc
        if (iX & (1 << k)) >> k:
            Xkpc -= 1
        else:
            Xkpc += 1
        ans = rem_groups[Xk % Xkpc] + 1 + (0 if Xk % Xkpc == 0 else 1)
        print(ans)



if __name__ == '__main__':
    main()

Buggy submission (verdict: Runtime Error):
from sys import stdin
from sys import setrecursionlimit
from collections import Counter, deque, defaultdict
from math import floor, ceil
from bisect import bisect_left
from itertools import combinations
import random
setrecursionlimit(100000)

INF = int(1e10)
MOD = int(1e9 + 7)

# popcount table
popcount = {}
popcount[0] = 0
def gpc(n):
    if n not in popcount:
        popcount[n] = bin(n).count("1")
    return popcount[n]

# mem rec
solutions = {}
def sol(Xk):
    # pc = popcount[Xk]
    pc = gpc(Xk)
    # print("Call {}, {}".format(Xk, pc))
    if Xk == 0:
        solutions[(Xk, 0)] = 0
        return 0
    elif (Xk, pc) in solutions:
        return solutions[Xk, pc]
    else:
        count = 1 + sol(Xk % pc)
        solutions[Xk, pc] = count
        return count

def main():
    from builtins import int, map
    N = int(input())
    X = input()
    
    # 余りが0からN - 1
    Xpc = X.count("1")
    iX = int(X, 2)
    rem_groups = [0] * N
    for k in range(1, N):
        # print(k, gpc(k), k % gpc(k))
        rem_groups[k] = k % gpc(k)

    # ans = [-1] * (N + 1)
    for k in range(N - 1, -1, -1):
        # f(k)を計算
        Xk = iX ^ (1 << k)
        Xkpc = Xpc
        if (iX & (1 << k)) >> k:
            Xkpc -= 1
        else:
            Xkpc += 1
        ans = rem_groups[Xk % Xkpc] + 1 + (0 if Xk % Xkpc == 0 else 1)
        # ans_sol = sol(Xk)
        # print(k, Xk, Xkpc, ans, ans_sol)
        print(ans)



if __name__ == '__main__':
    main()