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:
N=int(input())
X=input()

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

cnt=[0]*N
for i in range(1,N):
    p = popcount(i)
    cnt[i]=cnt[i%p]+1


P=X.count("1")

#MODSPP[i]=2**i%(P+1)
MODSPP=[0]*N
MODSPM=[0]*N

PP=P+1
if P-1<=0:
    PM=1
else:
    PM=P-1

MODSPP[0]=1%PP
MODSPM[0]=1%PM

for i in range(1,N):
    MODSPP[i]=(MODSPP[i-1]*2)%PP
    MODSPM[i]=(MODSPM[i-1]*2)%PM



MODSX_PP=0
MODSX_PM=0
for i in range(N):
    if X[i]=="1":
        MODSX_PP+=MODSPP[N-i-1]
        MODSX_PM+=MODSPM[N-i-1]
    MODSX_PP%=PP
    MODSX_PM%=PM


for i in range(N):
    if X[i]=="0":
        ret=MODSX_PP+MODSPP[N-i-1]
        ret%=PP
        print(cnt[ret]+1)
    else:
        if P-1<=0:
            print(0)
        else:
            ret=(MODSX_PM-MODSPM[N-i-1]+PM)%PM
            print(cnt[ret]+1)

Submission status: Accepted

Solution code:
#from collections import deque,defaultdict
printn = lambda x: print(x,end='')
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True # and False
BIG = 10**18
R = 10**9 + 7
#R = 998244353

def ddprint(x):
  if DBG:
    print(x)

def foo(y):
    ans = 0
    while y>0:
        z = y
        sm = 0
        for i in range(20):
            if (1<<i)&z != 0:
                sm += 1
                z -= 1<<i
                if z==0:
                    break
        y = y%sm
        ans += 1
    #ddprint(f"foo {y=} {ans=}")
    return ans

n = inn()
x = ins()
m = list(x).count('1')
xn = int(x,2)
xremm = xn%(m-1) if m>1 else 0
xremp = xn%(m+1)
iremm = [0]*n
iremp = [0]*n
if m>1:
    iremm[0] = 1
iremp[0] = 1
for i in range(1,n):
    iremp[i] = (2*iremp[i-1])%(m+1)
    if m>1:
        iremm[i] = (2*iremm[i-1])%(m-1)

#ddprint(f"{m=} {xn=} {xremm=} {xremp=}")
#ddprint(iremm)
#ddprint(iremp)

for i in range(n):
    if x[i]=='1':
        if m==1:
            print(0)
        else:
            y = (xremm-iremm[n-1-i])%(m-1)
            print(foo(y)+1)
    else:
        y = (xremp+iremp[n-1-i])%(m+1)
        #ddprint(f"xrp {xremp} ir {iremp[n-1-i]} m+1 {m+1} {y=}")
        print(foo(y)+1)

Submission status: Accepted

Solution code:
N=int(input())
X=input()
def fx(n,c):
    if c==0:
        return 0
    b=n%c
    if b==0:
        return 1
    if b==1 or b==2:
        return 2
    t=bin(b).count("1")
    return fx(b,t)+1
c=X.count("1")
n=int(X,2)
lp=[1]*N
lm=[1]*N
for i in range(N-2,-1,-1):
    lp[i]=2*lp[i+1]%(c+1)
    if c==1:
        lm[i]=1
    else:
        lm[i]=2*lm[i+1]%(c-1)
np=n%(c+1)
if c>1:
    nm=n%(c-1)
else:
    nm=1
for i in range(N):
    if X[i]=="0":
        print(fx(np+lp[i],c+1))
    else:
        print(fx(nm-lm[i],c-1))

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

#from collections import defaultdict
#from heapq import heappush, heappop
#import numpy as np
import sys

sys.setrecursionlimit(10**6)
input = sys.stdin.buffer.readline
INF = 10 ** 9 + 1  # sys.maxsize # float("inf")
MOD = 10 ** 9 + 7

debug_indent = 0


