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:
import sys

sys.setrecursionlimit(10 ** 7)
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    n = int(input())
    X = input()

    cnt_init = X.count("1")
    x_init = int(X, 2)
    a = x_init % (cnt_init + 1)
    if cnt_init - 1 != 0:
        b = x_init % (cnt_init - 1)

    for i in range(n):
        if X[i] == "0":
            cnt = cnt_init + 1
            x = (a + pow(2, (n - i - 1), cnt)) % cnt
            res = 1
        else:
            cnt = cnt_init - 1
            if cnt != 0:
                x = (b - pow(2, (n - i - 1), cnt)) % cnt
                res = 1
            else:
                x = 0
                res = 0

        while x:
            cnt = bin(x).count("1")
            x %= cnt
            res += 1
        print(res)


if __name__ == '__main__':
    resolve()

Submission status: Accepted

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

def popcount(x):
  return bin(x).count("1")
p=X.count('1')

pl=a%(p+1)
if p!=1:
  mi=a%(p-1)

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

for i in range(N):
  if X[i]=='0':
    b=pl
    b+=pow(2,N-i-1,p+1)
    b%=p+1
  else:
    if p!=1:
      b=mi
      b-=pow(2,N-i-1,p-1)
      b%=p-1
    else:
      print(0)
      continue
  print(f(b))

Submission status: Accepted

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

def popcount(x):
  return bin(x).count("1")
p=X.count('1')

pl=a%(p+1)
if p!=1:
  mi=a%(p-1)

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

for i in range(N):
  if X[i]=='0':
    b=pl
    b+=pow(2,N-i-1,p+1)
    b%=p+1
  else:
    if p!=1:
      b=mi
      b-=pow(2,N-i-1,p-1)
      b%=p-1
    else:
      print(0)
      continue
  print(f(b))

Submission status: Accepted

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce


sys.setrecursionlimit(2147483647)
INF = 10 ** 13
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 10 ** 9 + 7

n = I()
x = input()
cnt = x.count("1")
if cnt == 1:
    for i in range(n):
        if x[i] == "1":
            print(0)
        elif i == n - 1:
            print(2)
        else:
            print(1)
    exit()

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

xx = int(x, 2)
Y = xx % (cnt + 1)
Z = xx % (cnt - 1)
for i in range(n):
    if x[i] == '1':
        print(1 + f((Z - pow(2, n - i - 1, cnt - 1)) % (cnt - 1)))
    else:
        print(1 + f((Y + pow(2, n - i - 1, cnt + 1)) % (cnt + 1)))

Submission status: Accepted

Solution code:
N=int(input())
X=input()
Y=int(X,2)
Z=Y
C=X.count('1')
if C==1:
  for i in range(N):
    if X[i]=='1':
      print(0)
    elif i==N-1:
      print(2)
    else:
      print(1)
  exit()
Y,Z=Y%(C+1),Z%(C-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]=='1':
    print(1+f((Z-pow(2,N-i-1,C-1))%(C-1)))
  else:
    print(1+f((Y+pow(2,N-i-1,C+1))%(C+1)))

Submission status: Accepted

Solution code:
n = int(input())
s = input()
x = [0] * n

def pcnt(x):
    return bin(x).count('1')

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

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

pc = sum(x)
ans = [0] * n
for b in range(2):
    npc = pc
    if b == 0:
        npc += 1
    else:
        npc -= 1

    if npc <= 0: continue

    r0 = 0
    for i in range(n):
        r0 = (r0 * 2) % npc
        r0 += x[i]

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

for i in ans:
    print(i)

Submission status: Accepted

Solution code:
n = int(input())
x = input()
original_pop_count = x.count('1')
one_pop_count = original_pop_count-1
zero_pop_count = original_pop_count+1

one_mod = 0
zero_mod= 0
for b in x:
    if one_pop_count!=0:
        one_mod=(one_mod*2+int(b))%one_pop_count
    zero_mod=(zero_mod*2+int(b))%zero_pop_count
