Problem:


Score : 400 points

Problem Statement

Let \mathrm{popcount}(n) be the number of 1s in the binary representation of n.
For example, \mathrm{popcount}(3) = 2, \mathrm{popcount}(7) = 3, and \mathrm{popcount}(0) = 0.

Let f(n) be the number of times the following operation will be done when we repeat it until n becomes 0: "replace n with the remainder when n is divided by \mathrm{popcount}(n)." (It can be proved that, under the constraints of this problem, n always becomes 0 after a finite number of operations.)

For example, when n=7, it becomes 0 after two operations, as follows:

\mathrm{popcount}(7)=3, so we divide 7 by 3 and replace it with the remainder, 1.

\mathrm{popcount}(1)=1, so we divide 1 by 1 and replace it with the remainder, 0.

You are given an integer X with N digits in binary.
For each integer i such that 1 \leq i \leq N, let X_i be what X becomes when the i-th bit from the top is inverted.
Find f(X_1), f(X_2), \ldots, f(X_N).

Constraints

1 \leq N \leq 2 \times 10^5

X is an integer with N digits in binary, possibly with leading zeros.

Input

Input is given from Standard Input in the following format:

N
X

Output

Print N lines. The i-th line should contain the value f(X_i).

Sample Input 1

3
011

Sample Output 1

2
1
1

X_1 = 7, which will change as follows: 7 \rightarrow 1 \rightarrow 0. Thus, f(7) = 2.

X_2 = 1, which will change as follows: 1 \rightarrow 0. Thus, f(1) = 1.

X_3 = 2, which will change as follows: 2 \rightarrow 0. Thus, f(2) = 1.

Sample Input 2

23
00110111001011011001110

Sample Output 2

2
1
2
2
1
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
1
3



Sample input:
3
011


Sample output:
2
1
1

Submission status: Accepted

Solution code:
def func(z,c):
    if c == 0:
        z = 0
    else:
        z = z%c
    a = bin(z)
    b = 0
    for i in range(len(a)):
        if a[i] == "1":
            b += 1
    return z,b

n = int(input())
x = input()
c = 0
for i in range(n):
    if x[i] == "1":
        c += 1
s0 = int(x,2)%(c+1)
if c <= 1:
    s1 = 0
else:
    s1 = int(x,2)%(c-1)
for i in range(n):
    sw = 0
    if x[i] == "0":
        d = c + 1
        z = (s0 + pow(2,n-i-1,d))%d
    else:
        d = c - 1
        if d == 0:
            z = 0
            sw = 1
        else:
            z = (s1 - pow(2,n-i-1,d))%d
    ans = 1
    p = bin(z)
    e = 0
    for A in str(p):
        if A == "1":
            e += 1
    d = e
    if sw == 1:
        ans = 0
    else:
        while z:
            z,d = func(z,d)
            ans += 1
    print(ans)

Submission status: Accepted

Solution code:
import sys
from collections import deque
import bisect
import copy
import heapq
import itertools
import math
input = sys.stdin.readline
sys.setrecursionlimit(1000000)
mod = 10 ** 9 + 7

def read_values(): return map(int, input().split())
def read_index(): return map(lambda x: int(x) - 1, input().split())
def read_list(): return list(read_values())
def read_lists(N): return [read_list() for n in range(N)]


def f(N):
    res = 0
    while N != 0:
        b = format(N, "b").count("1")
        N %= b
        res += 1
    return res


def main():
    N = int(input())
    X = input().strip()
    K = X.count("1")

    A = [(1, 1)]
    for i in range(N):
        a, b = A[-1]
        A.append(((a * 2) % (K - 1) if K != 1 else 0, (b * 2) % (K + 1)))

    B = [0, 0]
    for i, b in enumerate(X[::-1]):
        if b == "0":
            continue
        if K != 1:
            B[0] += A[i][0]
            B[0] %= K - 1
        B[1] += A[i][1]
        B[1] %= K + 1

    res = [0] * N
    for i, b in enumerate(X[::-1]):
        if b == "0":
            res[i] = (B[1] + A[i][1]) % (K + 1)
        else:
            if K == 1:
                res[i] = 0
                continue
            res[i] = (B[0] - A[i][0]) % (K - 1)
        res[i] = f(res[i]) + 1

    for r in res[::-1]:
        print(r)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n = int(input())