def debug(*x):
    global debug_indent
    x = list(x)
    indent = 0
    if x[0].startswith("enter") or x[0][0] == ">":
        indent = 1
    if x[0].startswith("leave") or x[0][0] == "<":
        debug_indent -= 1
    x[0] = "  " * debug_indent + x[0]
    print(*x, file=sys.stderr)
    debug_indent += indent


def solve(N, X):
    o1 = ord("1")

    def f(n):
        p = bin(n).count("1")
        return n % p

    table = [0] * 20
    for i in range(1, 20):
        x = f(i)
        if x == 0:
            table[i] = 1
        else:
            table[i] = table[x] + 1

    numOne = X.count(o1)
    ret = [0] * N

    # debug(": numOne", numOne)
    v = 0
    mod = numOne + 1
    p2mod_p1 = [0] * N
    p = 1
    for j in range(N):
        v *= 2
        v %= mod
        if (X[j] == o1):
            v += 1
        p2mod_p1[j] = p
        p *= 2
        p %= mod

    xmod_p1 = v % mod  # X mod (bc(X) + 1)
    xmod_m1 = 0  # X mod (bc(X) - 1)
    if numOne > 1:
        p = 1
        p2mod_m1 = [0] * N
        v = 0
        mod = numOne - 1
        for j in range(N):
            v *= 2
            v %= mod
            if (X[j] == o1):
                v += 1
            xmod_m1 = v % mod
            p2mod_m1[j] = p
            p *= 2
            p %= mod

    # debug(": xmod_p1, xmod_m1", xmod_p1, xmod_m1)
    # debug(": p2mod_p1, p2mod_m1", p2mod_p1, p2mod_m1)

    for i in range(N):
        if X[i] == o1:
            mod = numOne - 1
            if mod == 0:
                # already 0
                ret[i] = 0
                continue
            v2 = (xmod_m1 - p2mod_m1[-1-i]) % mod
        else:
            mod = numOne + 1
            v2 = (xmod_p1 + p2mod_p1[-1-i]) % mod
        # v = 0
        # for j in range(N):
        #     v *= 2
        #     v %= mod
        #     if (X[j] == o1) ^ (i == j):
        #         v += 1
        # v %= mod
        # debug(": v, v2", v, v2)
        # assert v == v2
        v = v2

        # debug(": v", v)
        if v == 0:
            ret[i] = 1
            continue
        if v < 20:
            ret[i] = table[v] + 1
            continue

        v = f(v)
        ret[i] = table[v] + 2

    # debug(": table", table)
    # debug(": ret", ret)
    return ret


def main():
    # parse input
    N = int(input())
    X = input().strip()
    print(*solve(N, X), sep="\n")


# tests
T1 = """
3
011
"""


def test_T1():
    """
    >>> as_input(T1)
    >>> main()
    2
    1
    1
    """


T2 = """
23
00110111001011011001110
"""


def test_T2():
    """
    >>> as_input(T2)
    >>> main()
    2
    1
    2
    2
    1
    2
    2
    2
    2
    2
    2
    2
    2
    2
    2
    2
    2
    2
    2
    2
    2
    1
    3
    """


T3 = """
100
1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
"""


# def test_T3():
#     """
#     >>> as_input(T3)
#     >>> main()
#     result
#     """
# add tests above


def _test():
    import doctest
    doctest.testmod()


def as_input(s):
    "use in test, use given string as input file"
    import io
    global read, input
    f = io.StringIO(s.strip())

    def input():
        return bytes(f.readline(), "ascii")

    def read():
        return bytes(f.read(), "ascii")


USE_NUMBA = False
if (USE_NUMBA and sys.argv[-1] == 'ONLINE_JUDGE') or sys.argv[-1] == '-c':
    print("compiling")
    from numba.pycc import CC
    cc = CC('my_module')
    cc.export('solve', solve.__doc__.strip().split()[0])(solve)
    cc.compile()
    exit()