#予めf[i]を計算する
f = [0]*220000
pop_count = [0]*220000
for i in range(1,220000):
    pop_count[i]= pop_count[i//2] + i%2
    f[i] = f[i%pop_count[i]]+1
one_pow2 = [1]*220000
zero_pow2 = [1]*220000
for i in range(1,220000):
    if one_pop_count!=0:
        one_pow2[i] = one_pow2[i-1]*2%one_pop_count
    zero_pow2[i] = zero_pow2[i-1]*2%zero_pop_count


for i in range(n-1,-1,-1):
    if x[n-1-i]=='1':
        if one_pop_count!=0:
            nxt = one_mod
            nxt-=one_pow2[i]
            nxt%=one_pop_count
            print(f[nxt]+1)
        else:
            print(0)
    if x[n-1-i]=='0':
        nxt = zero_mod
        nxt+=zero_pow2[i]
        nxt%=zero_pop_count
        print(f[nxt]+1)

Submission status: Accepted

Solution code:
N=int(input())
X=input()
A=[0,1,1,2,1,2,1,2,1,2,1,2,1,2,2,3,1]

ppx=0

for i in range(N):
  if X[i]=="1":
    ppx+=1
if ppx<=1:
  ppxm1=1
else:
  ppxm1=ppx-1
Xmod=[0,0]
XmodP=[0]*N
XmodM=[0]*N
XmodP[0]=1%(ppx+1)
XmodM[0]=1%(ppxm1)
Xmod=[XmodP[0]*(X[-1]=="1"),XmodM[0]*(X[-1]=="1")]
for i in range(N-1):
  XmodP[i+1]=(XmodP[i]*2)%(ppx+1)
  XmodM[i+1]=(XmodM[i]*2)%(ppxm1)
  if X[-2-i]=="1":
    Xmod[0]=(Xmod[0]+XmodP[i+1])%(ppx+1)
    Xmod[1]=(Xmod[1]+XmodM[i+1])%(ppxm1)
for i in range(N):
  if X[i]=="0":
    Xm=(Xmod[0]+XmodP[-1-i])%(ppx+1)
  else:
    Xm=(Xmod[1]-XmodM[-1-i])%(ppxm1)
  if ppx==1 and X[i]=="1":
    print(0)
  elif Xm==0:
    print(1)
  else:
    px=0
    temp=Xm
    while temp>0:
      if temp%2==1:
        px+=1
        temp=(temp-1)/2
      else:
        temp=temp/2
    p=Xm%px
    print(A[p]+2)

Submission status: Accepted

Solution code:
N = int(input())
X_bin = input()
#N = 10**5
#X_bin = '1' * N

X_int = int(X_bin, 2)  # bin => int


def calc_bin_cnt(next_int):
    if next_int == 0:
        return 0
    next_bin = bin(next_int)[2:]
    # popcount
    cnt = 0
    for i in next_bin:
        if i == '1':
            cnt += 1
    return cnt


def calc_ans(next_int, cnt=None):
    if next_cnt == 0:
        return 0
    if next_int == 0:
        return 1
    if cnt is None:
        cnt = calc_bin_cnt(next_int)
    next_int = next_int % cnt
    if next_int > 0:
        ans = calc_ans(next_int) + 1
    else:
        ans = 1
    return ans


X_cnt = calc_bin_cnt(X_int)
f_p = X_int % (X_cnt+1)
if X_cnt-1 == 0:
    f_m = 0
else:
    f_m = X_int % (X_cnt-1)
for i in range(N):
    if X_bin[i] == '1':
        next_cnt = X_cnt - 1
        if next_cnt == 0:
            next_int = 0
        else:
            next_int = f_m - pow(2, (N-i-1), next_cnt)  # マイナスでも正しく求まる？
    else:
        next_cnt = X_cnt + 1
        next_int = f_p + pow(2, (N-i-1), next_cnt)
    print(calc_ans(next_int, next_cnt))
    #calc_ans(next_cnt, next_cnt)

Submission status: Accepted

Solution code:
def popcnt(n):
    c = (n & 0x5555555555555555) + ((n>>1) & 0x5555555555555555)
    c = (c & 0x3333333333333333) + ((c>>2) & 0x3333333333333333)
    c = (c & 0x0f0f0f0f0f0f0f0f) + ((c>>4) & 0x0f0f0f0f0f0f0f0f)
    c = (c & 0x00ff00ff00ff00ff) + ((c>>8) & 0x00ff00ff00ff00ff)
    c = (c & 0x0000ffff0000ffff) + ((c>>16) & 0x0000ffff0000ffff)
    c = (c & 0x00000000ffffffff) + ((c>>32) & 0x00000000ffffffff)
    return c


N = int(input())
X = input()
pc = X.count('1')
if pc == 0:
    for i in range(N):
        print(1)
elif pc == 1:
    if X[-1] == '1':
        for i in range(N-1):
            print(2)
        print(0)
    else:
        for i in range(N-1):
            if X[i] == '1':
                print(0)
            else:
                print(1)
        print(2)
else:
    modX1 = 0
    modX2 = 0
    Xi = [None] * N
    x1 = 1
    x2 = 1
    for i in range(N):
        if X[-i-1] == '1':
            Xi[-i-1] = x1
            modX1 = (modX1+x1) % (pc-1)
            modX2 = (modX2+x2) % (pc+1)
        else:
            Xi[-i-1] = x2
        x1 = x1 * 2 % (pc-1)
        x2 = x2 * 2 % (pc+1)
    for i in range(N):
        ans = 1
        x = (modX1 - Xi[i]) % (pc-1) if X[i] == '1' else (modX2 + Xi[i]) % (pc+1)
        while x != 0:
            x = x % popcnt(x)
            ans += 1
        print(ans)

Submission status: Accepted

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

N = int(input())
X = input()
Xint = int(X, 2)
Xcount = X.count("1")

"""
0010
1010 10(mod2) -> 0
i = n-1の時だけ +1
0011 -> 3 -> 1->0
0110 -> 6(mod2) -> 0
"""

if Xcount == 1:
    for i in range(N):
        if X[i] == "1":
            print(0)
        elif i == N-1:
            print(2)
        else:
            print(1)
    exit()

Modplus, Modminus = Xint%(Xcount+1), Xint%(Xcount-1)

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

for i in range(N):
    if X[i] == "1":
        print(1+f((Modminus-pow(2, N-1-i, Xcount-1))%(Xcount-1)))
    else:
        print(1+f((Modplus+pow(2, N-1-i, Xcount+1))%(Xcount+1)))

Submission status: Accepted

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

    N = int(input())
    Xs = input()
    X = int(Xs, 2)
    d = popcnt(X)

    lut = [0] * N
    for i in range(1, N):
        Xi = i % popcnt(i)
        lut[i] = lut[Xi] + 1

    dp = d+1
    dm = d-1
    mp = X % dp
    mm = X % dm if dm else 0
    # print(lut)
    # print(format(X, 'b'))

    ans = []
    for i in range(N):
        mask = 1 << (N-i-1)
        Xi = X ^ mask
        _ans = 0
        if Xs[i] == '1':
            if dm:
                m = (mm - pow(2, N-i-1, dm)) % dm
                _ans = lut[m] + 1
            # m = (mm - mask) % dm
        else:
            # m = (mp + mask) % dp
            m = (mp + pow(2, N-i-1, dp)) % dp
            _ans = lut[m] + 1
        ans.append(_ans)
    print(*ans, sep='\n')

resolve()

Submission status: Accepted

Solution code:
n=int(input())
X=input()
x=X.count('1')
x_plus=int(X,2)%(x+1)
keta=n-1
if x==1:
    for i in range(n):
        tmp=0
        ans=1
        if X[i]=='0':
            tmp+=x_plus
            tmp+=pow(2,keta,(x+1))
            tmp%=(x+1)
            while tmp:
                tmp=tmp%(bin(tmp).count('1'))
                ans+=1
            print(ans)
        else:
            print(0)
        keta-=1
else:
    x_minus=int(X,2)%(x-1)
    for i in range(n):
        tmp=0
        ans=1
        if X[i]=='0':
            tmp+=x_plus
            tmp+=pow(2,keta,(x+1))
            tmp%=(x+1)
            while tmp:
                tmp=tmp%(bin(tmp).count('1'))
                ans+=1
            print(ans)
        else:
            tmp+=x_minus
            tmp-=pow(2,keta,(x-1))
            tmp%=(x-1)
            while tmp:
                tmp=tmp%(bin(tmp).count('1'))
                ans+=1
            print(ans)
        keta-=1

Submission status: Accepted

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

#10進数に変換
decX = int(strX,2)

#1の数をカウント
pop_c = strX.count('1')

# X % popcount+1
f_p = decX % (pop_c + 1)

# X % popcount-1(0になる時は0)
if pop_c == 1:
  f_m = 0
else:
  f_m = decX % (pop_c - 1)

for i in range(0,N):
  if strX[i] == '0':
    pop_a = (f_p + pow(2,(N-1-i),(pop_c + 1))) % (pop_c + 1) 
    Ans = 1
    
  elif pop_c == 1:
    pop_a = 0
    Ans = 0
    
  else:
    pop_a = f_m - (pow(2,(N-1-i),(pop_c - 1)))
    if pop_a < 0:
      pop_a = pop_a + pop_c - 1
    Ans = 1
  
  while pop_a > 0:
    wkpop = bin(pop_a).count('1')
    pop_a = pop_a % wkpop
    Ans += 1
  
  print(Ans)

Submission status: Accepted

Solution code:

import math
from collections import defaultdict,deque
ml=lambda:map(int,input().split())
ll=lambda:list(map(int,input().split()))
ii=lambda:int(input())
ip=lambda:list(input())
ips=lambda:input().split()

"""========main code==============="""

def fast_expo(x,y,m):
    res=1
    while(y):
        if(y&1):
            res*=x
            res%=m
        x*=x
        x%=m
        y>>=1
    return res    

dp=defaultdict(int)
dp[1]=1
dp[2]=1
for i in range(3,200001):
    k=i
    cnt=0
    while(k):
        if(k%2): cnt+=1
        k>>=1
    dp[i]=dp[i%cnt]+1
n=ii()
a=ip()
a=a[::-1]
c=a.count('1')

min_1=0
max_1=0

for i in range(n):
    if(a[i]=='1'):
        if(c-1!=0):
            min_1+=fast_expo(2,i,c-1)
            min_1%=(c-1)
        max_1+=fast_expo(2,i,c+1)
        
        max_1%=(c+1)
    
ans=[]    

for i in range(n):
    if(a[i]=='1'):
        if(c-1==0):
            ans.append(0)
        else:    
            ans.append(dp[(min_1-fast_expo(2,i,c-1)+(c-1))%(c-1)]+1)
    else:
        ans.append(dp[(max_1+fast_expo(2,i,c+1))%(c+1)]+1)
ans=ans[::-1]
for i in ans:
    print(i)

Submission status: Accepted

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

import math
from collections import defaultdict,deque
ml=lambda:map(int,input().split())
ll=lambda:list(map(int,input().split()))
ii=lambda:int(input())
ip=lambda:list(input())
ips=lambda:input().split()

"""========main code==============="""

def fast_expo(x,y,m):
    res=1
    while(y):
        if(y&1):
            res*=x
            res%=m
        x*=x
        x%=m
        y>>=1
    return res    

dp=defaultdict(int)
dp[1]=1
dp[2]=1
for i in range(3,200001):
    k=i
    cnt=0
    while(k):
        if(k%2): cnt+=1
        k>>=1
    dp[i]=dp[i%cnt]+1
n=ii()
a=ip()
a=a[::-1]
c=a.count('1')

min_1=0
max_1=0

for i in range(n):
    if(a[i]=='1'):
        if(c-1!=0):
            min_1+=fast_expo(2,i,c-1)
            min_1%=(c-1)
        max_1+=fast_expo(2,i,c+1)
        
        max_1%=(c+1)
    
ans=[]    

for i in range(n):
    if(a[i]=='1'):
        if(c-1==0):
            ans.append(0)
        else:    
            ans.append(dp[(min_1-fast_expo(2,i,c-1)+(c-1))%(c-1)]+1)
    else:
        ans.append(dp[(max_1+fast_expo(2,i,c+1))%(c+1)]+1)
ans=ans[::-1]
for i in ans:
    print(i)

Submission status: Accepted

Solution code:
import sys


def popcount(n):
    c = 0
    while n:
        if n & 1:
            c += 1
        n >>= 1

    return c


def f(n, c=0):
    while pc := popcount(n):
        n %= pc
        c += 1

    return c


def _resolve(n, x_bytes):
    one_i = b'1'[0]
    pc_x = x_bytes.count(b'1')

    i2_mod_pc_x_p1 = [0] * n
    i2_mod_pc_x_m1 = [0] * n
    x_mod_pc_x_p1 = 0
    x_mod_pc_x_m1 = 0

    i2 = 1
    x = 0
    mod = pc_x + 1
    for a in range(n):
        i2_mod_pc_x_p1[- 1 - a] = i2
        i2 *= 2
        i2 %= mod

        x *= 2
        x %= mod
        if (x_bytes[a] == one_i):
            x += 1
    x_mod_pc_x_p1 = x % mod

    if pc_x > 1:
        i2 = 1
        x = 0
        mod = pc_x - 1
        for a in range(n):
            i2_mod_pc_x_m1[- 1 - a] = i2
            i2 *= 2
            i2 %= mod

            x *= 2
            x %= mod
            if (x_bytes[a] == one_i):
                x += 1
        x_mod_pc_x_m1 = x % mod

    # print(pc_x)
    # print(x_mod_pc_x_p1)
    # print(x_mod_pc_x_m1)

    # print(i2_mod_pc_x_p1)
    # print(i2_mod_pc_x_m1)

    for a in range(n):
        if x_bytes[a] == one_i:
            mod = pc_x - 1
            if mod == 0:
                yield 0
                continue
            b = x_mod_pc_x_m1 - i2_mod_pc_x_m1[a]
        else:
            mod = pc_x + 1
            b = x_mod_pc_x_p1 + i2_mod_pc_x_p1[a]
        b %= mod

        yield f(b, 1)

def resolve(in_, out):
    n = int(in_.readline())
    x_bytes = in_.readline()
    for ret in _resolve(n, x_bytes):
        print(ret, file=out)


def main():
    resolve(sys.stdin.buffer, sys.stdout)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def popcount(x):
    return bin(x).count("1")
def solve(n):
    if n == 0:
        return 0
    return 1+solve(n % popcount(n))

N = int(input())
X = input()
num_x = int(X, 2)
p_cnt = X.count('1')
if p_cnt == 1:
    for i in range(N):
        if X[i] == '1':
            print(0)
        elif i == N-1:
            print(2)
        else:
            print(1)
    exit()
r0_p = num_x % (p_cnt+1)
r0_m = num_x % (p_cnt-1)
for i in range(N):
    if X[i] == '0':
        c_p_cnt = p_cnt+1
        r = (r0_p + pow(2, (N - 1 - i), c_p_cnt)) % c_p_cnt
    else:
        c_p_cnt = p_cnt-1
        if c_p_cnt == 0:
            print(0)
            continue
        r = (r0_m- pow(2, (N - 1 - i), c_p_cnt)) % c_p_cnt
    print(1 + solve(r % c_p_cnt))

Submission status: Accepted

Solution code:
#D
N=int(input())
X=str(input())
   
CNT=0
for i in range(N):
    if X[i]=="1":
        CNT+=1
NUM=int(X,2)

to0_cnt=[0 for i in range(N)]
for i in range(1,N):
    ans=0
    num=i
    while True:
        cnt=0
        for j in bin(num)[2:]:
            if j=="1":
                cnt+=1
        if cnt==0:
            break
        r=num%cnt
        ans+=1
        if r==0:
            break
        num=r
    to0_cnt[i]=ans
                
R=[NUM%(CNT+1),NUM%(CNT-1) if CNT!=1 else 0]
for i in range(N):
    if X[i]=="0":
        cnt=CNT+1
        r=(R[0]+pow(2,N-i-1,cnt))%cnt
    else:
        cnt=CNT-1
        if NUM-pow(2,N-i-1)==0:
            print(0)
            continue
        r=(R[1]-pow(2,N-i-1,cnt))%cnt
    
    ans=1+to0_cnt[r]
    print(ans)

Submission status: Accepted

Solution code:
N = int(input())
num = input()
X = int(num,2)
c = num.count('1')
def A(s):
    if s == 0:
        return 1
    return A(s%(bin(s).count('1'))) + 1
if c==1:
  for i in range(N):
    if num[i] == '1':
      print(0)
    elif i == N-1:
      print(2)
    else:
      print(1)
  exit()
amari1 = X%(c+1)
amari2 = X%(c-1)
for i in range(N):
    if num[i] == '1':
        print(A((amari2-pow(2,N-1-i,c-1))%(c-1)))
    else:
        print(A((amari1+pow(2,N-1-i,c+1))%(c+1)))

Submission status: Accepted

Solution code:
N=int(input())
X=input()
Y=int(X,2)
Z=Y
C=X.count('1')
if C==1:
  for i in range(N):
    if X[i]=='1':
      print(0)
    elif i==N-1:
      print(2)
    else:
      print(1)
  exit()
Y,Z=Y%(C+1),Z%(C-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]=='1':
    print(1+f((Z-pow(2,N-i-1,C-1))%(C-1)))
  else:
    print(1+f((Y+pow(2,N-i-1,C+1))%(C+1)))

Submission status: Accepted

Solution code:
def popcount_int(n):
    return bin(n).count('1')

def popcount_bin(s):
    return s.count('1')

def poptimes(n,cnt=1):
    if n==0:
        return cnt
    else:
        n%=popcount_int(n)
        cnt+=1
        return poptimes(n,cnt)

N=int(input())
S=input()

S_int=int(S,2)
pc=popcount_bin(S)
pc_plus=S_int%(pc+1)
if pc!=1:
    pc_minus=S_int%(pc-1)

for i in range(N):
    if S[i]=='1':
        if pc!=1:
            tmp=pc_minus-pow(2,N-i-1,pc-1)
            print(poptimes(tmp%(pc-1)))
        else:
            print(0)
            continue
    else:
        tmp=pc_plus+pow(2,N-i-1,pc+1)
        print(poptimes(tmp%(pc+1)))

Submission status: Accepted

Solution code:
numBits = int(input())
bitString = input()

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

count1 = bitString.count('1')
x = int(bitString,2)
xPlus = x % (count1 + 1)
if (count1 - 1) == 0:
  xMinus = 0
else:
  xMinus = x % (count1 - 1)

for i in range(numBits)  :
  if bitString[i] == '0':
    print(calculateAndPrintPopcount( (xPlus + pow(2,numBits-1-i,(count1+1))) % (count1+1) ) + 1)
  else:
    if (count1-1) == 0:
      print(0)
    else:
      print(calculateAndPrintPopcount( (xMinus - pow(2,numBits-1-i,(count1-1)) ) % (count1-1) ) +1)

Submission status: Accepted

Solution code:
N=int(input())
x=input()
num=0
n=0
def twice(a):
    ans=0
    while a:
        ans+=a%2
        a//=2
    return ans

ma=5*10**5
dp=[0]*ma
for i in range(1,ma):
    dp[i]=dp[i%twice(i)]+1
c=x.count("1")
a=int(x,2)%(c+1)
if c==1:
    for i in range(N):
        if x[i]=="0":
            print(dp[(a+pow(2,N-i-1,2))%2]+1)
        else:
            print(0)
    exit()
b=int(x,2)%(c-1)
for i in range(N):
    if x[i]=="0":
        print(dp[(a+pow(2,N-i-1,c+1))%(c+1)]+1)
    else:
        print(dp[(b-pow(2,N-i-1,c-1))%(c-1)]+1)

Submission status: Accepted

Solution code:
def popcnt_int(n): # n:int
    return bin(n).count('1')

def popcnt_bin(s): # s:str
    return s.count('1')

def poptimes(n, cnt=1): #:int, popcntのcounter
    if n==0:
        return cnt
    else:
        n %= popcnt_int(n)
        cnt += 1
        return poptimes(n, cnt)

n = int(input())
s = input() #これが直接処理し難い大きさ → 一回目の処理に要工夫。
# 要:いずれかを反転させた場合のbitの数は'反転前のbit数±1'の2通り！

s_int = int(s,2) # 2進数で読み込む
pc = popcnt_bin(s)
pc_plus = s_int % (pc+1) # 予めs_intのmod(pc+1)を取得
if  pc != 1: # mod(pc-1)も同様だが, bitが1個だけの場合に反転すると全て'0'になるためこの場合だけ例外扱い。
    pc_minus = s_int % (pc-1)
#print(n,s,s_int,pc,pc_plus,pc_minus)

# 以下で反転した差分を処理(一回目の処理完了) → 二回目以降は処理対象の値が大きくないためそのまま処理(poptimes関数)すればOK
for i in range(n):
    if s[i] == '1': # 1から0へと減じた差分を処理 
        if pc != 1: # 例外を考慮
            tmp = pc_minus - pow(2, n-i-1, pc-1) # ここで差し引くが, 差分をmod(pc-1)で処理
            print(poptimes(tmp % (pc-1))) # poptimesへパスする前にもmod(pc-1)
        else: # 例外処理: pc=1(反転して全部'0')の場合
            print(0)
            continue
    
    else: # 0から1への差分を処理, 必ず一つはbitが立つので例外は考慮不要
        tmp = pc_plus + pow(2, n-i-1, pc+1)
        print(poptimes(tmp % (pc+1)))

Submission status: Accepted

Solution code:
def popcnt_int(n): # n:int
    return bin(n).count('1')

def popcnt_bin(s): # s:str
    return s.count('1')

def poptimes(n, cnt=1): #:int
    if n==0:
        return cnt
    else:
        n %= popcnt_int(n)
        cnt += 1
        return poptimes(n, cnt)

n = int(input())
s = input()

s_int = int(s,2)
pc = popcnt_bin(s)
pc_plus = s_int % (pc+1)
if  pc != 1:
    pc_minus = s_int % (pc-1)
#print(n,s,s_int,pc,pc_plus,pc_minus)

for i in range(n):
    if s[i] == '1':
        if pc != 1:
            tmp = pc_minus - pow(2, n-i-1, pc-1)
            print(poptimes(tmp % (pc-1)))
        else:
            print(0)
            continue
    
    else:
        tmp = pc_plus + pow(2, n-i-1, pc+1)
        print(poptimes(tmp % (pc+1)))

Submission status: Accepted

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

def goes_to_zero(n):
  cnt = 0
  while(n > 0):
    n %= bin(n).count('1')
    cnt += 1
  return cnt
  
c1 = X.count('1')
xint = int(X,2)
xtp = xint % (c1 + 1)
if (c1 - 1) == 0:  
  xtm = 0
else:
  xtm = xint % (c1 - 1)
  
for i in range(n)  :
  if X[i] == '0':
    print(goes_to_zero( (xtp + pow(2,n-1-i,(c1+1))) % (c1+1) ) + 1)
  else:
    if (c1-1) == 0:
      print(0)
    else:
      print(goes_to_zero( (xtm - pow(2,n-1-i,(c1-1)) ) % (c1-1) ) +1)

Submission status: Accepted

Solution code:
def popcount(x):
    return bin(x).count('1')
 
def f(x):
    if x == 0:
        return 1
    return f(x%popcount(x))+1
 
n=int(input())
x=input()
xx=int(x,2)
p=x.count('1')
s=xx%(p+1)
if p!=1:
    t=xx%(p-1)
for i in range(n):
    if x[i]=='1':
        if p!=1:
            k=t
            k-=pow(2,n-i-1,p-1) 
            k%=p-1
        else:
            print(0)
            continue
    else:
        k=s
        k+=pow(2,n-i-1,p+1)
        k%=p+1
    print(f(k))

Submission status: Accepted

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

N=int(input())
X=input()[::-1]
c=X.count('1')

sump,summ=0,0
for i in range(N):
    if X[i]=='1':
        sump=(sump+pow(2,i,c+1))%(c+1)
        if c>1:
            summ=(summ+pow(2,i,c-1))%(c-1)
ans=[]
for i in range(N):
    if X[i]=='0':
        x=(sump+pow(2,i,c+1))%(c+1)
        ans.append(query(x)+1)
    else:
        if c==1:
            ans.append(0)
        else:
            x=(summ-pow(2,i,c-1)+c-1)%(c-1)
            ans.append(query(x)+1)
print(*ans[::-1],sep='\n')

Submission status: Accepted

Solution code:
def popcount(x):
    if x in memo:
        return memo[x]
    res=0
    while(x>0):
        if x&1:
            res+=1
        x//=2
    memo[x]=res
    return res
memo={}

N=int(input())
X=input()[::-1]
c=X.count('1')
count=[0]*(c+2)
for i in range(c+2):
    x=i
    cnt=0
    while(x>0):
        x=x%popcount(x)
        cnt+=1
    count[i]=cnt

if X[0]=='0':
    summ,sumn,sump=0,0,0
else:
    summ,sumn,sump=1,1,1
bitm,bitn,bitp=[0]*N,[0]*N,[0]*N
bitm[0],bitn[0],bitp[0]=1,1,1
for i in range(1,N):
    if c>1:
        bitm[i]=bitm[i-1]*2%(c-1)
    bitn[i]=bitn[i-1]*2%c
    bitp[i]=bitp[i-1]*2%(c+1)
    if X[i]=='1':
        if c>1:
            summ=(summ+bitm[i])%(c-1)
        sumn=(sumn+bitn[i])%c
        sump=(sump+bitp[i])%(c+1)
ans=[]
for i in range(N):
    if X[i]=='0':
        x=(sump+bitp[i])%(c+1)
        ans.append(count[x]+1)
    else:
        if c==1:
            ans.append(0)
        else:
            x=(summ-bitm[i]+c-1)%(c-1)
            ans.append(count[x]+1)
print(*ans[::-1],sep='\n')

Submission status: Accepted

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

    c1 = x.count('1')
    c1p, c1m = c1 + 1, c1 - 1
    sp = sum(pow(2, n - i - 1, c1p) for i, c in enumerate(x) if c == '1')
    sm = None
    if c1m > 0:
        sm = sum(pow(2, n - i - 1, c1m) for i, c in enumerate(x) if c == '1')

    A = [0] * n
    for i in range(n):
        nx = None
        if x[i] == '0':
            nx = (sp + pow(2, n - i - 1, c1p)) % c1p
        else:
            if sm is None:
                continue

            nx = (sm - pow(2, n - i - 1, c1m)) % c1m

        A[i] += 1

        while nx > 0:
            nx %= format(nx, 'b').count('1')
            A[i] += 1

    for a in A:
        print(a)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n = int( input() )
x = input()
x_pop = x.count( "1" )
x_pls = x_pop + 1
x_mns = x_pop - 1

# 2の冪乗のリスト．ただし後々に備えてpopcountで割った余りにしてある
rp = [ pow( 2, i, x_pls ) for i in range( n + 1 ) ]
if x_mns > 0:
    rm = [ pow( 2, i, x_mns ) for i in range( n + 1 ) ]
else:
    rm = [ 0 ] * ( n + 1 )

x = x[ : : -1 ]
rem_p = 0
rem_m = 0
for i in range( n ):
    if x[ i ] == "1":
        rem_p += rp[ i ]
        rem_m += rm[ i ]

for i in range( n - 1, -1, -1 ):
    if x[ i ] == "0":
        tmp = ( rem_p + rp[ i ] ) % x_pls
    elif x_mns > 0:
        tmp = ( rem_m - rm[ i ] ) % x_mns
    else: # popcount( X_i ) == 0
        print( 0 )
        continue
    ans = 1
    while tmp > 0:
        tmp = tmp % bin( tmp ).count( "1" )
        ans += 1
    print( ans )

Submission status: Accepted

Solution code:
from collections import deque
N = int(input())
X = str(input())
X = list(X)
#motokosu = X.count("1")
motokosu = 0
only = float("inf")
for i in range(N):
  if X[i] == "1":
    motokosu += 1
    only = i
if motokosu != 1:
  only = float("inf")
#print(motosuji,motokosu)
MAX = 2*pow(10,5)+10
base = [0 for _ in range(MAX)] #0から19までの答えを保存
for i in range(MAX):
  now = i
  temp = 0
  while now != 0:
    ones = 0
    tnow = now*1
    for t in range(len(bin(now))-2):
      if (now>>t)&1 == 1:
        ones += 1
    #print(i,ones,now)
    now = now%ones
    #print(now,base[now])
    base[i] = base[now] + 1
    break
    #temp += 1
  #base[i] = temp
#print(base)
A = []
pkosu = motokosu+1
mkosu = motokosu-1
P = deque([])
M = deque([])
ptemp = 1; mtemp = 1
for i in range(N):
  P.appendleft(ptemp%pkosu)
  ptemp = ptemp*2%pkosu
  if mkosu < 1:
    M.appendleft(0)
  else:
    M.appendleft(mtemp%mkosu)
    mtemp = mtemp*2%mkosu

pmotosuji = 0; mmotosuji = 0
for i in range(N):
  if X[i] == "1":
    pmotosuji = (pmotosuji+P[i])%pkosu
    if mkosu >= 1:
      mmotosuji = (mmotosuji+M[i])%mkosu
#print(P,M,pkosu,mkosu,pmotosuji,mmotosuji)

for i in range(N): #i桁目を入れ替える
  if only == i:
    print(0)
    continue
  if X[i] == "0": #その桁が0なら1にする
    kosu = motokosu + 1
    suji = (pmotosuji + P[i])%kosu
  else: #その桁が1なら0にする
    kosu = motokosu - 1
    if kosu == 0:
      suji = -1
    else:
      suji = (mmotosuji - M[i])%kosu
    
  #print(suji,kosu)
  #if suji == 0:
  #  ans = 0
  if suji == -1:
    ans = 1
  else:
    nxt = suji%kosu
    ans = 1+base[nxt]
  #A.append(ans)
  print(ans)

#print(*A,sep="\n")
#print(2**17)
#print(motokosu)