x = list(input())

count = x.count('1')
one_count = count - 1
zero_count = count + 1

one_mod = 0
zero_mod = 0
for b in x:
    if one_count:
        one_mod = (one_mod * 2 + int(b)) % one_count
    zero_mod = (zero_mod * 2 + int(b)) % zero_count

f = [0] * 2000001
pop_count = [0] * 200001
for i in range(1, 200001):
    pop_count[i] = pop_count[i//2] + i % 2
    f[i] = f[i % pop_count[i]] + 1

for i in range(n):
    if x[i] == '1':
        if one_count:
            nxt = one_mod
            nxt -= pow(2, n-i-1, one_count)
            nxt %= one_count
            print(f[nxt] + 1)
        else:
            print(0)
    if x[i] == '0':
        nxt = zero_mod
        nxt += pow(2, n-i-1, zero_count)
        nxt %= zero_count
        print(f[nxt] + 1)

Submission status: Accepted

Solution code:
n = int(input())
x = input()
a = x.count('1')
b = int(x,2)

ary = [None for i in range(200010)]
ary[0] = 0

def f(n):
  if ary[n] is not None:
    return ary[n]
  b = bin(n).count('1')
  r = 1 + f(n%b)
  ary[n] = r
  return ary[n]

a1 = a + 1
a0 = a - 1
for i in range(200010):
  f(i)

# one = [1] * 200010
# zero = [1] * 200010
# for i in range(1, 200010):
#     if a0 != 0:
#         one[i] = one[i-1] * 2 % a0
#     zero[i] = zero[i-1] * 2 % a1

c1 = b%a1
if a0 != 0:
  c0 = b%a0
for i in range(n-1, -1, -1):
  if x[n-1-i] == '0':
    # y = c1 + zero[i]
    y = c1 + pow(2,i,a1)
    y %= a1
    print (ary[y]+1)
  else:
    if a0 != 0:
      y = c0 - pow(2,i,a0)
      y %= a0
      print (ary[y]+1)
    else:
      print (0)

Submission status: Accepted

Solution code:
n = int(input())
x = input()
a = x.count('1')
b = int(x,2)
# print (b)

ary = [None for i in range(200010)]
ary[0] = 0

def f(n):
  if ary[n] is not None:
    return ary[n]
  b = bin(n).count('1')
  r = 1 + f(n%b)
  ary[n] = r
  return ary[n]


a1 = a + 1
a0 = a - 1
for i in range(200010):
  f(i)


one = [1] * 200010
zero = [1] * 200010
for i in range(1, 200010):
    if a0 != 0:
        one[i] = one[i-1] * 2 % a0
    zero[i] = zero[i-1] * 2 % a1


ans = [0 for i in range(n)]
c1 = b%a1
if a0 != 0:
  c0 = b%a0
for i in range(n-1, -1, -1):
  if x[n-1-i] == '0':
    y = c1 + zero[i]
    # y = x %a1
    y %= a1
    print (ary[y]+1)
  else:
    if a0 != 0:
      y = c0 - one[i]
      y %= a0
      print (ary[y]+1)
    else:
      print (0)
# ans.reverse()
# for i in ans:
#   print (i)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
# sys.setrecursionlimit(10**6)
# buff_readline = sys.stdin.buffer.readline
buff_readline = sys.stdin.readline
readline = sys.stdin.readline

INF = 2**62-1


def read_int():
    return int(buff_readline())


def read_str():
    return readline().strip()


def slv(N, X):
    C = X.count('1')
    cmr = 0
    cpr = 0
    for b in X:
        b = int(b)
        cpr = ((cpr * 2) + b) % (C+1)
        if C-1 != 0:
            cmr = ((cmr * 2) + b) % (C-1)

    ans = []
    for i in range(N):
        t = 1
        if X[i] == '0':
            x = (cpr + pow(2, N-i-1, C+1)) % (C+1)
        elif X[i] == '1' and C-1 != 0:
            x = (cmr - pow(2, N-i-1, C-1)) % (C-1)
        else:
            x = 0
            t = 0

        while x != 0:
            x %= bin(x).count('1')
            t += 1

        ans.append(t)

    return ans


def main():
    N = read_int()
    X = read_str()
    print(*slv(N, X), sep='\n')


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
# sys.setrecursionlimit(10**6)
# buff_readline = sys.stdin.buffer.readline
buff_readline = sys.stdin.readline
readline = sys.stdin.readline

INF = 2**62-1


def read_int():
    return int(buff_readline())


def read_str():
    return readline().strip()


def slv(N, X):
    C = X.count('1')
    cmr = 0
    cpr = 0
    for b in X:
        b = int(b)
        cpr = ((cpr * 2) + b) % (C+1)
        if C-1 != 0:
            cmr = ((cmr * 2) + b) % (C-1)

    ans = []
    for i in range(N):
        t = 0
        if X[i] == '0':
            x = (cpr + pow(2, N-i-1, C+1)) % (C+1)
            t += 1
        elif X[i] == '1' and C-1 != 0:
            x = (cmr - pow(2, N-i-1, C-1)) % (C-1)
            t += 1
        else:
            x = 0

        while x != 0:
            x %= bin(x).count('1')
            t += 1

        ans.append(t)

    return ans


def main():
    N = read_int()
    X = read_str()
    print(*slv(N, X), sep='\n')


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
# sys.setrecursionlimit(10**6)
# buff_readline = sys.stdin.buffer.readline
buff_readline = sys.stdin.readline
readline = sys.stdin.readline

INF = 2**62-1


def read_int():
    return int(buff_readline())


def read_str():
    return readline().strip()


def slv(N, X):
    C = X.count('1')
    cmr = 0
    cpr = 0
    for b in X:
        b = int(b)
        cpr = ((cpr * 2) + b) % (C+1)
        if C-1 != 0:
            cmr = ((cmr * 2) + b) % (C-1)

    ans = []
    for i in range(N):
        t = 0
        if X[i] == '0':
            x = (cpr + pow(2, N-i-1, C+1)) % (C+1)
            t += 1
        elif X[i] == '1' and C-1 != 0:
            x = (cmr - pow(2, N-i-1, C-1)) % (C-1)
            t += 1
        else:
            x = 0

        while x != 0:
            x = x % bin(x).count('1')
            t += 1

        ans.append(t)

    return ans


def main():
    N = read_int()
    X = read_str()
    print(*slv(N, X), sep='\n')


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
# sys.setrecursionlimit(10**6)
# buff_readline = sys.stdin.buffer.readline
buff_readline = sys.stdin.readline
readline = sys.stdin.readline

INF = 2**62-1


def read_int():
    return int(buff_readline())


def read_str():
    return readline().strip()


def slv(N, X):
    C = X.count('1')
    cmr = 0
    cpr = 0
    for b in X:
        b = int(b)
        cpr = ((cpr * 2) + b) % (C+1)
        if C-1 != 0:
            cmr = ((cmr * 2) + b) % (C-1)

    ans = []
    for i in range(N):
        t = 1
        if X[i] == '0':
            x = (cpr + pow(2, N-i-1, C+1)) % (C+1)
        elif X[i] == '1' and C-1 != 0:
            x = (cmr - pow(2, N-i-1, C-1)) % (C-1)
        else:
            x = 0
            t = 0

        while x != 0:
            x = x % bin(x).count('1')
            t += 1

        ans.append(t)

    return ans


def main():
    N = read_int()
    X = read_str()
    print(*slv(N, X), sep='\n')


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
# sys.setrecursionlimit(10**6)
# buff_readline = sys.stdin.buffer.readline
buff_readline = sys.stdin.readline
readline = sys.stdin.readline

INF = 2**62-1


def read_int():
    return int(buff_readline())


def read_str():
    return readline().strip()


def slv(N, X):
    C = X.count('1')
    cmr = 0
    cpr = 0
    for b in X:
        cpr = ((cpr * 2) + int(b)) % (C+1)

    for b  in X:
        if C-1 != 0:
            cmr = ((cmr * 2) + int(b)) % (C-1)

    ans = []
    for i in range(N):
        t = 1
        if X[i] == '0':
            x = (cpr + pow(2, N-i-1, C+1)) % (C+1)
        elif X[i] == '1' and C-1 != 0:
            x = (cmr - pow(2, N-i-1, C-1)) % (C-1)
        else:
            x = 0
            t = 0

        while x != 0:
            x = x % bin(x).count('1')
            t += 1

        ans.append(t)

    return ans


def main():
    N = read_int()
    X = read_str()
    print(*slv(N, X), sep='\n')


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
# sys.setrecursionlimit(10**6)
# buff_readline = sys.stdin.buffer.readline
buff_readline = sys.stdin.readline
readline = sys.stdin.readline

INF = 2**62-1


def read_int():
    return int(buff_readline())


def read_str():
    return readline().strip()


def slv(N, X):
    C = X.count('1')
    cmr = 0
    cpr = 0
    for b in X:
        if C-1 != 0:
            cmr = ((cmr * 2) + int(b)) % (C-1)
        cpr = ((cpr * 2) + int(b)) % (C+1)

    ans = []
    for i in range(N):
        t = 1
        if X[i] == '0':
            x = (cpr + pow(2, N-i-1, C+1)) % (C+1)
        elif X[i] == '1' and C-1 != 0:
            x = (cmr - pow(2, N-i-1, C-1)) % (C-1)
        else:
            x = 0
            t = 0

        while x != 0:
            x = x % bin(x).count('1')
            t += 1

        ans.append(t)

    return ans


def main():
    N = read_int()
    X = read_str()
    print(*slv(N, X), sep='\n')


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(10**6)
# buff_readline = sys.stdin.buffer.readline
buff_readline = sys.stdin.readline
readline = sys.stdin.readline

INF = 2**62-1


def read_int():
    return int(buff_readline())


def read_int_n():
    return list(map(int, buff_readline().split()))


def read_float():
    return float(buff_readline())


def read_float_n():
    return list(map(float, buff_readline().split()))


def read_str():
    return readline().strip()


def read_str_n():
    return readline().strip().split()


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, X):
    C = X.count('1')
    cmr = 0
    cpr = 0
    for b in X:
        if C-1 != 0:
            cmr = ((cmr * 2) + int(b)) % (C-1)
        cpr = ((cpr * 2) + int(b)) % (C+1)

    ans = []
    for i in range(N):
        t = 1
        if X[i] == '0':
            x = (cpr + pow(2, N-i-1, C+1)) % (C+1)
        elif X[i] == '1' and C-1 != 0:
            x = (cmr - pow(2, N-i-1, C-1)) % (C-1)
        else:
            x = 0
            t = 0

        while x != 0:
            x = x % bin(x).count('1')
            t += 1

        ans.append(t)

    return ans