else:
    input = sys.stdin.buffer.readline
    read = sys.stdin.buffer.read

    if (USE_NUMBA and sys.argv[-1] != '-p') or sys.argv[-1] == "--numba":
        # -p: pure python mode
        # if not -p, import compiled module
        from my_module import solve  # pylint: disable=all
    elif sys.argv[-1] == "-t":
        print("testing")
        _test()
        sys.exit()
    elif sys.argv[-1] != '-p' and len(sys.argv) == 2:
        # input given as file
        input_as_file = open(sys.argv[1])
        input = input_as_file.buffer.readline
        read = input_as_file.buffer.read

    main()

Submission status: Accepted

Solution code:
n = int(input())
x = input()
def cal(num):
    A = 1
    while num>0:
        X = bin(num)
        X = str(X)
        Y = X.count("1")
        num = num%Y
        A += 1
    return(A)
y = x.count("1")
if (y==0):
    ans = [1]*n
    print(*ans, sep="\n")
    exit()
elif (y==1):
    w1 = []
    wa = 1
    for i in range(n):
        wa %= y+1
        w1.append(wa)
        wa *= 2
    w1.reverse()
    a1 = 0
    for i in range(n):
        if (x[i]=="1"):
            a1 += w1[i]
    a1 %= y+1
    ans = []
    for i in range(n):
        if (x[i]=="0"):
            tnp = a1
            tnp += w1[i]
            tnp %= y+1
            ans.append(cal(tnp))
        else:
            ans.append(0)
    print(*ans, sep="\n")
    exit()
        
w1 = []
w2 = []
wa = 1
for i in range(n):
    wa %= y+1
    w1.append(wa)
    wa *= 2
wa = 1
for i in range(n):
    wa %= y-1
    w2.append(wa)
    wa *= 2
#print(w1,w2)
w1.reverse()
w2.reverse()
a1 = 0
a2 = 0
for i in range(n):
    if (x[i]=="1"):
        a1 += w1[i]
        a2 += w2[i]
a1 %= y+1
a2 %= y-1
#print(a1,a2)
ans = []
for i in range(n):
    if (x[i]=="0"):
        tnp = a1
        tnp += w1[i]
        tnp %= y+1
        ans.append(cal(tnp))
    else:
        tnp = a2
        tnp -= w2[i]
        tnp %= y-1
        ans.append(cal(tnp))
    #print(tnp)
print(*ans, sep="\n")

Submission status: Accepted

Solution code:
n = int(input())
x = input()
mod_num1 = [0 for i in range(n+1)]
mod_num2 = [0 for i in range(n+1)]
mod_num3 = [0 for i in range(n+1)]
num2 = x.count('1')
if num2 == 0:
    for i in range(n):
        print(1)
    exit()
elif num2 == 1:
    index = x.index('1')
    for i in range(n):
        if x[i] == '1':
            print(0)
        else:
            if index == n-1 or i == n-1:
                print(2)
            else:
                print(1)
    exit()
num1 = num2 - 1
num3 = num2 + 1
for i in range(n):
    if x[i] == '1':
        mod_num1[i] = pow(2, n-i-1 ,num1)
        mod_num2[i] = pow(2, n-i-1, num2)
        mod_num3[i] = pow(2, n-i-1, num3)
def popcount(num):
    res = 0
    while num != 0:
        res += 1
        num = num % "{:b}".format(num).count('1')
    return res
s_1 = sum(mod_num1)
s_2 = sum(mod_num2)
s_3 = sum(mod_num3)
for i in range(n):
    if x[i] == '1':
        print(popcount((s_1 - pow(2, n-i-1, num1)) % num1) + 1)
    else:
        print(popcount((s_3 + pow(2, n-i-1, num3)) % num3) + 1)

Submission status: Accepted

Solution code:
def popcount(n):
    count = 0
    while n !=0:
        k = bin(n)[2:len(bin(n))].count("1")
        n = n%k
        count+=1
    return count


N = int(input())

X = list(map(int,list(input())))

c = X.count(1)

amari_c = 0#Xをcで割ったあまり
amari_c_dic = 0
amari_c_inc = 0

