Problem p02609 (python)

Fixed submission:
N=int(input())
X=input()
num_X = int(X, base=2)
pop_x = X.count("1")
if pop_x <= 1:
    mod0 = pop_x + 1
    res0 = num_X % mod0
else:
    mod1 = pop_x - 1
    mod0 = pop_x + 1
    res1 = num_X % (mod1)
    res0 = num_X % (mod0)

# pops = [0]*(N+20)
for i in range(N):
    tmp = 0
    if X[i] == "0":
        # +
        tmp = (res0 + pow(2, N-i-1, mod0))%mod0
    else:
        if pop_x == 1:
            print(0)
            continue
        tmp = (res1 - pow(2, N-i-1, mod1))%mod1
    
    if tmp == 0:
        print(1)
        continue
    cnt = 1
    while tmp != 0:
        pop = bin(tmp).count("1")
        tmp %= pop
        cnt += 1
    print(cnt)

Buggy submission (verdict: Runtime Error):
N=int(input())
X=input()
num_X = int(X, base=2)
pop_x = X.count("1")
mod1 = pop_x - 1
mod0 = pop_x + 1
res1 = num_X % (mod1)
res0 = num_X % (mod0)

# pops = [0]*(N+20)
for i in range(N):
    tmp = 0
    if X[i] == "0":
        # +
        tmp = (res0 + pow(2, N-i-1, mod0))%mod0
    else:
        tmp = (res1 - pow(2, N-i-1, mod1))%mod1
    
    if tmp == 0:
        print(1)
        continue
    cnt = 1
    while tmp != 0:
        pop = bin(tmp).count("1")
        tmp %= pop
        cnt += 1
    print(cnt)

Buggy submission (verdict: Runtime Error):
N=int(input())
X=input()
num_X = int(X, base=2)
pop_x = X.count("1")
mod1 = pop_x - 1
mod0 = pop_x + 1
res1 = num_X % (mod1)
res0 = num_X % (mod0)

pops = [0]*(N+20)
for i in range(N):
    tmp = 0
    if X[i] == "0":
        # +
        tmp = (res0 + pow(2, N-i-1, mod0))%mod0
    else:
        tmp = (res1 - pow(2, N-i-1, mod1))%mod1
    
    if tmp == 0:
        print(1)
        continue
    cnt = 1
    while tmp != 0:
        if not pops[tmp]:
            pop = bin(tmp).count("1")
            pops[tmp] = pop
        else:
            pop = pops[tmp]

        tmp %= pop
        cnt += 1
    print(cnt)

Buggy submission (verdict: Runtime Error):
N=int(input())
X=input()
num_X = int(X, base=2)
pop_xi = [0]*N
pop_x = X.count("1")
X_pop_res = [0]*N

mod1 = pop_x - 1
mod0 = pop_x + 1
res1 = num_X % (mod1)
res0 = num_X % (mod0)

# for i in range(N):
#     if X[i]=="1":
#         pop_xi[i] = mod1
#         X_pop_res[i] = res1
#     else:
#         pop_xi[i] = mod0
#         X_pop_res[i] = res0
pops = [0]*(N+20)
for i in range(N):
    tmp = 0
    if X[i] == "0":
        # +
        tmp = (res0 + pow(2, N-i-1, mod0))%mod0
    else:
        tmp = (res1 - pow(2, N-i-1, mod1))%mod1
    
    if tmp == 0:
        print(1)
        continue
    cnt = 1
    while tmp != 0:
        if not pops[tmp]:
            pop = bin(tmp).count("1")
        else:
            pop = pops[tmp]

        tmp %= pop
        cnt += 1
    print(cnt)

Buggy submission (verdict: Runtime Error):
def main():
    N = int(input())
    X = int(input(), 2)

    def popcount(num):
        return bin(num).count("1")
    
    popc_X = popcount(X)
    puls1 = X % (popc_X + 1)
    minu1 = X % (popc_X - 1)
    dic = {0: minu1, 1: puls1}
    tow = [1]
    for i in range(1,N):
        tow.append(2*tow[i-1])
    pop_table = {i: [popcount(i), 0, 0] for i in range(1, 1+N)}
    def f(x, factor, i):
        temp = dic[factor]
        if factor:
            temp += tow[i] % (popc_X + 1)
        else:
            temp -= tow[i] % (popc_X - 1) 
        count = 1
        visited = []
        
        while temp > 0:
            if pop_table[temp][1] == 0:
                pop_table[temp][1] = count
            else:
                if pop_table[temp][2]:
                    count += pop_table[temp][1]
                    break

            if pop_table[temp][2] == 0:
                visited.append(temp)
            temp %= pop_table[temp][0]
            count += 1

        for v in visited:
            pop_table[v][1] = count - pop_table[v][1]
            pop_table[v][2] = 1
        return count
    

    # ans = [0]*N
    for i in range(N-1, -1, -1):
        xi = X ^ (1 << i)
        # print(xi, "xi")
        if X & (1<<i):
            factor = 0
        else:
            factor = 1
        print(f(xi, factor, i))
    # for a in ans:
    #     print(a)

main()

Buggy submission (verdict: Runtime Error):
def main():
    N = int(input())
    X = int(input(), 2)

    def popcount(num):
        return bin(num).count("1")
    
    popc_X = popcount(X)
    pop_table = {i: [popcount(i), 0, 0] for i in range(1, N+1)}
    
    def f(x, factor):
        temp = x
        temp %= (popc_X + factor)
        count = 1
        visited = []
        
        while temp > 0:
            if pop_table[temp][1] == 0:
                pop_table[temp][1] = count
            else:
                if pop_table[temp][2]:
                    count += pop_table[temp][1]
                    break

            if pop_table[temp][2] == 0:
                visited.append(temp)
            temp %= pop_table[temp][0]
            count += 1

        for v in visited:
            pop_table[v][1] = count - pop_table[v][1]
            pop_table[v][2] = 1
        return count
    

    # ans = [0]*N
    for i in range(N-1, -1, -1):
        xi = X ^ (1 << i)
        # print(xi, "xi")
        if X & (1<<i):
            factor = -1
        else:
            factor = 1
        print(f(xi, factor))
    # for a in ans:
    #     print(a)

main()

Buggy submission (verdict: Runtime Error):
def main():
    N = int(input())
    X = int(input(), 2)

    def popcount(x):
        '''xの立っているビット数をカウントする関数
        (xは64bit整数)'''

        # 2bitごとの組に分け、立っているビット数を2bitで表現する
        x = x - ((x >> 1) & 0x5555555555555555)

        # 4bit整数に 上位2bit + 下位2bit を計算した値を入れる
        x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)

        x = (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f # 8bitごと
        x = x + (x >> 8) # 16bitごと
        x = x + (x >> 16) # 32bitごと
        x = x + (x >> 32) # 64bitごと = 全部の合計
        return x & 0x0000007f
  
    def f(x):
        temp = x
        count = 0
        while temp > 0:
            temp = temp % popcount(temp)
            count += 1
        return count
    
    ans = [0]*N
    for i in range(0, N):
        xi = X ^ (1 << i)
        ans[N-i-1] = f(xi)
    for a in ans:
        print(a)

main()