def main():
    N = read_int()
    X = read_str()
    print(*slv(N, X), sep='\n')


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(10**6)
# buff_readline = sys.stdin.buffer.readline
buff_readline = sys.stdin.readline
readline = sys.stdin.readline

INF = 2**62-1


def read_int():
    return int(buff_readline())


def read_int_n():
    return list(map(int, buff_readline().split()))


def read_float():
    return float(buff_readline())


def read_float_n():
    return list(map(float, buff_readline().split()))


def read_str():
    return readline().strip()


def read_str_n():
    return readline().strip().split()


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, X):
    C = X.count('1')
    cmr = 0
    cpr = 0
    for b in X:
        if C-1 != 0:
            cmr *= 2
            cmr += int(b)
            cmr %= C - 1
        cpr *= 2
        cpr += int(b)
        cpr %= C + 1

    for i in range(N):
        t = 1
        if X[i] == '0':
            x = (cpr + pow(2, N-i-1, C+1)) % (C+1)
        elif X[i] == '1' and C-1 != 0:
            x = (cmr - pow(2, N-i-1, C-1)) % (C-1)
        else:
            x = 0
            t = 0
        while x != 0:
            x = x % bin(x).count('1')
            t += 1
        print(t)


def main():
    N = read_int()
    X = read_str()
    slv(N, X)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n = int(input())