for i in range(0,N,1):
    if c > 0:
        amari_c = (amari_c + X[N-i-1]*pow(2,i,c))%c
    if c-1 > 0:
        amari_c_dic = (amari_c_dic + X[N-i-1]*pow(2,i,c-1))%(c-1)
    amari_c_inc = (amari_c_inc + X[N-i-1]*pow(2,i,c+1))%(c+1)

for i in range(0,N,1):
    if X[i]==0:#1にはんてんするので　
            tmp = (amari_c_inc + pow(2,N-i-1,c+1))%(c+1)
            print(1+popcount(tmp))

    elif X[i]==1:
        if c-1 >0:
            tmp = (amari_c_dic - pow(2,N-i-1,c-1))%(c-1)
            print(1+popcount(tmp))
        else:
            print(0)

Submission status: Accepted

Solution code:
def func(N):
    return N%bin(N).count("1")

N = int(input())
X = input()

popcount = X.count("1")
X_num = int(X,2)

O = X_num%(popcount+1)
if popcount==1:
    I = 0
else:
    I = X_num%(popcount-1)

bO = 1
bI = 1

ans= []
for i in range(N):
    if X[-1-i]=="0":
        hoge = (O + bO)%(popcount+1)
    else:
        if popcount==1:
            ans.append(0)
            continue
        hoge = (I - bI)%(popcount-1)
    count = 1
    while hoge:
        hoge = func(hoge)
        count += 1
    ans.append(count)
    bO = (bO*2)%(popcount+1)
    if popcount != 1:
        bI = (bI*2)%(popcount-1)

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

Submission status: Accepted

Solution code:
N = int(input())
X = list(map(int, input()))[::-1]
p = sum(X)

if p==0:
    for _ in range(N):
        print(1)
    exit()

if p==1:
    if X[0]==0:
        ans = [2]
        for n in range(1, N):
            ans.append(1 if X[n]==0 else 0)
    else:
        ans = [0] + [2]*(N-1)

    for a in ans[::-1]:
        print(a)
        
    exit()
    

pp = p+1
rp = []
k = 1
for n in range(N):
    rp.append(k%pp)
    k = k*2%pp

sp = 0
for r,x in zip(rp, X):
    if x==1: sp = (sp+r)%pp
    
pn = p-1
rn = []
k = 1
for n in range(N):
    rn.append(k%pn)
    k = k*2%pn

sn = 0
for r,x in zip(rn, X):
    if x==1: sn = (sn+r)%pn

def popcount(x):
    p = 0
    while x:
        p += x&1
        x>>=1
    return p

def op(x):
    p = popcount(x)
    return x%p

def f(x):
    n = 0
    while x:
        n+=1
        x = op(x)
    return n
    
ans = []
for n,x in enumerate(X):
    if x==0:
        ans.append(1+f((sp+rp[n])%pp))
    else:
        ans.append(1+f((sn-rn[n])%pn))

for a in ans[::-1]:
    print(a)

Submission status: Accepted

Solution code:
N = int(input())
X = list(input())
X = [int(x) for x in X]
X.reverse()

def popcnt0(n):
    c = 0
    for i in range(64):
        c += (n >> i) & 1
    return c
  
#最初にNまでの表を作る
D = [0 for _ in range(N+1)]
D[1] = 1
for i in range(2, N+1):
  D[i] = D[i % popcnt0(i)] + 1
  
#次に、Xの１のカウントを求める
ct_1 = 0
for x in X:
  if x == 1:
    ct_1 += 1

#ct_1-1による2^n mod
if ct_1 > 1:
  B = [0 for _ in range(N)]
  j = 1
  for i in range(N):
    B[i] = j
    j *= 2
    j %= ct_1 - 1 


#ct_1+1による2^n mod
C = [0 for _ in range(N)]
j = 1
for i in range(N):
  C[i] = j
  j *= 2
  j %= ct_1 + 1 

