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:
from collections import defaultdict
from collections import deque
con = 10 ** 9 + 7; INF = float("inf")

def getlist():
	return list(map(int, input().split()))

class Graph(object):
	def __init__(self):
		self.graph = defaultdict(list)

	def __len__(self):
		return len(self.graph)

	def add_edge(self, a, b):
		self.graph[a].append(b)

class BFS(object):
	def __init__(self, graph, s, N):
		self.g = graph.graph
		self.Q = deque(); self.Q.append(s)
		self.dist = [INF] * N; self.dist[s] = 0
		while self.Q:
			v = self.Q.popleft()
			for i in self.g[v]:
				if self.dist[i] == INF:
					self.dist[i] = self.dist[v] + 1
					self.Q.append(i)

#処理内容
def main():
	N = int(input())
	X = list(map(int, list(input())))

	G = Graph()
	for i in range(1, 2 * (10 ** 5) + 1):
		cnt1 = 0
		n = i
		while True:
			if n % 2 == 1:
				cnt1 += 1
			n = int(n // 2)
			if n == 0:
				break
		a = i % cnt1; b = i
		G.add_edge(a, b)

	BF = BFS(G, 0, 2 * (10 ** 5) + 1)
	dist = BF.dist

	X1cnt = 0
	for i in X:
		if i == 1:
			X1cnt += 1

	if X1cnt == 0:
		for i in range(N):
			print(1)

	elif X1cnt == 1:
		Xplus = 0
		for i in range(N):
			Xplus += pow(2, i, X1cnt + 1) * X[-1 - i]

		for i in range(N):
			if X[i] == 1:
				print(0)
			else:
				val = Xplus
				val += pow(2, N - 1 - i, X1cnt + 1)
				val %= X1cnt + 1
				print(dist[val] + 1)

	else:
		Xplus = 0
		Xnone = 0
		Xminus = 0
		for i in range(N):
			Xplus += pow(2, i, X1cnt + 1) * X[-1 - i]
			Xnone += pow(2, i, X1cnt) * X[-1 - i]
			Xminus += pow(2, i, X1cnt - 1) * X[-1 - i]

		Xplus %= X1cnt + 1
		Xnone %= X1cnt
		Xminus %= X1cnt - 1
		for i in range(N):
			if X[i] == 1:
				val = Xminus
				val -= pow(2, N - 1 - i, X1cnt - 1)
				val %= X1cnt - 1
				print(dist[val] + 1)
			else:
				val = Xplus
				val += pow(2, N - 1 - i, X1cnt + 1)
				val %= X1cnt + 1
				print(dist[val] + 1)


if __name__ == '__main__':
	main()

Submission status: Accepted

Solution code:
import sys
import math
import bisect

def pow_mod(x, n, m):
    if n == 0:
        return 1
    ans = pow_mod(x, n // 2, m) ** 2 % m
    if n % 2 == 1:
        ans = ans * x % m
    return ans

def query_popcount(n):
    ans = 0
    while n:
        ans += n % 2
        n >>= 1
    return ans

def query_value(n):
    if n == 0:
        return 0
    m = query_popcount(n)
    return 1 + query_value(n % m)


def main():
    n = int(input())
    s = input()
    m = 0
    d = {}
    for c in s:
        if c == '1':
            m += 1
    # print('m: %d' % (m))
    if m - 1 != 0:
        val = 0
        for c in s:
            val = val * 2 + ord(c) - ord('0')
            if val >= (m - 1):
                val -= (m - 1)
        d[m-1] = val
    if m + 1 != 0:
        val = 0
        for c in s:
            val = val * 2 + ord(c) - ord('0')
            if val >= (m + 1):
                val -= (m + 1)
        d[m+1] = val
    # print('d: %s' % str(d))
    ans = []
    for i in range(n):
        if s[i] == '0':
            r = (d[m+1] + pow_mod(2, n - 1 - i, m + 1)) % (m+1)
            val = 1 + query_value(r)
            ans.append(val)
        elif s[i] == '1':
            if m - 1 == 0:
                ans.append(0)
            else:
                r = (d[m-1] + (m-1) - pow_mod(2, n - 1 - i, m - 1)) % (m-1)
                val = 1 + query_value(r)
                ans.append(val)

    for a in ans:
        print(a)

if __name__ == "__main__":
    main()

Submission status: Accepted

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

mem = dict()
def find(n):
    if n == 0 :
        return 0
    elif n in mem :
        return mem[n]

    cur = n 
    bit_count = 0
    while cur > 0 :
        bit_count += cur%2
        cur //= 2

    if bit_count == 1 : 
        mem[n] = 1
    else :
        mem[n] = 1+find(n%bit_count)
    return mem[n] 

bit_count = sum([ int(x) for x in X ])

dp = [ [0]*N for _ in range(2)]   
def build_dp(j, v):
    if v == 0:
        return 
    st = 1
    _dp = dp[j]
    for i in range(N-1,-1,-1):
        _dp[i] = st%v
        st = (st*2)%v

build_dp(0, bit_count-1)
build_dp(1, bit_count+1)

base = [0]*2
k = 0
for v in [bit_count-1, bit_count+1]:
    st = 1 
    if v == 0 :
        continue
    for i in range(N-1,-1,-1):
        if X[i] == '1' :
            base[k] = (base[k]+st)%v
        st = (st*2)%v
    k += 1

for i in range(0,N):
    if X[i] == '1' :
        if bit_count-1 == 0 :
            print(0)
        else :
            value = (base[0]-dp[0][i]+bit_count-1) % (bit_count-1)
            print(1+find(value))
    else :
        value = (base[1]+dp[1][i]+bit_count+1) % (bit_count+1)
        print(1+find(value))

Submission status: Accepted

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

def Z(): return int(input())
def ZZ(): return [int(_) for _ in input().split()]

def main():
    N = Z()
    X = input()
    pcnt = 0
    ans = []
    for x in X:
        if x == '1': pcnt += 1
    if pcnt == 0:
        for _ in range(N):
            print(1)
            return
    Xinv = X[::-1]
    ex1 = ex2 = 1
    num1 = num2 = 0
    for x in Xinv:
        num1 += (ex1 * int(x)) % (pcnt + 1)
        num1 %= (pcnt + 1)
        if pcnt > 1:
            num2 += (ex2 * int(x)) % (pcnt - 1)
            num2 %= (pcnt - 1)
        ex1 *= 2
        ex1 %= (pcnt + 1)
        ex2 *= 2
        if pcnt > 1: ex2 %= (pcnt - 1)

    def solve(n, p, s):
        if n == 0 and s > 0: return s
        n %= p
        p = bin(n).count('1')
        return solve(n, p, s+1)

    for i in range(N):
        if X[i] == '1':
            p = pcnt - 1
            if p == 0:
                ans.append(0)
                continue
            num = num2 - pow(2, N-i-1, p)
            ans.append(solve(num, p, 0))
        else:
            p = pcnt + 1
            num = num1 + pow(2, N-i-1, p)
            ans.append(solve(num, p, 0))

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

    return

if __name__ == '__main__':
    main()

Submission status: Accepted

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

def popcount(n):
    return bin(n).count('1')

def process(n):
    return n % popcount(n)

def func(n):
    ret = 0
    while n > 0:
        n = process(n)
        ret += 1
    return ret

pcnt = X.count('1')
mods_plus = []
totalmod_plus = 0
tmp_plus = 1
pp = pcnt+1
mods_minus = []
totalmod_minus = 0
tmp_minus = 1
pm = pcnt-1
for c in reversed(X):
    if c == '1':
        totalmod_plus += tmp_plus
        totalmod_plus %= pp
    mods_plus.append(tmp_plus)
    tmp_plus = tmp_plus*2 % pp
    if pcnt != 1:
        if c == '1':
            totalmod_minus += tmp_minus
            totalmod_minus %= pm
        mods_minus.append(tmp_minus)
        tmp_minus = tmp_minus*2 % pm

for i in range(N):
    if X[i] == '1':
        if pcnt == 1:
            print(0)
        else:
            mod = mods_minus[-i-1]
            print(func((totalmod_minus - mod) % pm) + 1)
    else:
        mod = mods_plus[-i-1]
        print(func((totalmod_plus + mod) % pp) + 1)

Submission status: Accepted

Solution code:
n=int(input())
x=input()
one=x.count("1")
amari_m=0
amari_p=0
for i in range(n):
	if x[-i-1]=="1":
		amari_p+=pow(2,i,one+1)
		if one==1:
			amari_m=-1
		else:
			amari_m+=pow(2,i,one-1)
		amari_p%=one+1
		if one!=1:
			amari_m%=one-1
for i in range(n):
	cnt=0
	if x[i]=="1":
		if one==1:
			print(0)
			continue
		r=(amari_m-pow(2,(n-i-1),one-1))%(one-1)
	else:
		r=(amari_p+pow(2,(n-i-1),one+1))%(one+1)
	while r:
		r%=bin(r).count("1")
		cnt+=1
	print(cnt+1)

Submission status: Accepted

Solution code:
def popcount(x):
    return bin(x)[2:].count("1")

def f(x):
    cnt=0
    while(x>0):
        x%=popcount(x)
        cnt+=1
    return cnt

n=int(input())
s=input()
d=s.count("1")
if d==0:
    for i in range(n):
        print(1)
elif d==1:
    if s[-1]=="1":
        for i in range(n-1):
            print(2)
        else:
            print(0)
    else:
        for i in range(n-1):
            if s[i]=="1":
                print(0)
            else:
                print(1)
        print(2)
else:
    s=s[::-1]
    toaddm=1
    toaddM=1
    m=0
    M=0
    for i in range(n):
        if s[i]=="1":
            m+=toaddm
            M+=toaddM
            m%=d-1
            M%=d+1
        toaddm*=2
        toaddm%=d-1
        toaddM*=2
        toaddM%=d+1
    toaddm=-1
    toaddM=1
    res=[None for i in range(n)]
    for i in range(n):
        if s[i]=="1":
            res[i]=f((m+toaddm)%(d-1))+1
        else:
            res[i]=f((M+toaddM)%(d+1))+1
        toaddm*=2
        toaddm%=d-1
        toaddM*=2
        toaddM%=d+1
    for i in res[::-1]:
        print(i)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1<<30)

N = int(input())
X = input()
ones = X.count('1')

v1 = 0
v2 = 0
m1 = ones + 1
m2 = ones - 1
p1 = 1 % m1
p2 = 1

for i, v in enumerate(reversed(X)):
	if v == '1':
		v1 = (v1 + p1) % m1

		if m2 > 0:
			v2 = (v2 + p2) % m2

	p1 = p1 * 2 % m1
	if m2 > 0:
		p2 = p2 * 2 % m2

from functools import lru_cache

@lru_cache(maxsize=None)
def f(i):
	if i == 0: return 0

	return 1 + f(i % popcount(i))

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


for i in range(N):
	div = ones + 1 if X[i] == '0' else ones - 1
	if div == 0:
		print(0)
	elif div == 1:
		print(1)
	else:

		if div == m1:
			x = (v1 + pow(2, N-i-1, m1)) % m1
		elif div == m2:
			x = (v2 - pow(2, N-i-1, m2)) % m2
		else:
			assert False

		#print(x, (int(X, 2) ^ (1 << (N-i-1))) % div, div)

		print(1 + f(x))

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

n=II()
s=SI()
p=s.count("1")
p0=p-1
p1=p+1
pw0=[]
pw1=[]
two0=two1=1
for _ in range(n):
    pw0.append(two0)
    pw1.append(two1)
    if p0>0:two0=two0*2%p0
    two1=two1*2%p1

t0=0
t1=0
for i,c in enumerate(s[::-1]):
    if c=="1":
        if p0>0:t0=(t0+pw0[i])%p0
        t1=(t1+pw1[i])%p1

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

dp0=[-1]*n
def f0(x):
    if x==0:return 1
    if dp0[x]==-1:dp0[x]=f0(x%popcnt(x))+1
    return dp0[x]

ans=[]
for i,c in enumerate(s[::-1]):
    if p0==0 and c=="1":
        ans.append(0)
        continue
    if c=="1":
        cur=(t0-pw0[i])%p0
    else:
        cur=(t1+pw1[i])%p1
    ans.append(f0(cur))

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

Submission status: Accepted

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

x_cnt = x.count('1')
yp = 0
ym = 0
for i in range(n):
    yp *= 2
    yp += int(x[i])
    yp %= x_cnt + 1

    if x_cnt != 1:
        ym *= 2
        ym += int(x[i])
        ym %= x_cnt - 1


def count(z):
    cnt = 0
    while z:
        z = z % bin(z).count('1')
        cnt += 1
    return cnt


# print(x, x_cnt, yp, ym)

ans = [0] * n
bp = bm = 1
for i in reversed(range(n)):
    if x[i] == '0':
        z = (yp + bp) % (x_cnt + 1)
        ans[i] = 1 + count(z)
    else:
        if x_cnt == 1:
            ans[i] = 0
        else:
            z = (ym - bm + x_cnt - 1) % (x_cnt - 1)
            ans[i] = 1 + count(z)
    # print(i, z, ans[i])
    bp *= 2
    bp %= x_cnt + 1
    if x_cnt != 1:
        bm *= 2
        bm %= x_cnt - 1

print(*ans, sep='\n')

Submission status: Accepted

Solution code:
def func(n):
    ans = 0
    while n > 0:
        cnt = 0
        for i in range(33):
            if (n & (1<<i)) != 0:
                cnt += 1
        ans += 1
        n %= cnt
    return ans

def main():
    n = int(input())
    s = input()
    ans = [0]*n
    cnt = 0
    for c in s:
        if c == "1":
            cnt += 1
    ad = cnt + 1
    df = cnt - 1
    start_ad = 0
    start_df = 0
    for i in range(n):
        if ad > 0:
            if s[n-1-i] == "1":
                start_ad += pow(2, i, ad)
                start_ad %= ad
        if df > 0:
            if s[n-1-i] == "1":
                start_df += pow(2, i, df)
                start_df %= df
    for i in range(n):
        if s[i] == "0":
            ans[i] = 1
            tmp = (start_ad + pow(2, n-1-i, ad)) % ad
            ans[i] += func(tmp)
        else:
            if cnt == 1:
                ans[i] = 0
            else:
                ans[i] = 1
                tmp = (start_df - pow(2, n-1-i, df)) % df
                ans[i] += func(tmp)
    for v in ans:
        print(v)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def popcount(x):
    x -= (x >> 1) & 0x55555555
    x = (x & 0x33333333) + ((x >> 2) & 0x33333333)
    x = (x + (x >> 4)) & 0x0f0f0f0f
    x += x >> 8
    x += x >> 16
    return x & 0x3f

A = [0] * 200001
for i in range(1, 200001):
    A[i] = A[i % popcount(i)] + 1


N = int(input())
xx = input()
p = xx.count("1") - 1
q = xx.count("1") + 1

X = int(xx, 2)
xx = xx[::-1]

if p: a = X % p
b = X % q
s = 1
t = 1
ANS = []
for i, x in enumerate(xx):
    if x == "0":
        ANS.append(A[(b + t) % q] + 1)
    else:
        ANS.append(A[(a - s) % p] + 1 if p else 0)
    if p: s = s * 2 % p
    t = t * 2 % q

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

Submission status: Accepted

Solution code:
from collections import defaultdict
def main():
    N = int(input())
    S = input()
    D = defaultdict(bool)
    cnt = 0
    all1 = 0
    all2 = 0
    for i in range(N):
        if S[i] == "1":
            D[i] = True
            cnt += 1
        else:
            D[i] == False

    for i in range(N):
        if S[i] == "1":
            all1 += pow(2, N-1-i, cnt+1)
            if cnt != 1:
                all2 += pow(2, N-1-i, cnt-1)

    for i in range(N):
        P = 0
        if S[i] == "1":
            if cnt == 1:
                print(0)
                continue
            else:
                P += all2-pow(2, N-1-i, cnt-1)
            ans = 1
            P = P % (cnt-1)
            while P:
                c = P
                mod = 0
                while c:
                    mod += c & 1
                    c = c >> 1
                P = P % mod
                ans += 1
            print(ans)
            continue
        else:
            P += all1+pow(2, N-1-i, cnt+1)
            ans = 1
            P = P % (cnt+1)
            while P:
                c = P
                mod = 0
                while c:
                    mod += c & 1
                    c = c >> 1
                P = P % mod
                ans += 1
            print(ans)
if __name__=="__main__":
    main()

Submission status: Accepted

Solution code:
n = int(input())
x = input()
pcnt = x.count("1")
pp = pcnt+1
pn = pcnt-1
ansb = [0,0,0]
def modpcnt(x):
  if x == 0:
    return 0
  b = x.bit_length()
  mod = 0
  for i in range(b):
    if x&1<<i:
      mod += 1
  return 1+modpcnt(x%mod)
for i in range(n):
  if x[i] == "1":
    ansb[1] += pow(2,n-i-1,pcnt)
    ansb[1] %= pcnt
    ansb[0] += pow(2,n-i-1,pp)
    ansb[0] %= pp
    if pn == 0:
      ansb[2] = 0
    else:
      ansb[2] += pow(2,n-i-1,pn)
      ansb[2] %= pn
for i in range(n):
  if x[i] == "0":
    tmp = (ansb[0]+pow(2,n-i-1,pp))%pp
    print(modpcnt(tmp)+1)
  else:
    if pn == 0:
      print(0)
    else:
      tmp = (ansb[2]-pow(2,n-i-1,pn))%pn
      print(modpcnt(tmp)+1)

Submission status: Accepted

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

data=[0]*N
for i in range(1,N):
    temp=0
    for j in range(20):
        temp+=(i>>j &1)
    next=i%temp
    data[i]=data[next]+1

base=sum(int(X[i]) for i in range(N))

if base==0:
    baseup=0
    for i in range(N):
        baseup=(baseup*2)%(base+1)
        baseup=(baseup+int(X[i]))%(base+1)

    for i in range(N):
        if X[i]=="1":
            temp=(basedown-pow(2,N-1-i,base-1))%(base-1)
            print(1+data[temp])
        else:
            temp=(baseup+pow(2,N-1-i,base+1))%(base+1)
            print(1+data[temp])
elif base==1:
    baseup=0
    for i in range(N):
        baseup=(baseup*2)%(base+1)
        baseup=(baseup+int(X[i]))%(base+1)

    for i in range(N):
        if X[i]=="1":
            print(0)
        else:
            temp=(baseup+pow(2,N-1-i,base+1))%(base+1)
            print(1+data[temp])
else:
    basedown=0
    baseup=0
    for i in range(N):
        basedown=(basedown*2)%(base-1)
        baseup=(baseup*2)%(base+1)
        basedown=(basedown+int(X[i]))%(base-1)
        baseup=(baseup+int(X[i]))%(base+1)

    for i in range(N):
        if X[i]=="1":
            temp=(basedown-pow(2,N-1-i,base-1))%(base-1)
            print(1+data[temp])
        else:
            temp=(baseup+pow(2,N-1-i,base+1))%(base+1)
            print(1+data[temp])

Submission status: Accepted

Solution code:
N = int(input())
X = list(input())
P = X.count("1")
if P != 1:
    P1 = 0
    P2 = 0
    for i in range(N):
        if X[i] == "1":
            P1 += pow(2,N-i-1,P-1)
            P1 %= P-1
            P2 += pow(2,N-i-1,P+1)
            P2 %= P+1
    for i in range(N):
        count = 1
        if X[i] == "0":
            cur = P2+pow(2,N-i-1,P+1)
            cur %= P+1
        else:
            cur = P1-pow(2,N-1-i,P-1)
            cur %= P-1
        while cur > 0:
            mod = bin(cur).count("1")
            cur %= mod
            count += 1
        print(count)
else:
    P2 = 0
    for i in range(N):
        if X[i] == "1":
            P2 += pow(2,N-i-1,P+1)
    for i in range(N):
        count = 1
        if X[i] =="1":
            print(0)
        else:
            cur = P2+pow(2,N-i-1,P+1)
            cur %= P+1
            while cur > 0:
                mod = bin(cur).count("1")
                cur %= mod
                count += 1
            print(count)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
input = sys.stdin.readline

n = int(input())
x = [int(item) for item in list(input().rstrip())]
x.reverse()

ones = x.count(1)
aug = ones + 1
dim = ones - 1

modaug = 0
moddim = 0
for i, item in enumerate(x):
    if item == 1:
        modaug += pow(2, i, aug)
        modaug %= aug
        if dim != 0:
            moddim += pow(2, i, dim)
            moddim %= dim

cnt = [-1] * (2*10**5 + 10)
cnt[0] = 0; cnt[1] = 1
for i in range(1, 2*10**5 + 10):
    val = i
    num = bin(val).count("1")
    cnt[i] = cnt[val % num] + 1

ans = []
for i, item in enumerate(x):
    if item == 0:
        tmp = modaug + pow(2, i, aug)
        tmp %= aug
    else:
        if dim == 0:
            ans.append(0)
            continue
        else:
            tmp = moddim - pow(2, i, dim)
            tmp %= dim
    ans.append(cnt[tmp] + 1)

ans.reverse()
for item in ans:
    print(item)

Submission status: Accepted

Solution code:
N = int(input())
X = input()
X = X[::-1]

def count(n):
    if n==0:
        return 0
    m = 0
    for i in range(18):
        if n&2**i:
            m += 1
    n %= m
    return 1+count(n)



p1 = [1]*(N+1)
p2 = [1]*(N+1)
m = 0
for i in range(N):
    if X[i]=='1':
        m += 1

for n in range(N):
    p1[n+1] = 2*p1[n]%(m+1)
    if m!=1:
        p2[n+1] = 2*p2[n]%(m-1)

num = [0]*N
base1 = 0
base2 = 0
for i in range(N):
    if X[i]=='1':
        base1 += p1[i]
        base2 += p2[i]

ans = [0]*N
for i in range(N):
    if X[i]=='0':
        num[i] = (base1+p1[i])%(m+1)
        ans[i] += 1
    else:
        if m!=1:
            num[i] = (base2-p2[i])%(m-1)
            ans[i] += 1
        else:
            num[i] = 0



for i in range(N-1,-1,-1):
    ans[i] += count(num[i])
    print(ans[i])

Submission status: Accepted

Solution code:
N = int(input())
X = input()
Xi = int(X, 2)

c0 = X.count('1')
Xp = Xi % (c0 + 1)

if c0 != 1:
    Xm = Xi % (c0 - 1)

for i, x in enumerate(X):
    if x == '1':
        if c0 == 1:
            print(0)
            continue
        y = (Xm - pow(2, N - 1 - i, c0 - 1)) % (c0 - 1)
    else:
        y = (Xp + pow(2, N - 1 - i, c0 + 1)) % (c0 + 1)

    ans = 1
    while y:
        y %= bin(y).count('1')
        ans += 1
    print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(200000)
n=int(input())
x=input()

tab=[0]+[i%bin(i).count('1') for i in range(1,200001)]

xcnt=x.count("1")
staxp=0
staxm=0
pl=xcnt+1
mi=xcnt-1
if mi==0:
    mi=1
for i in range(n):
    if x[n-i-1]=="1":
        staxp=(staxp+pow(2,i,pl))%pl
        staxm=(staxm+pow(2,i,mi))%mi
    
def calc(x,now):
    if x==0:
        return now
    else:
        return calc(tab[x],now+1)

for i in range(n):
    if x[i]=="1":
        if xcnt==1:
            print(0)
        else:
            sta=(staxm-pow(2,n-i-1,mi))%mi
            print(1+calc(sta,0))
    else:
        sta=(staxp+pow(2,n-i-1,pl))%pl
        print(1+calc(sta,0))

Submission status: Accepted

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

# n = 3
# x = "100"

l = 2*10**5 + 5
A = [0] * l
for i in range(1,l):
    ab = format(i, "b")
    abo = ab.count("1")
    A[i] = i % abo

B = [-1] * l
B[0] = 0
# print(A[:10])

def dd(y):
    # print(y)
    if B[y] == -1:
        return dd(A[y])+1
    else:
        return B[y]

for i in range(1, l):
    # print(dd(i))
    B[i] = dd(i)

# print(B[:100])

m = x.count("1")
m0 = m-1
m00 = m0
if m0 == 0:
    m0 = 1

m1 = m+1
M0 = [1]
M1 = [1]
for i in range(l):
    M0.append((M0[-1]*2) % m0)
    M1.append((M1[-1]*2) % m1)

n0 = 0
n1 = 0
for i in range(n):
    if x[n-1-i] == "1":
        n0 = (n0 + M0[i]) % m0
        n1 = (n1 + M1[i]) % m1

for i in range(n):
    nn = 0
    if x[i] == "1":
        nn = (n0 - M0[n-i-1]) % m0
    else:
        nn = (n1 + M1[n-i-1]) % m1
    print(B[nn]+1 if (m00!=0 or x[i]!="1") else 0)

Submission status: Accepted

Solution code:
import sys
N = int(input())

X = input()

o = 0
cnt = 0
for i in X:
    o *= 2
    if i == "1":
        o += 1
        cnt += 1

if cnt == 0:
    for i in range(N):
        print (1)
    sys.exit()
elif cnt == 1:
    orev = [o % (cnt+1) , None]
else:
    orev = [o % (cnt+1) , o % (cnt-1)]

for i in range(N):

    nb = int(X[i])

    if nb == 0:
        mod = cnt+1
        now = (orev[0] + pow(2,N-1-i,mod)) % mod

        ans = 1
        while now != 0:
            s = format( now , 'b' )
            one = 0
            for j in s:
                if j == "1":
                    one += 1
            now %= one
            ans += 1

        print (ans)

    else:
        if cnt == 1:
            print (0)
            continue
        
        mod = cnt-1
        now = (orev[1] - pow(2,N-1-i,mod)) % mod

        ans = 1
        while now != 0:
            s = format( now , 'b' )
            one = 0
            for j in s:
                if j == "1":
                    one += 1
            now %= one
            ans += 1

        print (ans)

Submission status: Accepted

Solution code:
from functools import lru_cache
N = int(input())
S = input()
X = int(S, 2)

P = S.count('1')
if P == 0:
    for i in range(N):
        print(1)
    exit()

Rp = X % (P+1)
if P != 1:
    Rn = X % (P-1)

@lru_cache(None)
def popcnt(x):
    return bin(x).count('1')

for i in range(N):
    if S[i] == '1':
        if P == 1:
            print(0)
            continue
        p = P-1
        x = (Rn - pow(2, N-1-i, p)) % p
    else:
        p = P+1
        x = (Rp + pow(2, N-1-i, p)) % p

    cnt = 1
    while x:
        x %= popcnt(x)
        cnt += 1
    print(cnt)

Submission status: Accepted

Solution code:
def calc(x):
    if x == 0:
        return 0
    cnt = 0
    for i in range(25):
        if x >> i & 1:
            cnt += 1
    return 1 + calc(x % cnt)

N = int(input())
X = list(map(int, input().rstrip()))
count = sum(X)
mod1 = [0] * N
mod2 = [0] * N
sum1 = sum2 = 0
for i, d in enumerate(X):
    if count > 1:
        mod1[i] = pow(2, N - i - 1, count-1)
    mod2[i] = pow(2, N - i - 1, count+1)
    if d:
        if count > 1:
            sum1 = (sum1 + mod1[i]) % (count - 1)
        sum2 = (sum2 + mod2[i]) % (count + 1)
for i, d in enumerate(X):
    ans = 0
    if d:
        if count > 1:
            ans = 1 + calc((sum1 - mod1[i]) % (count - 1))
    else:
        ans = 1 + calc((sum2 + mod2[i]) % (count + 1))
    print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
N = int(input())
S = list(map(int, list(input())[: -1]))
pp = sum(S)
Xp = 0
Xm = 0
S.reverse()
for i in range(N):
  Xp += pow(2, i, pp + 1) * S[i]
  Xp %= pp + 1
  Xm += pow(2, i, max(1, pp - 1)) * S[i]
  Xm %= max(1, pp - 1)
#print(Xp, Xm)
rres = [0] * N
for i in range(N):
  res = 1
  if S[i]:
    if pp == 1: res = 0
    else:
      X = (Xm - pow(2, i, max(1, pp - 1))) % max(1, pp - 1)
      while X:
        c = bin(X).count("1")
        X %= c
        res += 1
  else:
    X = (Xp + pow(2, i, pp + 1)) % (pp + 1)
    while X:
      c = bin(X).count("1")
      X %= c
      res += 1
  rres[i] = res
rres.reverse()
for r in rres: print(r)

Submission status: Accepted

Solution code:
def popc(x):
    acc = 0
    while x > 0:
        acc += x&1
        x >>= 1
    return acc

def fn(x):
    if x == 0:
        return 0
    return fn(x % popc(x)) + 1

n = int(input())
s = input()
o = s.count("1")
x = int(s, 2)
mp = x % (o+1)
mn = 0
if o > 1:
    mn = x % (o-1)
for i in range(n-1, -1, -1):
    if s[n-i-1] == "1":
        if o == 1:
            print(0)
            continue
        print(fn((mn - pow(2, i, o-1)) % (o-1)) + 1)
    else:
        print(fn((mp + pow(2, i, o+1)) % (o+1)) + 1)

Submission status: Accepted

Solution code:
import sys

readline = sys.stdin.readline
readall = sys.stdin.read
ns = lambda: readline().rstrip()
ni = lambda: int(readline().rstrip())
nm = lambda: map(int, readline().split())
nl = lambda: list(map(int, readline().split()))
prn = lambda x: print(*x, sep='\n')

def popcount(x):
    x = x - ((x >> 1) & 0x55555555)
    x = (x & 0x33333333) + ((x >> 2) & 0x33333333)
    x = (x + (x >> 4)) & 0x0f0f0f0f
    x = x + (x >> 8)
    x = x + (x >> 16)
    return x & 0x0000007f

def solve():
    n = ni()
    X = list(map(int, list(ns())))
    p = sum(X)
    pl, ps = p+1, p-1

    g = [-1] * (n+5)
    g[0] = 0
    for i in range(1, n+5):
        g[i] = g[i % popcount(i)] + 1
    ql = qs = 0
    for x in X:
        ql = (ql * 2 + x) % pl
        if ps > 0:
            qs = (qs * 2 + x) % ps
    vl = vs = 1
    ans = [0]*n
    for i in range(n-1, -1, -1):
        if X[i]:
            if ps > 0:
                ans[i] = g[(qs-vs)%ps] + 1
        else:
            ans[i] = g[(ql+vl)%pl] + 1
        if ps > 0:
            vs = vs * 2 % ps
        vl = vl * 2 % pl
    prn(ans)
    return

solve()

Submission status: Accepted

Solution code:
import sys
input=lambda: sys.stdin.readline().rstrip()
n=int(input())
X=input()
def popcount(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

F=[0]*(n+1)
F[1]=1
for i in range(2,n+1):
  F[i]=1+F[i%popcount(i)]

ct=X.count("1")
if ct==0:
  for _ in range(n):
    print(1)
elif ct==1:
  for i in range(n):
    if X[i]=="1":
      cur=i
      break
  for i in range(n):
    if i==cur:
      print(0)
    else:
      if i==n-1 or cur==n-1:
        print(2)
      else:
        print(1)

else:
  a,b=0,0
  for i in range(n):
    if X[n-1-i]=="1":
      a=(a+pow(2,i,ct-1))%(ct-1)
      b=(b+pow(2,i,ct+1))%(ct+1)
  for i in range(n):
    if X[i]=="0":
      print(F[(b+pow(2,n-1-i,ct+1))%(ct+1)]+1)
    else:
      print(F[(a-pow(2,n-1-i,ct-1))%(ct-1)]+1)

Submission status: Accepted

Solution code:
n = int(input())
x = input()
popcount_x = x.count("1")
popcount_x1 = popcount_x + 1
popcount_x2 = popcount_x - 1

if popcount_x2 == 0: popcount_x2 = -1

div1 = [0]*n
div2 = [0]*n
cur1 = 1
cur2 = 1
for i in range(n):
    cur1 %= popcount_x1
    cur2 %= popcount_x2
    div1[i] = cur1
    div2[i] = cur2
    cur1 *= 2
    cur2 *= 2


fn = [0]*n
for i in range(1,n):
    popcount = bin(i)[2:].count("1")
    fn[i] = fn[(i)%popcount] + 1

    
x_div1 = sum(int(x[i]) * div1[-i-1] for i in range(n)) % popcount_x1
x_div2 = sum(int(x[i]) * div2[-i-1] for i in range(n)) % popcount_x2

for i in range(n):
    if x[i] == "0": 
        xi_div = (x_div1 + div1[-i-1]) % popcount_x1
        print(fn[xi_div] + 1)
    else:
        if popcount_x2 == -1:
            print(0)
        else:
            xi_div = (x_div2 - div2[-i-1]) % popcount_x2
            print(fn[xi_div] + 1)

Submission status: Accepted

Solution code:
n = int(input())
x = input()
d = [0] * n
t = x.count('1')
a = 0
b = 0


if t == 1:
    for i in range(n):
        d[i] = (a + pow(2, n - i - 1, t + 1)) % (t + 1)
    for i in range(n):
        a *= 2
        if x[i] == '1':
            a += 1
        a %= t + 1
    for i in range(n):
        if x[i] == '1':
            print(0)
        else:
            p = d[i]
            ans = 1
            while p > 0:
                p %= bin(p).count('1')
                ans += 1
            print(ans)
else:
    for i in range(n):
        a *= 2
        b *= 2
        if x[i] == '1':
            a += 1
            b += 1
        a %= t + 1
        b %= t - 1
    for i in range(n):
        if x[i] == '1':
            d[i] = (b - pow(2, n - i - 1, t - 1)) % (t - 1)
        else:
            d[i] = (a + pow(2, n - i - 1, t + 1)) % (t + 1)
    for i in range(n):
        a *= 2
        b *= 2
        if x[i] == '1':
            a += 1
            b += 1
        a %= t + 1
        b %= t - 1
    for p in d:
        ans = 1
        while p > 0:
            p %= bin(p).count('1')
            ans += 1
        print(ans)