s = input()
x = [int(i) for i in s]
pc = s.count('1')

def popcnt(x):
    x = x - ((x >> 1) & 0x5555555555555555)
    x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)
    x = (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f
    x = x + (x >> 8)
    x = x + (x >> 16)
    x = x + (x >> 32)
    return x & 0x0000007f

def f(x):
    if x == 0:
        return 0
    return f(x % popcnt(x)) + 1

ans = [0]*n
for a in range(2):
    npc = pc
    if a == 0:
        npc += 1
    else:
        npc -= 1
    
    if npc <= 0:
        continue
    
    r0 = 0
    for i in range(n):
        r0 = (r0*2) % npc
        r0 += x[i]

    k = 1
    for i in range(n-1, -1, -1):
        if x[i] == a:
            r = r0
            if a == 0:
                r = (r+k) % npc
            else:
                r = (r-k+npc) % npc
            ans[i] = f(r) + 1
        k = (k*2) % npc

for i in ans:
    print(i)

Submission status: Accepted

Solution code:
def f(n):
    ret = 1
    while n > 0:
        n %= bin(n).count('1')
        ret += 1
    return ret

if __name__ == "__main__":
    n = int(input())
    x = input()
    cnt = x.count('1')

    if cnt == 1:
        for k in x[:-1]:
            if k == '0':
                print(1)
            else:
                print(0)
        if x[-1] == '1':
            print(0)
        else:
            print(2)
        exit()

    xNum = 0
    for k in x:
        xNum <<= 1
        if k == '1':
            xNum += 1
    ans = []
    p = xNum % (cnt + 1)
    m = xNum % (cnt - 1)

    for i in range(n):
        if x[i] == '0':
            ans.append(f((p + pow(2, n - i - 1, cnt + 1)) % (cnt + 1)))
        else:
            ans.append(f((m - pow(2, n - i - 1, cnt - 1)) % (cnt - 1)))
    print(*ans, sep='\n')

Submission status: Accepted

Solution code:
N = int(input())
S = input()
X = list(int(x) for x in S)


def popcount(x):
    return bin(x).count("1")


def f(x):
    if x == 0:
        return 0
    return f(x % popcount(x)) + 1


MAX = 2 * 10 ** 5 + 5
# print(X)

pc = sum(X)  # もとのpopcount

ans = [0] * (N + 1)
for b in range(2):
    npc = pc  # 今のpopcount
    if b == 0:
        npc += 1
    else:
        npc -= 1
    if npc <= 0:
        continue
    # もとの割った余りを求めていく
    r0 = 0
    for i in range(N):
        r0 = (r0 * 2) % npc
        r0 += X[i]
    k = 1
    for i in reversed(range(N)):
        if X[i] == b:  # i桁目がbのものだけ処理する。
            r = r0  # 今の桁を変えたときに割った余りがどう変化するか
            if b == 0:
                r = (r + k) % npc
            else:
                r = (r - k + npc) % npc
            # i桁目をフリップしたときの値がここまでで求まった。
            ans[i] = f(r) + 1
        k = (k * 2) % npc

for i in range(N):
    print(ans[i])

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
sys.setrecursionlimit(10 ** 8)
from itertools import accumulate
from itertools import permutations
from itertools import combinations
from collections import defaultdict
from collections import Counter
import fractions
import math
from collections import deque
from bisect import bisect_left
from bisect import bisect_right
from bisect import insort_left
import itertools
from heapq import heapify
from heapq import heappop
from heapq import heappush
import heapq
from copy import deepcopy
from decimal import Decimal
alf = list("abcdefghijklmnopqrstuvwxyz")
ALF = list("ABCDEFGHIJKLMNOPQRSTUVWXYZ")
#import numpy as np
INF = float("inf")
#d = defaultdict(int)
#d = defaultdict(list)
N = int(input())
S = list(input())[:-1]
table = [0]*(N+5)
table[1] = 1
for i in range(2,N+3):
    num = i
    cnt = 0
    while num != 0:
        a = num % 2
        num = num // 2
        cnt += a
    p = i % cnt
    table[i] = table[p]+1
c = 0
for s in S:
    if s == "1":
        c += 1
p = 0
q = 0

for i in range(N):
    ss = S[N-1-i]
    p += int(ss)*pow(2,i,c+1)
    if c != 1:
        q += int(ss)*pow(2,i,c-1)
    p %= (c+1)
    if c != 1:
        q %= (c-1)
for i in range(N):
    ss = S[i]
    if ss == "0":
        ans = (p+pow(2,N-1-i,c+1))%(c+1)
        print(table[ans]+1)
    else:
        if c == 1:
            print(0)
        else:
            if c != 1:
                ans = (q-pow(2,N-1-i,c-1))%(c-1)
                print(table[ans]+1)
            else:
                print(0)

Submission status: Accepted

Solution code:
import sys
from functools import lru_cache
 
sys.setrecursionlimit(4100000)
 
@lru_cache(maxsize=None)
def f(n):
    if n == 0:
        return 0

    return f(n % bin(n).count('1')) + 1

def main():
    N = int(input())
    X = list(input())
    pc = X.count('1')
    now = 0
    for i in range(N):
        if X[i] == '1':
            now += pow(2,N-i-1)

    ac = pc + 1
    dc = pc - 1
    ac_now = now % ac
    if dc:
        dc_now = now % dc
    for i in range(N):
        cnt = 0
        if X[i] == '1' and dc:
            tmp = (dc_now - pow(2, N-i-1, dc)) % dc
            cnt = 1 + f(tmp)
        elif X[i] == '0':
            tmp = (ac_now + pow(2, N-i-1, ac)) % ac
            cnt = 1 + f(tmp)

        print(cnt)



if __name__ == "__main__":
    main()

Submission status: Accepted

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


def f(n):
    if n == 0:
        return 1
    p = n % (bin(n).count('1'))
    return f(p) + 1


def main(input, print):
    N = int(input())
    X = list(map(int, list(input().strip())))
    ans = [0] * N

    pcnt = 0
    for i in range(N):
        if X[i] == 1:
            pcnt += 1
    for is_up in range(2):
        current_pcnt = pcnt
        if is_up:
            current_pcnt -= 1
        else:
            current_pcnt += 1
        if current_pcnt <= 0:
            continue
        total = 0
        for i in range(N):
            total = (total*2) % current_pcnt
            total += X[i]
        current_mask = 1
        for i in reversed(range(N)):
            if(X[i] == is_up):
                current_total = total
                if is_up:
                    current_total = (current_total-current_mask+current_pcnt) % current_pcnt
                else:
                    current_total = (current_total+current_mask) % current_pcnt
                ans[i] = f(current_total)
            current_mask = current_mask * 2 % current_pcnt

    for i in range(N):
        print(ans[i])


if __name__ == '__main__':
    main(sys.stdin.readline, print)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(300000)

def I(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def MI0(): return map(lambda s: int(s) - 1, sys.stdin.readline().split())
def LMI(): return list(map(int, sys.stdin.readline().split()))
def LMI0(): return list(map(lambda s: int(s) - 1, sys.stdin.readline().split()))
MOD = 10 ** 9 + 7
INF = float('inf')


N = I()
X = input()

popcount = X.count('1')

def mod(popcount):
    if popcount in [0, 1]:
        return [0] * N
    a = []
    base = 1
    for i in range(N):
        if i == 0:
            a.append(1)
        else:
            base = base * 2 % popcount
            a.append(base)
    return a

def summod(modX, popcount):
    if popcount == 0:
        return 0
    a = 0
    for i, x in enumerate(modX):
        if X[i] == '1':
            a = (a + x) % popcount
    return a

modXm = list(reversed(mod(popcount - 1)))
modXp = list(reversed(mod(popcount + 1)))

s_modXm = summod(modXm, popcount - 1)
s_modXp = summod(modXp, popcount + 1)

for i in range(N):
    if X[i] == '1':
        if popcount - 1 == 0:
            print(0)
            continue
        modX, s, m = modXm, s_modXm, popcount - 1
        s = (s + m - modX[i]) % m
    else:
        modX, s, m = modXp, s_modXp, popcount + 1
        s = (s + modX[i]) % m
    ans = 1
    while True:
        pc = bin(s).count('1')
        if pc == 0:
            break
        s = s % pc
        ans += 1
    print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7) #再帰関数の上限,10**5以上の場合python
import math
from copy import copy, deepcopy
from copy import deepcopy as dcp
from operator import itemgetter
from bisect import bisect_left, bisect, bisect_right#2分探索
#bisect_left(l,x), bisect(l,x)#aはソート済みである必要あり。aの中からx未満の要素数を返す。rightだと以下
from collections import deque, defaultdict
#deque(l), pop(), append(x), popleft(), appendleft(x)
#q.rotate(n)で → にn回ローテート
from collections import Counter#文字列を個数カウント辞書に、
#S=Counter(l),S.most_common(x),S.keys(),S.values(),S.items()
from itertools import accumulate,combinations,permutations,product#累積和
#list(accumulate(l))
from heapq import heapify,heappop,heappush
#heapify(q),heappush(q,a),heappop(q) #q=heapify(q)としないこと、返り値はNone
#import fractions#古いatcoderコンテストの場合GCDなどはここからimportする
from functools import reduce,lru_cache#pypyでもうごく
#@lru_cache(maxsize = None)#maxsizeは保存するデータ数の最大値、2**nが最も高効率
from decimal import Decimal

def input(): 
    x=sys.stdin.readline()
    return x[:-1] if x[-1]=="\n" else x
def printe(*x):print("## ",*x,file=sys.stderr)
def printl(li): _=print(*li, sep="\n") if li else None
def argsort(s, return_sorted=False): 
    inds=sorted(range(len(s)), key=lambda k: s[k])
    if return_sorted: return inds, [s[i] for i in inds]
    return inds
def alp2num(c,cap=False): return ord(c)-97 if not cap else ord(c)-65
def num2alp(i,cap=False): return chr(i+97) if not cap else chr(i+65)
def matmat(A,B):
    K,N,M=len(B),len(A),len(B[0])
    return [[sum([(A[i][k]*B[k][j]) for k in range(K)]) for j in range(M)] for i in range(N)]
def matvec(M,v):
    N,size=len(v),len(M)
    return [sum([M[i][j]*v[j] for j in range(N)]) for i in range(size)]
def T(M):
    n,m=len(M),len(M[0])
    return [[M[j][i] for j in range(n)] for i in range(m)]
def main():
    mod = 1000000007
    #w.sort(key=itemgetter(1),reverse=True)  #二個目の要素で降順並び替え

    N = int(input())
    s = input()
    #N, K = map(int, input().split())
    #A = tuple(map(int, input().split())) #1行ベクトル
    #L = tuple(int(input()) for i in range(N)) #改行ベクトル
    #S = tuple(tuple(map(int, input().split())) for i in range(N)) #改行行列
    def bin(x): return format(x, 'b')
    def bitcount(x): #xは64bit整数
      x= x - ((x >> 1) & 0x5555555555555555)
      x= (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)
      x= (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f 
      x+= (x >> 8); x+= (x >> 16); x+= (x >> 32) 
      return x & 0x7f
    
    @lru_cache(None)
    def r(n):
        if n==0:
            return 0
        bc=bitcount(n)
        return r(n%bc)+1

    mod=s.count("1")
    c1=0
    c2=0
    cur1=1%(mod+1)
    
    if mod>1:
        cur2=1%(mod-1)
        for i in range(N):
            if s[-1-i]=="1":
                c1+=cur1
                c1%=(mod+1)
                c2+=cur2
                c2%=(mod-1)

            cur1=cur1*2%(mod+1)
            cur2=cur2*2%(mod-1)
    else:
        for i in range(N):
            if s[-1-i]=="1":
                c1+=cur1
                c1%=(mod+1)
            cur1=cur1*2%(mod+1)



    for i in range(N):
        if s[i]=="1":
            f=-1
            cmod=mod-1
        else:
            f=1
            cmod=mod+1

        if cmod==0:
            print(0)
            continue
        
        if f==1:
            n=c1+pow(2,N-1-i,cmod)
            n%=cmod
        else:
            n=c2-pow(2,N-1-i,cmod)
            n%=cmod

        print(1+r(n))
    #printe(c1,c2)





if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n=int(input())
x=input()
import sys
sys.setrecursionlimit(10**7)
if n==1:
  print(0 if x=='1' else 1)
  exit()
def pc(x):
  a=bin(x)[2:]
  return a.count('1')
def func(x):
  if x==0:
    return 0
  else:
    return func(x%pc(x))+1
pcx=x.count('1')
if pcx==0:
  for _ in range(n):
    print(1)
else:
  x0,x1=0,0
  for i in range(n):
    if x[i]=='1':
      if pcx!=1:
        x0+=pow(2,n-1-i,pcx-1)
        x0%=pcx-1
      x1+=pow(2,n-1-i,pcx+1)
      x1%=pcx+1
  for i in range(n):
    ans=0
    if x[i]=='1':
      if pcx==1:
        print(0)
      else:
        xx=x0-pow(2,n-1-i,pcx-1)
        xx%=pcx-1
        print(func(xx)+1)
    else:
      xx=x1+pow(2,n-1-i,pcx+1)
      xx%=pcx+1
      print(func(xx)+1)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7) #再帰関数の上限,10**5以上の場合python
import math
from copy import copy, deepcopy
from copy import deepcopy as dcp
from operator import itemgetter
from bisect import bisect_left, bisect, bisect_right#2分探索
#bisect_left(l,x), bisect(l,x)#aはソート済みである必要あり。aの中からx未満の要素数を返す。rightだと以下
from collections import deque, defaultdict
#deque(l), pop(), append(x), popleft(), appendleft(x)
#q.rotate(n)で → にn回ローテート
from collections import Counter#文字列を個数カウント辞書に、
#S=Counter(l),S.most_common(x),S.keys(),S.values(),S.items()
from itertools import accumulate,combinations,permutations,product#累積和
#list(accumulate(l))
from heapq import heapify,heappop,heappush
#heapify(q),heappush(q,a),heappop(q) #q=heapify(q)としないこと、返り値はNone
#import fractions#古いatcoderコンテストの場合GCDなどはここからimportする
from functools import reduce,lru_cache#pypyでもうごく
#@lru_cache(maxsize = None)#maxsizeは保存するデータ数の最大値、2**nが最も高効率
from decimal import Decimal

def input(): 
    x=sys.stdin.readline()
    return x[:-1] if x[-1]=="\n" else x
def printe(*x):print("## ",*x,file=sys.stderr)
def printl(li): _=print(*li, sep="\n") if li else None
def argsort(s, return_sorted=False): 
    inds=sorted(range(len(s)), key=lambda k: s[k])
    if return_sorted: return inds, [s[i] for i in inds]
    return inds
def alp2num(c,cap=False): return ord(c)-97 if not cap else ord(c)-65
def num2alp(i,cap=False): return chr(i+97) if not cap else chr(i+65)
def matmat(A,B):
    K,N,M=len(B),len(A),len(B[0])
    return [[sum([(A[i][k]*B[k][j]) for k in range(K)]) for j in range(M)] for i in range(N)]
def matvec(M,v):
    N,size=len(v),len(M)
    return [sum([M[i][j]*v[j] for j in range(N)]) for i in range(size)]
def T(M):
    n,m=len(M),len(M[0])
    return [[M[j][i] for j in range(n)] for i in range(m)]
def main():
    mod = 1000000007
    #w.sort(key=itemgetter(1),reverse=True)  #二個目の要素で降順並び替え

    N = int(input())
    s = input()
    #N, K = map(int, input().split())
    #A = tuple(map(int, input().split())) #1行ベクトル
    #L = tuple(int(input()) for i in range(N)) #改行ベクトル
    #S = tuple(tuple(map(int, input().split())) for i in range(N)) #改行行列
    def bin(x): return format(x, 'b')
    def bitcount(x): return bin(x).count("1")
    
    #@lru_cache(None)
    def r(n):
        if n==0:
            return 0
        bc=bitcount(n)
        return r(n%bc)+1

    mod=s.count("1")
    c1=0
    c2=0
    cur1=1%(mod+1)
    
    if mod>1:
        cur2=1%(mod-1)
        for i in range(N):
            if s[-1-i]=="1":
                c1+=cur1
                c1%=(mod+1)
                c2+=cur2
                c2%=(mod-1)

            cur1=cur1*2%(mod+1)
            cur2=cur2*2%(mod-1)
    else:
        for i in range(N):
            if s[-1-i]=="1":
                c1+=cur1
                c1%=(mod+1)
            cur1=cur1*2%(mod+1)



    for i in range(N):
        if s[i]=="1":
            f=-1
            cmod=mod-1
        else:
            f=1
            cmod=mod+1

        if cmod==0:
            print(0)
            continue
        
        if f==1:
            n=c1+pow(2,N-1-i,cmod)
            n%=cmod
        else:
            n=c2-pow(2,N-1-i,cmod)
            n%=cmod

        print(1+r(n))
    #printe(c1,c2)





if __name__ == "__main__":
    main()