#X mod ct_1-1 と、X mod ct_1+1 を求める
s = 0
t = 0
for i in range(N):
  if ct_1 > 1:
    s += X[i] * B[i]
    s %= ct_1-1
  t += X[i] * C[i] 
  t %= ct_1+1

X.reverse()
#print(X)
#print(D,B,C)
i = N-1
#各場合の1回目の操作後の数を計算して、Dをつかって答えを出す
for x in X:
  if x == 1:
    if ct_1 > 1:
      k = (s - B[i]) % (ct_1-1)
    else:
      print(0)
  else:
    k = (t + C[i]) % (ct_1+1)        
  i -= 1
  if ct_1 > 1 or x == 0:
    print(D[k]+1)

Submission status: Accepted

Solution code:
n = int(input())
x = list(input())
y = x.count("1")
s, t = y - 1, y + 1
p = [1] * 20
for i in range(1, 20):
    p[i] = p[i - 1] * 2
p.sort(reverse = True)
a, b, u, v = 1 / 2, 1 / 2, 0, 0
m1, m2 = [0] * n, [0] * n
if not s == 0:
    for i in range(1, n + 1):
        a += a
        a %= s
        b += b
        b %= t
        m1[i - 1] = a
        m2[i - 1] = b
        if x[-i] == "1":
            u += a
            v += b
else:
    for i in range(1, n + 1):
        b += b
        b %= t
        m2[i - 1] = b
        if x[-i] == "1":
            v += b
ans = [1] * n
if not s == 0:
    for i in range(1, n + 1):
        if x[-i] == "1":
            j = (u - m1[i - 1]) % s
        else:
            j = (v + m2[i - 1]) % t
        if not j == 0:
            while not j == 0:
                ans[-i] += 1
                l = j
                cnt = 0
                for k in p:
                    if l == 0:
                        break
                    if k <= l:
                        cnt += 1
                        l -= k
                j = j % cnt
else:
    for i in range(1, n + 1):
        if x[-i] == "1":
            ans[-i] = 0
        else:
            j = (v + m2[i - 1]) % t
            if not j == 0:
                while not j == 0:
                    ans[-i] += 1
                    l = j
                    cnt = 0
                    for k in p:
                        if l == 0:
                            break
                        if k <= l:
                            cnt += 1
                            l -= k
                    j = j % cnt
for i in ans:
    print(i)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
N = int(input())
X = input().strip()

def solve(N,X):
    if not '1' in X:
        for i in range(N):
            print(1)
        exit()

    def popcount(n):
        t = 0
        while n > 0:
            k = bin(n).count('1')
            n %= k
            t += 1
        return t

    X1 = X.count('1')

    Rp1 = []
    Rm1 = []
    Bp1 = []
    Bm1 = []

    for i, x in enumerate(list(X[::-1])):
        tp1 = pow(2,i,X1+1)
        if X1-1 > 0:
            tm1 = pow(2,i,X1-1)
        else:
            tm1 = 0
        Bp1.append(tp1)
        Bm1.append(tm1)
        if x == '1':
            Rp1.append(tp1)
            Rm1.append(tm1)
        else:
            Rp1.append(0)
            Rm1.append(0)

    basep1 = sum(Rp1) % (X1+1)
    if X1-1 > 0:
        basem1 = sum(Rm1) % (X1-1)
    else:
        basem1 = 0
    Rp1 = Rp1[::-1]
    Rm1 = Rm1[::-1]
    Bp1 = Bp1[::-1]
    Bm1 = Bm1[::-1]

    #print("base",basep1)
    #print("base",basem1)
    for bp1,bm1,x in zip(Bp1,Bm1,X):
        if x == '1':
            t = basem1 - bm1
            MOD = X1 - 1
            if MOD <= 0:
                print(0)
                continue
        else:
            t = basep1 + bp1
            MOD = X1 + 1
        #print("x",x,"t",t)
        #print(t % MOD,MOD)
        print(popcount(t % MOD) + 1)

solve(N,X)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

'''
Author: andyli
Time: 2020-07-11 19:58:49
'''

