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:
# -*- coding: utf-8 -*-
import sys 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N = int(readline())
S = readline().decode().rstrip()
one_cnt = S.count('1')
S_rev = S[::-1]
#one_modは元のビットが立ってるとき zero_modは逆
one_mod = 0
zero_mod = 0
#Nが大きすぎるため下の桁から順に計算
for i in range(N):
    if S_rev[i] == '1' and one_cnt - 1 != 0:
        one_mod += pow(2,i,one_cnt - 1)
        one_mod %= (one_cnt - 1)
        zero_mod += pow(2,i,one_cnt + 1)
        zero_mod %= (one_cnt + 1)

cnt = [0]*(one_cnt+1)
pop_cnt = [0]* (one_cnt+1)
for i in range(1,one_cnt+1):
    pop_cnt[i] = pop_cnt[i//2] + i%2
    j = i % pop_cnt[i]
    cnt[i] = 1 + cnt[j] 

one_pow2 = [1]*(N+1)
zero_pow2 = [1]*(N+1)
for i in range(1,N):
    if one_cnt-1 != 0:
        one_pow2[i+1] = one_pow2[i]*2 % (one_cnt - 1)
    zero_pow2[i+1] = zero_pow2[i]*2 % (one_cnt + 1)

for i in range(N):
    if S[i] == '1':
        if one_cnt-1 == 0:
            print(0)
        else:
            nxt = one_mod
            nxt -= one_pow2[N-i]
            nxt %= (one_cnt - 1)
            print(1+cnt[nxt])
    else:
        nxt = zero_mod
        nxt += zero_pow2[N-i]
        nxt %= (one_cnt + 1)
        print(1+cnt[nxt])

Submission status: Accepted

Solution code:
import sys

input_methods=['clipboard','file','key']
using_method=1
input_method=input_methods[using_method]

tin=lambda : map(int, input().split())
lin=lambda : list(tin())
mod=1000000007

#+++++

dd={}
def get_f(v):
	global dd
	if v == 0:
		return 0
		
	if v in dd:
		return dd[v]
	
	pn = bin(v).count('1')
	ret = 1+get_f(v % pn)
	dd[v] = ret
	return ret
	
def bb(n, s):
	saigo = int(s[-1])
	for i, c in enumerate(s[:-1]):
		if c == '0':
			print(get_f(saigo)+1)
		else:
			print(0)
			
	if saigo == 0:
		print(get_f(1)+1)
	else:
		print(0)
		

def main():
	n = int(input())
	#b , c = tin()
	s = input()
	sa=s[::-1]
	n_one=s.count('1')
	if n_one == 1:
		bb(n,s)
		return 
	#pa(n_one)
	#pa(s)
	amari_p = 0
	amari_n = 0
	for i, c in enumerate(sa):
		if c == '1':
			amari_p += pow(2,i,n_one+1)
			amari_n += pow(2,i,n_one-1)
			amari_p %= n_one+1
			amari_n %= n_one-1
		
	#pa(amari_p)
	#pa(amari_n)
	for i, c in enumerate(s):
		keta = n - i - 1
		if c == '1':
			ta = amari_n
			ta -= pow(2,keta,n_one-1)
			ta %= n_one-1
		else:
			ta = amari_p
			ta += pow(2, keta, n_one+1)
			#pa(('q',ta))
			ta %= n_one+1
		#pa((keta,pow(2,keta),ta))
		print(get_f(ta)+1)
		
		
	
		
	
	
	
#+++++
isTest=False

def pa(v):
	if isTest:
		print(v)
		
def input_clipboard():
	import clipboard
	input_text=clipboard.get()
	input_l=input_text.splitlines()
	for l in input_l:
		yield l

if __name__ == "__main__":
	if sys.platform =='ios':
		if input_method==input_methods[0]:
			ic=input_clipboard()
			input = lambda : ic.__next__()
		elif input_method==input_methods[1]:
			sys.stdin=open('inputFile.txt')
		else:
			pass
		isTest=True
	else:
		pass
		#input = sys.stdin.readline
			
	ret = main()
	if ret is not None:
		print(ret)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline


def readstr():
    return input().strip()


def readint():
    return int(input())


def readnums():
    return map(int, input().split())


def readstrs():
    return input().split()


def main():
    N = readint()
    X = readstr()
    s = sum(tuple(map(int, X)))
    s1 = s + 1
    s2 = s - 1 if s != 1 else 1
    m1 = int(X, 2) % s1
    m2 = int(X, 2) % s2
    t1 = [1]
    t2 = [1]
    for i in range(N):
        t1.append(t1[i] * 2 % s1)
        t2.append(t2[i] * 2 % s2)
    for i in range(N):
        ans = 0
        if X[i] == '0':
            x = (m1 + t1[(N - i - 1)]) % s1
        else:
            if s == 1:
                print(0)
                continue
            else:
                x = (m2 - t2[(N - i - 1)]) % s2
        d = sum(tuple(map(int, bin(x)[2:])))
        ans += 1
        while x:
            x %= d
            d = sum(tuple(map(int, bin(x)[2:])))
            ans += 1
        print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline


def readstr():
    return input().strip()


def readint():
    return int(input())


def readnums():
    return map(int, input().split())


def readstrs():
    return input().split()


def popcount(n):
    ret = 0
    while n:
        ret += n & 1
        n >>= 1
    return ret


def main():
    N = readint()
    X = readstr()
    s = sum(tuple(map(int, X)))
    s1 = s + 1
    s2 = s - 1 if s != 1 else 1
    m1 = int(X, 2) % s1
    m2 = int(X, 2) % s2
    t1 = [1]
    t2 = [1]
    for i in range(N):
        t1.append(t1[i] * 2 % s1)
        t2.append(t2[i] * 2 % s2)
    for i in range(N):
        ans = 0
        if X[i] == '0':
            x = (m1 + t1[(N - i - 1)]) % s1
        else:
            if s == 1:
                print(0)
                continue
            else:
                x = (m2 - t2[(N - i - 1)]) % s2
        d = sum(tuple(map(int, bin(x)[2:])))
        ans += 1
        while x:
            x %= d
            d = sum(tuple(map(int, bin(x)[2:])))
            ans += 1
        print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline


def readstr():
    return input().strip()


def readint():
    return int(input())


def readnums():
    return map(int, input().split())


def readstrs():
    return input().split()


def popcount(n):
    ret = 0
    while n:
        ret += n & 1
        n >>= 1
    return ret


def main():
    N = readint()
    X = readstr()
    s = sum(tuple(map(int, X)))
    s1 = s + 1
    s2 = s - 1 if s != 1 else 1
    m1 = int(X, 2) % s1
    m2 = int(X, 2) % s2
    t1 = [1]
    t2 = [1]
    for i in range(N):
        t1.append(t1[i] * 2 % s1)
        t2.append(t2[i] * 2 % s2)
    for i in range(N):
        ans = 0
        if X[i] == '0':
            x = (m1 + t1[(N - i - 1)]) % s1
        else:
            if s == 1:
                print(0)
                continue
            else:
                x = (m2 - t2[(N - i - 1)]) % s2
        d = popcount(x)
        ans += 1
        while x:
            x %= d
            d = popcount(x)
            ans += 1
        print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
N=int(input())
X=input()
def calc(n,count):
    if n==0:
        return count
    popcount=bin(n).count("1")
    next_n=n%popcount
    #print(next_n)
    if next_n==0:
        return count+1
    else:
        return calc(next_n, count+1)

popcount=X.count("1")
if popcount==1:
    plus=0
    for i in range(N):
        x=X[i]
        if x=="1":
            plus+=pow(2,N-i-1,popcount+1)
    for i in range(N):
        x=X[i]
        if x=="1":
            print(0)
        else:
            ans=plus+pow(2,N-i-1,popcount+1)
            ans%=(popcount+1)
            print(calc(ans,1))
    exit()


plus=0
minus=0
for i in range(N):
    x=X[i]
    if x=="1":
        plus+=pow(2,N-i-1,popcount+1)
        minus+=pow(2,N-i-1,popcount-1)
        plus%=(popcount+1)
        minus%=(popcount-1)

for i in range(N):
    x=X[i]
    if x=="1":
        ans=minus-pow(2,N-i-1,popcount-1)
        ans%=(popcount-1)
        print(calc(ans,1))

    else:
        ans=plus+pow(2,N-i-1,popcount+1)
        ans%=(popcount+1)
        print(calc(ans,1))

Submission status: Accepted

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

origin_count = sX.count('1')
one_r_count = origin_count -1
zero_r_count = origin_count +1

one_mod = 0
zero_mod =0
for b in sX:
    if one_r_count != 0:
        one_mod = (one_mod * 2 + int(b) )% one_r_count
    zero_mod = (zero_mod * 2  + int(b) )% zero_r_count

f = [0] * 220000
pop = [0]* 220000

for i in range(1,220000):
    pop[i] = pop[i//2] + i%2
    f[i] = f[i % pop[i]] + 1

onepow = [1] * 220000
zeropow = [1]* 220000

for i in range(1,220000):
    if one_r_count != 0:
        onepow[i] = onepow[i-1] * 2 % one_r_count
    zeropow[i] = zeropow[i-1] * 2 % zero_r_count

for i in range(1,N+1):
    if sX[i-1] == '1':
        if one_r_count != 0:
            Xi_n = one_mod - onepow[N-i]
            Xi_n %= one_r_count
            print(f[Xi_n]+1)
        else:
            print(0)
    else:
        Xi_n = zero_mod + zeropow[N-i]
        Xi_n %= zero_r_count
        print(f[Xi_n]+1)

Submission status: Accepted

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

origin_count = sX.count('1')
one_r_count = origin_count -1
zero_r_count = origin_count +1

one_mod = 0
zero_mod =0
for b in sX:
    if one_r_count != 0:
        one_mod = (one_mod * 2 + int(b) )% one_r_count
    zero_mod = (zero_mod * 2  + int(b) )% zero_r_count

f = [0] * 220000
pop = [0]* 220000

for i in range(1,220000):
    pop[i] = pop[i//2] + i % 2
    f[i] = f[i % pop[i]] + 1

onepow = [1] * 220000
zeropow = [1]* 220000

for i in range(1,220000):
    if one_r_count != 0:
        onepow[i] = onepow[i-1] * 2 % one_r_count
    zeropow[i] = zeropow[i-1] * 2 % zero_r_count

for i in range(1,N+1):
    if sX[i-1] == '1':
        if one_r_count != 0:
            Xi_n = one_mod - onepow[N-i]
            Xi_n %= one_r_count
            print(f[Xi_n]+1)
        else:
            print(0)
    else:
        Xi_n = zero_mod + zeropow[N-i]
        Xi_n %= zero_r_count
        print(f[Xi_n]+1)

Submission status: Accepted

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

origin_count = sX.count('1')
one_r_count = origin_count -1
zero_r_count = origin_count +1

one_mod = 0
zero_mod =0
for b in sX:
    if one_r_count != 0:
        one_mod = (one_mod * 2 + int(b) )% one_r_count
    zero_mod = (zero_mod * 2  + int(b) )% zero_r_count

f = [0] * 220000
pop = [0]* 220000

for i in range(1,220000):
    pop[i] = pop[i//2] + i % 2
    f[i] = f[i % pop[i]] + 1

onepow = [1] * 220000
zeropow = [1]* 220000

for i in range(1,220000):
    if one_r_count != 0:
        onepow[i] = onepow[i-1] * 2 % one_r_count
    zeropow[i] = zeropow[i-1] * 2 % zero_r_count

for i in range(1,N+1):
    if sX[i-1] == '1':
        if one_r_count != 0:
            Xi_n = one_mod - onepow[N-i]
            Xi_n %= one_r_count
            print(f[Xi_n]+1)
        else:
            print(0)
    else:
        Xi_n = zero_mod + zeropow[N-i]
        Xi_n %= zero_r_count
        print(f[Xi_n]+1)

Submission status: Accepted

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

origin_count = sX.count('1')
one_r_count = origin_count -1
zero_r_count = origin_count +1

one_mod = 0
zero_mod =0
for b in sX:
    if one_r_count != 0:
        one_mod = (one_mod * 2 + int(b) )% one_r_count
    zero_mod = (zero_mod * 2  + int(b) )% zero_r_count

f = [0] * 220000
pop = [0]* 220000

for i in range(1,220000):
    pop[i] = pop[i//2] + i % 2
    f[i] = f[i % pop[i]] + 1

onepow = [1] * 220000
zeropow = [1]* 220000

for i in range(1,220000):
    if one_r_count != 0:
        onepow[i] = onepow[i-1] * 2 % one_r_count
    zeropow[i] = zeropow[i-1] * 2 % zero_r_count

for i in range(1,N+1):
    if sX[i-1] == '1':
        if one_r_count != 0:
            Xi_n = one_mod - onepow[N-i]
            Xi_n %= one_r_count
            print(f[Xi_n]+1)
        else:
            print(0)
    if sX[i-1] == '0':
        Xi_n = zero_mod + zeropow[N-i]
        Xi_n %= zero_r_count
        print(f[Xi_n]+1)

Submission status: Accepted

Solution code:
N=int(input())
X=input()
popcount=X.count('1')
mod = [popcount+1, popcount-1]
bi = [[0] * N for _ in range(2)]
Xnum = [0] * 2
add_diff = [1, -1]
for j in range(2):
    if mod[j] != 0:
        for i in range(N):
            if i==0: bi[j][0]=1%mod[j]
            else: bi[j][i]=bi[j][i-1]*2%mod[j]
            Xnum[j] = (Xnum[j] + int(X[N-i-1])*bi[j][i])%mod[j]
for i in range(N):
    if popcount==1 and X[i]=='1':
        print(0)
        continue
    Xi = ( Xnum[int(X[i])] + add_diff[int(X[i])] * bi[int(X[i])][N-i-1] ) % mod[int(X[i])]
    ans = 1
    while Xi!=0:
        Xi = Xi % bin(Xi).count('1')
        ans += 1
    print(ans)

Submission status: Accepted

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

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

XC = X.count('1')
XI = int(X, 2)
XCP = XC + 1
XCM = XC - 1
XTP = XI % XCP
XTM = XI % XCM if XCM != 0 else 0

for i in range(N):
    if X[i] == "0":
        print(goes_to_zero((XTP + pow(2, N - 1 - i, XCP)) % XCP) + 1)
    else:
        if XCM == 0:
            print(0)
        else:
            print(goes_to_zero((XTM - pow(2,N - 1 - i, XCM)) % XCM) + 1)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
import math


def read():
    N = int(input().strip())
    X = input().strip()
    return N, X


def bitdiv(N:int, X:str, d:int):
    q = 0
    for i in range(N):
        q <<= 1
        q |= int(X[i])
        p, q = divmod(q, d)
    return q


def solve(N, X):
    BP = [0 for i in range(N)]
    BM = [0 for i in range(N)]

    c = X.count("1")
    

    # 2^k mod (c+1) を高速に求める
    qp = int(X, base=2) % (c+1)
    BP[N-1] = 1 % (c+1)
    for i in range(N-2, -1, -1):
        BP[i] = (BP[i+1] * 2) % (c+1)
    
    # 2^k mod (c-1) を高速に求める
    if c > 1:
        qm = int(X, base=2) % (c-1)
        BM[N-1] = 1 % (c-1)
        for i in range(N-2, -1, -1):
            BM[i] = (BM[i+1] * 2) % (c-1)

    for i in range(N):
        q = 0
        ans = 0
        if X[i] == "0":
            # X_i \equiv (X + 2^i)
            q = (qp + BP[i]) % (c+1)
            ans += 1
        elif X[i] == "1" and c > 1:
            # X_i \equiv (X - 2^i)
            q = (qm - BM[i]) % (c-1)
            ans += 1
        else:
            q = 0
            ans = 0
        while q > 0:
            q %= (bin(q).count("1"))
            ans += 1
        print(ans)


if __name__ == '__main__':
    inputs = read()
    outputs = solve(*inputs)
    if outputs is not None:
        print("%s" % str(outputs))

Submission status: Accepted

Solution code:
N=int(input())
X=input()
popcount=X.count('1')
bi1=[]
bi0=[]
Xnum1 = 0
Xnum0 = 0
if popcount != 1:
    for i in range(N):
        if i==0: bi1.append(1)
        else: bi1.append(bi1[i-1]*2%(popcount-1))
        Xnum1 = (Xnum1 + int(X[N-i-1])*bi1[i])%(popcount-1)
for i in range(N):
    if i==0: bi0.append(1)
    else: bi0.append(bi0[i-1]*2%(popcount+1))
    Xnum0 = (Xnum0 + int(X[N-i-1])*bi0[i])%(popcount+1)
for i in range(N):
    if popcount==1 and X[i]=='1':
        print(0)
        continue
    if X[i]=='1':
        Xi = (Xnum1 - bi1[N-i-1])%(popcount-1)
    else:
        Xi = (Xnum0 + bi0[N-i-1])%(popcount+1)
    ans = 1
    while Xi!=0:
        Xi = Xi % bin(Xi).count('1')
        ans += 1
    print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
import math


def read():
    N = int(input().strip())
    X = input().strip()
    return N, X


def bitdiv(N:int, X:str, d:int):
    q = 0
    for i in range(N):
        q <<= 1
        q |= int(X[i])
        p, q = divmod(q, d)
    return q


def solve(N, X):
    BP = [0 for i in range(N)]
    BM = [0 for i in range(N)]

    c = X.count("1")
    

    # 2^k mod (c+1) を高速に求める
    qp = bitdiv(N, X, c+1)
    BP[N-1] = 1 % (c+1)
    for i in range(N-2, -1, -1):
        BP[i] = (BP[i+1] * 2) % (c+1)
    
    # 2^k mod (c-1) を高速に求める
    if c > 1:
        qm = bitdiv(N, X, c-1)
        BM[N-1] = 1 % (c-1)
        for i in range(N-2, -1, -1):
            BM[i] = (BM[i+1] * 2) % (c-1)

    for i in range(N):
        q = 0
        ans = 0
        if X[i] == "0":
            # X_i \equiv (X + 2^i)
            q = (qp + BP[i]) % (c+1)
            ans += 1
        elif X[i] == "1" and c > 1:
            # X_i \equiv (X - 2^i)
            q = (qm - BM[i]) % (c-1)
            ans += 1
        else:
            q = 0
            ans = 0
        while q > 0:
            q %= (bin(q).count("1"))
            ans += 1
        print(ans)


if __name__ == '__main__':
    inputs = read()
    outputs = solve(*inputs)
    if outputs is not None:
        print("%s" % str(outputs))

Submission status: Accepted

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

a = X.count("1")
ap, am = a+1, a-1
Flag = True

if am == 0:
  Flag = False
  am += 1

Ap = [1]
Am = [1]

for i in range(N-1):
  Ap.append(Ap[-1]*2%ap)
  Am.append(Am[-1]*2%am)

Aps = 0
Ams = 0

for i in range(N):
  if X[-1-i] == "1":
    Aps += Ap[i]
    Aps %= ap
    Ams += Am[i]
    Ams %= am
    
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

for i in range(N):
  cnt = 0
  if X[i] == "1":
    if Flag:
      p = Ams - Am[-1-i]
      p %= am
      cnt += 1
    else:
      p = 0
  else:
    p = Aps + Ap[-1-i]
    p %= ap
    cnt += 1
  while p > 0:
    p %= popcount(p)
    cnt += 1
  print(cnt)

Submission status: Accepted

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

init_pop_cnt = x.count('1')
init_pop_cnt_less = init_pop_cnt - 1
init_pop_cnt_more = init_pop_cnt + 1

valid_l = init_pop_cnt_less != 0

# x's state after f
init_res_less = 0
init_res_more = 0
seed_more = 1
seed_less = 1
for i in range(1, n+1):
  xp = x[-1 * i]
  if xp == '1':
    if valid_l:
      init_res_less += seed_less % init_pop_cnt_less
    init_res_more += seed_more % init_pop_cnt_more
  if valid_l:
    seed_less = (seed_less * 2) % init_pop_cnt_less
  seed_more = (seed_more * 2) % init_pop_cnt_more


dif_less = [0] * (2 * 10**5 + 100)
dif_more = [0] * (2 * 10**5 + 100)
if valid_l:
  dif_less[0] = 1 % init_pop_cnt_less
dif_more[0] = 1 % init_pop_cnt_more
for i in range(1, n+1):
  if valid_l:
    dif_less[i] = (dif_less[i-1] * 2) % init_pop_cnt_less
  dif_more[i] = (dif_more[i-1] * 2) % init_pop_cnt_more


def get_pc(dec):
  out = 0
  while dec > 0:
    if dec % 2 == 1:
      out+=1
    dec = dec // 2
  return out

def f(dec):
  pc = get_pc(dec)
  return dec % pc

cnt = [0] * (2 * 10**5 + 200)

for i in range(1, 2 * 10**5 + 100):
  c = 0
  cur = i
  while cur > 0:
    c += 1
    cur = f(cur)
  cnt[i] = c

for i in range(n):
  xi = x[i]

  if xi == '1':
    if valid_l:
      lx = init_res_less
      lx -= dif_less[n-i-1]
      lx %= init_pop_cnt_less
      print((cnt[lx] % init_pop_cnt_less) + 1)
    else:
      print(0)
  else:
    lx = init_res_more
    lx += dif_more[n-i-1]
    lx %= init_pop_cnt_more
    print((cnt[lx] % init_pop_cnt_more) + 1)

Submission status: Accepted

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

import sys
input=sys.stdin.readline


LEN=2*10**5+10

moves=[0]*LEN
for i in range(1,LEN):
  tmp=i
  cnt=0
  while tmp!=0:
    popcount=0
    for j in range(20):
      if tmp&(1<<j):
        popcount+=1
    tmp%=popcount
    cnt+=1
  moves[i]=cnt

n=int(input())
x=input()
k=x.count('1')
if k==0:
    for i in range(n):
        print(1)
elif k==1:
    pos=x.index('1')
    for i in range(n):
        if i==pos:
            print(0)
        else:
            if pos==n-1:
                print(2)
            else:
                if i==n-1:
                    print(2)
                else:
                    print(1)
else:
    sum1=0
    sum2=0
    tmp1=1
    tmp2=1
    for i in range(n-1,-1,-1):
        if x[i]=='1':
            sum1+=tmp1
            sum1%=k+1
            sum2+=tmp2
            sum2%=k-1
        tmp1*=2
        tmp1%=k+1
        tmp2*=2
        tmp2%=k-1
    for i in range(n):
        if x[i]=='0':
            tmp=sum1+pow(2,n-i-1,k+1)
            tmp%=k+1
            print(moves[tmp]+1)
        else:
            tmp=sum2-pow(2,n-i-1,k-1)
            tmp%=k-1
            print(moves[tmp]+1)

Submission status: Accepted

Solution code:
#!python3

import sys
iim = lambda: map(int, sys.stdin.readline().rstrip().split())
from functools import lru_cache


@lru_cache(maxsize=2*10**5)
def f2(x):
    if x == 0: return 0
    y = bin(x).count("1")
    return 1 + f2(x % y)

def resolve():
    N = int(input())
    W = 16
    S = input()
    cnt0 = S.count("1")

    if cnt0 == 0:
        print(*[1]*N, sep="\n")
        return

    X = int(S, 2)

    dc = {}
    for k, v in (("0", 1), ("1", -1)):
        x = cnt0 + v
        y = X % x if x else 0
        dc[k] = (x, v, y)

    ans = []
    for i, si in enumerate(S):
        cnt, v, n = dc[si]

        if cnt == 0:
            ans.append(0)
            continue

        ni = N - i - 1
        n = (n + v * pow(2, ni, cnt)) % cnt

        ans.append(1+f2(n))

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


if __name__ == "__main__":
    resolve()

Submission status: Accepted

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

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

def calc_small(n, iter):
    iter += 1
    mod = n % bin(n).count("1")

    if mod == 0:
        return iter
    else:
        return calc_small(mod, iter)

for i in range(N):
    if B_1 == 1 and int(B[i]) == 1:
        print(0)
        continue
    mod = (mod_m1 - pow(2,N-i-1,B_1-1)) % (B_1-1) if int(B[i]) == 1 else (mod_p1 + pow(2,N-i-1,B_1+1)) % (B_1+1)
    iter = 1
    if mod == 0:
        print(iter)
    else:
        print(calc_small(mod, iter))

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.buffer.readline
read = sys.stdin.buffer.read

import numpy as np


#N = 2 * 10 ** 5
#X = np.random.randint(0, 2, N)
#Y = int('0b' + ''.join(X.astype(str).tolist()), 0)

N = int(input())
X = input()
Y = int('0b' + X, 0)
X = np.array(list(X), int)

p = int(X.sum())
m1 = Y % (p + 1)
m2 = Y % max(1, p - 1)


count = np.zeros((N + 1, ))
for n in range(1, N):
    i = np.array(list(bin(n))[2:], int).sum()
    count[n] = 1 + count[n % i]

ans = [0] * N
for n in range(1, N + 1):
    flag = 0
    if X[n - 1]:
        z = m2 - pow(2, N - n, max(1, p - 1))
        z %= max(1, p - 1)
        if p - 1 == 0:
            flag = 1
    else:
        z = pow(2, N - n, p + 1) + m1
        z %= p + 1
        if p == 0:
            z = 0

    ans[n - 1] = int(count[z] + 1)
    if z == 0 and flag:
        ans [n - 1] = 0

print('\n'.join(map(str, ans)))

Submission status: Accepted

Solution code:
from collections import deque

n = int(input())
x = input()

memo = {0: 0}

def solve(X):
    x = X
    stack = deque([])
    while x:
        if x in memo:
            break
        stack.append(x)
        x = x % bin(x).count("1")
    cnt = memo[x] + 1
    while stack:
        x = stack.pop()
        memo[x] = cnt
        cnt += 1
    return cnt - 1



ans = []
px = x.count("1")

memo1 = [1 % (px - 1)] if px > 1 else []
memo2 = [1 % (px + 1)]
x1 = 0
x2 = 0

for i in range(n):
    if px > 1:
        memo1.append(memo1[-1] * 2 % (px-1))
    memo2.append(memo2[-1] * 2 % (px+1))

for i in range(n):
    if x[-i-1] == '1':
        if px > 1:
            x1 += memo1[i]
            x1 %= (px-1)
        x2 += memo2[i]
        x1 %= (px+1)

for i in range(n):
    if x[-i-1] == "1":
        if px > 1:
            ans.append(solve((x1-memo1[i])%(px-1)) + 1)
        else:
            ans.append(0)
    else:
        ans.append(solve((x2+memo2[i])%(px+1)) + 1)


for ansi in reversed(ans):
    print(ansi)

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/aising2020/tasks/aising2020_d

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

N = int(input())
X = input()
XC = X.count('1')
XI = int(X, 2)
XCP = XC + 1
XCM = XC - 1
XTP = XI % XCP
XTM = XI % XCM if XCM != 0 else 0
for i in range(N):
    if X[i] == "0":
        print(goes_to_zero((XTP + pow(2, N - 1 - i, XCP)) % XCP) + 1)
    else:
        if XCM == 0:
            print(0)
        else:
            print(goes_to_zero((XTM - pow(2,N - 1 - i, XCM)) % XCM) + 1)

Submission status: Accepted

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

if cnt1 > 1:
  x10mod_m = x10 % (cnt1-1)
  x10mod_p = x10 % (cnt1+1)
else:
  x10mod_m = 0
  x10mod_p = 0

ans = []
for i in range(n):
  if x[i] == '1':
    if cnt1 == 1:
      print(0)
      continue
    cntx = cnt1-1
    mod = ( x10mod_m - pow(2,n-1-i,cntx) ) % cntx
  else:
    cntx = cnt1+1
    mod = ( x10mod_p + pow(2,n-1-i,cntx) ) % cntx
    
  cnt = 1
  mod = format(mod, 'b')
  
  while True:
    if mod == '0':
      break
    mod = format( int(mod,2) % mod.count('1'), 'b')
    cnt += 1
  print(cnt)

Submission status: Accepted

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

def popcnt1(n):
    return bin(n).count("1")

k = [0,1,1,2,1,2,1,2,1,2,1,2,1,2,2,3,1,2,1] #18まで

c = 0
for i in range(N):
    if X[i] == "1":
        c += 1

m1 = 0
p1 = 0

for i in range(N):
    if c != 1:
        if X[i] == "1":
            m1 += pow(2,N-1-i,c-1)
            m1 %= c-1
            p1 += pow(2,N-1-i,c+1)
            p1 %= c+1
    else:
        if X[i] == "1":
            p1 += pow(2,N-1-i,c+1)
            p1 %= c+1

for i in range(N):
    if c != 1: 
        if X[i] == "0":
            B2 = p1 + pow(2,N-1-i,c+1)
            B2 %= c+1
        else:
            B2 = m1 - pow(2,N-1-i,c-1)
            B2 %= c-1
    else:
        if X[i] == "0":
            B2 = p1 + pow(2,N-1-i,c+1)
            B2 %= c+1
        else:
            print(0)
            continue

    S = len(bin(B2))
    c2 = popcnt1(B2)

    if c2 == 0:
        print(1)
    else:
        print(2+k[B2%c2])

Submission status: Accepted

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

one = x.count("1")
X = int(x, 2)

if one==1:
    for i in range(n):
        if x[i]=="1":
            print(0)
        elif i==n-1:
            print(2)
        else:
            print(1)
    
    
elif one>1:
    
    Xp = X % (one+1)
    Xm = X % (one-1)

    def f(x):
        if x==0:
            return 0
        return 1+f(x%bin(x).count("1"))

    for i in range(n):
        
        if x[i]=="0":
            c = pow(2, n-i-1, one+1)
            print(f((Xp+c)%(one+1))+1)
        else:
            c = pow(2, n-i-1, one-1)
            print(f((Xm-c)%(one-1))+1)
else:
    for i in range(n):
        print(1)

Submission status: Accepted

Solution code:

n = int(input())
x = input()

def popcount(ni):
    n_b = str(bin(ni))
    return n_b.count("1")

def ans(n,x):
    x_i = int(x, 2)
    x_orig = popcount(x_i)
    x_i_t = x_i % (x_orig+1)
    if x_orig != 1:
        x_i_b = x_i % (x_orig-1)
    else:
        x_i_b = x_i
    solve = 0
    for i in range(n):
        x_count = x_orig
        if x[i] == "0":
            x_count += 1
            solve = x_i_t + pow(2,n-1-i,x_count)
        else:
            x_count -= 1
            if x_count != 0:
                solve = x_i_b - pow(2,n-1-i,x_count)
            else:
                print(0)
                continue
        count = 0

        if x_count != 0 :
            solve = solve % x_count
            count+=1

        while solve > 0:
            solve = solve % popcount(solve)
            count+=1

        print(count)

    
ans(n,x)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
N=int(sys.stdin.readline().strip())
X=sys.stdin.readline().strip()

cnt_of_one=0
for x in X:
    if x=="1": cnt_of_one+=1

cnt_of_one_plus_one=cnt_of_one+1    #2進数Xのどこかの桁のbitが0→1になった数のpopconut
cnt_of_one_minus_one=cnt_of_one-1   #2進数Xのどこかの桁のbitが1→0になった数のpopconut

amari_cnt_of_one_plus_one=0     #2進数Xのどこかの桁のbitが0→1になった数に対して、popconutで割ったあまり
amari_cnt_of_one_minus_one=0    #2進数Xのどこかの桁のbitが1→0になった数に対して、popconutで割ったあまり
for i,x in enumerate(X[::-1]):
    if x=="1":    #その桁の値が1の時だけ数を足す
        amari_cnt_of_one_plus_one+=pow(2,i,cnt_of_one_plus_one)
        amari_cnt_of_one_plus_one%=cnt_of_one_plus_one
        if cnt_of_one_minus_one==0: #2進数の全ての桁が0の場合は、0で除算はできないので場合分けする
            amari_cnt_of_one_minus_one=0
        else:
            amari_cnt_of_one_minus_one+=pow(2,i,cnt_of_one_minus_one)
            amari_cnt_of_one_minus_one%=cnt_of_one_minus_one

def popcount(n):
    ret=0
    while 0<n:
        ret+=n%2
        n/=2
    return ret

def f(n):
    ret=0   #余りが0になるまで割った回数
    while 0<n:
        n%=popcount(n)
        ret+=1
    return ret

for i,x in enumerate(X):
    keta=N-i-1
    if x=="0":
        syoki_amari=(amari_cnt_of_one_plus_one+pow(2,keta,cnt_of_one_plus_one))%cnt_of_one_plus_one
        if syoki_amari==0:
            print 1
        else:
            print 1+f(syoki_amari)
    elif x=="1":
        if cnt_of_one_minus_one==0: #2進数の全ての桁が0という意味だから
            print 0 #値が0になるまでの操作回数は0回
        else:
            syoki_amari=(amari_cnt_of_one_minus_one-pow(2,keta,cnt_of_one_minus_one))%cnt_of_one_minus_one
            if syoki_amari==0:
                print 1
            else:
                print 1+f(syoki_amari)

Submission status: Accepted

Solution code:
def dfs(n):
    if n == 0:return 0
    return dfs(n % format(n, "b").count("1")) + 1
n = int(input())
x = input()
c = x.count("1")
a = int(x, 2)
if c == 1:
    for i in range(n):
        if x[i] == "1":
            print(0)
        elif i == n - 1:
            print(2)
        else:
            print(1)
else:
    j, k = a % (c + 1), a % (c - 1)
    for i in range(n):
        if x[i] == "1":print(dfs((k - pow(2, n - i - 1, c - 1)) % (c - 1)) + 1)
        else:print(dfs((j + pow(2, n - i - 1, c + 1)) % (c + 1)) + 1)

Submission status: Accepted

Solution code:
import math
from copy import copy
di = {}
di[0] = 0
for i in range(1, 2*(10**5)+1):
    di[i] = 0
for i in range(1, 2*(10**5)+1):
    count = 0
    for j in range(int(math.log2(i))+4):
        if (i>>j)&1:
            count += 1
    di[i] = di[i%count] + 1
n = int(input())
x = list(input())
x.reverse()
count = 0
for i in x:
    if i =='1':
        count += 1
mod_p = count + 1
mod_m = count - 1
di_p = {}
di_m = {}
for i in range(n):
    di_p[i] = pow(2, i, mod_p)
    if mod_m >= 1:
        di_m[i] = pow(2, i, mod_m)
s_p = 0
s_m = 0
for i in range(n):
    if x[i] == '1':
        s_p += di_p[i]
        if mod_m >= 1:
            s_m += di_m[i]
    else:
        continue
for i in range(n-1, -1, -1):
    sm = copy(s_m)
    sp = copy(s_p)
    if x[i] == '1' and (mod_m == 0 or mod_m == -1):
        print(0)
    elif x[i] == '1':
        sm -= di_m[i]
        sm %= mod_m 
        print(di[sm]+1)
    else:
        sp += di_p[i]
        sp %= mod_p
        print(di[sp]+1)