def main():
    n = int(input())
    x = input()
    popcounts = x.count('1')
    if popcounts == 1:
        for i in range(n):
            if x[i] == '1':
                print(0)
                continue
            if (i == n-1 and x[-1] == '0') or (i != n-1 and x[-1] == '1'):
                print(2)
            else:
                print(1)
        return
    if popcounts == 0:
        for i in range(n):
            print(1)
        
        return
    modmi = [0 for i in range(n+2)]
    modpl = [0 for i in range(n+2)]
    s = 1
    for i in range(0,n+2):
        s %= (popcounts-1)
        modmi[i] = s
        s <<= 1
    s = 1
    for i in range(0,n+2):
        s %= (popcounts+1)
        modpl[i] = s
        s <<= 1
    demodmi = int(x,base=2)%(popcounts-1)
    demodpl = int(x,base=2)%(popcounts+1)
    def count(n):
        ans = 0
        while n > 0:
            n %= bin(n).count('1')
            ans += 1
        return ans
    # print('\t',demodmi,demodpl)
    for i in range(n):
        if x[i] == '0':
            demodmi = (demodmi + modmi[(n-i-1)]) % (popcounts-1)
            demodpl = (demodpl + modpl[(n-i-1)]) % (popcounts+1)
            pass
        else:
            demodmi = (demodmi - modmi[(n-i-1)]) % (popcounts-1)
            demodpl = (demodpl - modpl[(n-i-1)]) % (popcounts+1)
            pass
        mod = demodmi if x[i] == '1' else demodpl
        # print('\t', mod)
        print(1 + count(mod))
        if x[i] == '1':
            demodmi = (demodmi + modmi[(n-i-1)]) % (popcounts-1)
            demodpl = (demodpl + modpl[(n-i-1)]) % (popcounts+1)
            pass
        else:
            demodmi = (demodmi - modmi[(n-i-1)]) % (popcounts-1)
            demodpl = (demodpl - modpl[(n-i-1)]) % (popcounts+1)
            pass

    return

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def base10toN(num, base):
    converted_string, modstring = "", ""
    currentnum = num
    if not num:
        return '0'
    while currentnum:
        mod = currentnum % base
        currentnum = currentnum // base
        converted_string = chr(48 + mod + 7*(mod > 10)) + converted_string
    return converted_string
n=int(input())
pop=[0]*(2*10**5+1)
for i in range(1,2*10**5+1):
  temp=base10toN(i,2)
  ans=0
  for j in range(len(temp)):
    if temp[j]=='1':
      ans+=1
  r=i%ans
  pop[i]=pop[r]+1
x=input()
ones=0
ans1=[]
for i in range(n):
  if x[i]=='1':
    ones+=1
dividemore=0
divideless=0
for i in range(n):
  if x[i]=='1':
    dividemore=(pow(2,n-1-i,ones+1)+dividemore)%(ones+1)
    if ones>=2:
      divideless=(pow(2,n-1-i,ones-1)+divideless)%(ones-1)
for i in range(n):
  counter=0
  if x[i]=='0':
    temp=(dividemore+pow(2,n-1-i,ones+1))%(ones+1)
  else:
    if ones==1:
      ans1.append('0')
      continue
    else:
      temp=(divideless-pow(2,n-1-i,ones-1))%(ones-1)
  ans1.append(str(pop[temp]+1))
print(' '.join(ans1))

Submission status: Accepted

Solution code:
N = int(input())
X = input()

X_pc = X.count("1")
X_res_m1 = 0
X_res_p1 = 0
for i, s in enumerate(reversed(X)):
    if s == "1":
        if X_pc > 1:
            X_res_m1 += pow(2, i, X_pc - 1)
            X_res_m1 %= X_pc - 1

        X_res_p1 += pow(2, i, X_pc + 1)
        X_res_p1 %= X_pc + 1

f = [-1] * (X_pc + 1)
f[0] = 0
for n in range(1, X_pc + 1):
    pc = format(n, "b").count("1")
    f[n] = f[n % pc] + 1

ans = []
for i, s in enumerate(reversed(X)):
    if s == "1":
        if X_pc > 1:
            fx = (X_res_m1 - pow(2, i, X_pc - 1)) % (X_pc - 1)
            ans.append(f[fx] + 1)
        else:
            ans.append(0)

    else:
        fx = (X_res_p1 + pow(2, i, X_pc + 1)) % (X_pc + 1)
        ans.append(f[fx] + 1)

print(*reversed(ans), sep="\n")

Submission status: Accepted

Solution code:
n = int(input())
x = input()
 
from collections import Counter
import sys
 
up = [0]*n
do = [0]*n
 
b = Counter(x)
 
if b["1"] >= 2:
    pr = b["1"]
    a = 1
    for i in range(n):
        up[n-1-i] = a
        a = a*2 % (pr+1)
    
    a = 1
    for i in range(n):
        do[n-1-i] = a
        a = a*2 % (pr-1)
        
    upsum,dosum = 0,0
    for i in range(n):
        upsum = (upsum + (int(x[i]) * up[i])) % (pr+1)
        dosum = (dosum + (int(x[i]) * do[i])) % (pr-1)
        
    pop = [0] * (n+1)
    for i in range(1,n+1):
        xx = bin(i)[2:]
        c = Counter(xx)
        pop[i] = i % c["1"]
        
    for i in range(n):
        if x[i] == "0":
            ss = (upsum + up[i]) % (pr+1)
            
            aa = 0
            for j in range(400):
                if ss == 0:
                    break
                else:
                    ss = pop[ss]
                    aa += 1
                    
            print(aa+1)
            
        elif x[i] == "1":
            ss = (dosum + (pr-1) - do[i]) % (pr-1)
            
            aa = 0
            for j in range(400):
                if ss == 0:
                    break
                else:
                    ss = pop[ss]
                    aa += 1
                    
            print(aa+1)
            
else:
    pr = b["1"]
    a = 1
    for i in range(n):
        up[n-1-i] = a
        a = a*2 % (pr+1)
 
    upsum = 0
    for i in range(n):
        upsum = (upsum + (int(x[i]) * up[i])) % (pr+1)
 
    pop = [0] * (n+1)
    for i in range(1,n+1):
        xx = bin(i)[2:]
        c = Counter(xx)
        pop[i] = i % c["1"]
    
    for j in range(n):
        if x[j] == "1":
            print(0)
        else:
            ss = (upsum + up[j]) % (pr+1)
            
            aa = 0
            for k in range(400):
                if ss == 0:
                    break
                else:
                    ss = pop[ss]
                    aa += 1
                    
            print(aa+1)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

'''
Author: andyli
Time: 2020-07-11 19:58:49
'''

import os
from io import BytesIO, IOBase
import sys


def main():
    n = int(input())
    x = input()
    popcounts = x.count('1')
    if popcounts == 1:
        for i in range(n):
            if x[i] == '1':
                print(0)
                continue
            if (i == n-1 and x[-1] == '0') or (i != n-1 and x[-1] == '1'):
                print(2)
            else:
                print(1)
        return
    if popcounts == 0:
        for i in range(n):
            print(1)
        
        return
    modmi = [0 for i in range(n+2)]
    modpl = [0 for i in range(n+2)]
    s = 1
    for i in range(0,n+2):
        s %= (popcounts-1)
        modmi[i] = s
        s <<= 1
    s = 1
    for i in range(0,n+2):
        s %= (popcounts+1)
        modpl[i] = s
        s <<= 1
    demodmi = int(x,base=2)%(popcounts-1)
    demodpl = int(x,base=2)%(popcounts+1)
    def count(n):
        ans = 0
        while n > 0:
            n %= bin(n).count('1')
            ans += 1
        return ans
    # print('\t',demodmi,demodpl)
    for i in range(n):
        if x[i] == '0':
            demodmi = (demodmi + modmi[(n-i-1)]) % (popcounts-1)
            demodpl = (demodpl + modpl[(n-i-1)]) % (popcounts+1)
            pass
        else:
            demodmi = (demodmi - modmi[(n-i-1)]) % (popcounts-1)
            demodpl = (demodpl - modpl[(n-i-1)]) % (popcounts+1)
            pass
        mod = demodmi if x[i] == '1' else demodpl
        # print('\t', mod)
        print(1 + count(mod))
        if x[i] == '1':
            demodmi = (demodmi + modmi[(n-i-1)]) % (popcounts-1)
            demodpl = (demodpl + modpl[(n-i-1)]) % (popcounts+1)
            pass
        else:
            demodmi = (demodmi - modmi[(n-i-1)]) % (popcounts-1)
            demodpl = (demodpl - modpl[(n-i-1)]) % (popcounts+1)
            pass

    return


# region fastio
BUFSIZE = 1048576


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = 'x' in file.mode or 'r' not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b'\n') + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode('ascii'))
        self.read = lambda: self.buffer.read().decode('ascii')
        self.readline = lambda: self.buffer.readline().decode('ascii')


sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
def input(): return sys.stdin.readline().rstrip('\r\n')

# endregion


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def g(n):
    c = 0
    while n > 0:
        p = 0
        n2 = n
        while n2 > 0:
            if n2%2 == 1:
                p += 1

            n2 //= 2

        n %= p
        c += 1

    return c


def modPow(a, b, mod):
    x = 1
    
    while b > 0:
        if b & 1:
            x = (x*a)%mod

        a = (a**2)%mod
        b //= 2

    return x


# def h(b, m):
#     x = 1
#     for _ in range(b):
#         x = x*2%m

#     return x


def f(N, X):
    b = sum(1 if x == '1' else 0 for x in X)

    Xplus = 0
    Xminus = 0

    for x in X:
        Xplus = (Xplus*2 + (1 if x == '1' else 0))%(b+1)
        
        if b > 1:
            Xminus = (Xminus*2 + (1 if x == '1' else 0))%(b-1)

    for i in range(N):
        if X[i] == '0':
#            X2 = (Xplus + h(N-i-1, b+1))%(b+1)
            X2 = (Xplus + modPow(2, N-i-1, b+1))%(b+1)
            print(g(X2) + 1)
        elif b > 1:
#            X2 = (Xminus - h(N-i-1, b-1))%(b-1)
            X2 = (Xminus - modPow(2, N-i-1, b-1))%(b-1)
            print(g(X2) + 1)
        else:
            print(0)


N = int(input())
X = input()
f(N, X)

Submission status: Accepted

Solution code:
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    sys.setrecursionlimit(10**7)
    INF = 10**18
    MOD = 10**9 + 7
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]
    _LI = lambda : [-int(x) for x in sys.stdin.readline().split()]
    NI = lambda : int(sys.stdin.readline())
    SI = lambda : sys.stdin.readline().rstrip()
    DD = ((1,0),(0,1),(-1,0),(0,-1))

    N = NI()
    X = SI()

    cnt = [0] * (N+1)
    for i in range(1,N+1):
        x = i % bin(i).count('1')
        if x == 0:
            cnt[i] = 1
        else:
            cnt[i] = cnt[x] + 1

    xc = X.count('1')
    xp = 0
    xm = 0
    xpb = 1
    xmb = 1
    for i in range(N-1,-1,-1):
        xp = (xp + int(X[i]) * xpb) % (xc+1)
        if xc > 1:
            xm = (xm + int(X[i]) * xmb) % (xc-1)
            xmb = (xmb * 2) % (xc - 1)
        else:
            xm = 0
            xmb = 0
        xpb = (xpb * 2) % (xc+1)

    for i in range(N):
        if X[i] == '0':
            x = (xp + pow(2,N-i-1,xc+1)) % (xc+1)
        else:
            if xc > 1:
                x = (xm - pow(2,N-i-1,xc-1)) % (xc-1)
            else:
                x = -1
        if x < 0:
            print(0)
        else:
            print(cnt[x]+1)



if __name__ == '__main__':
    main()