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: Runtime Error

Solution code:
NX = list(input().split())

N = int(NX[0])
X = NX[1]

for num in range(1,N+1):
    
    convert_num = list(X)
    check_num = int(convert_num[num-1])
    
    if check_num == 0:
        convert_num[num-1] = "1"
    else:
        convert_num[num-1] = "0"
    
    bin_count = convert_num.count("1")
    convert_num = int("".join(convert_num), 2)
    
    count = 0

    while convert_num != 0:
        convert_num =  convert_num % bin_count
        
        bin_str = bin(convert_num)
        bin_convert = bin_str[2:]
        
        bin_count = bin_convert.count("1")
        count += 1
        
    print(count)

Submission status: Runtime Error

Solution code:
NX = list(input().split())

N = int(NX[0])
X = NX[1]

for num in range(1,N+1):
    
    convert_num = list(X)
    check_num = int(convert_num[num-1])
    
    if check_num == 0:
        convert_num[num-1] = "1"
    else:
        convert_num[num-1] = "0"
    
    bin_count = convert_num.count("1")
    convert_num = int("".join(convert_num), 2)
    
    count = 0

    while convert_num != 0:
        convert_num =  convert_num % bin_count
        bin_count = convert2bit(convert_num). count("1")
        count += 1
        
    print(count)
    
def convert2bit(a):
        bin_str = bin(a)
        bin_convert = bin_str[2:]
        return bin_convert

Submission status: Runtime Error

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

for num in range(1,N+1):
    
    convert_num = list(X)
    check_num = int(convert_num[num-1])
    
    if check_num == 0:
        convert_num[num-1] = "1"
    else:
        convert_num[num-1] = "0"
    
    bin_count = convert_num.count("1")
    convert_num = int("".join(convert_num), 2)
    
    count = 0

    while convert_num != 0:
        convert_num =  convert_num % bin_count
        bin_count = convert2bit(convert_num). count("1")
        count += 1
        
    print(count)
    
def convert2bit(a):
        bin_str = bin(a)
        bin_convert = bin_str[2:]
        return bin_convert

Submission status: Runtime Error

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

def reverse(x, i):
    xl = list(x)
    xl[i] = "0" if xl[i] == "1" else "1"
    return "".join(xl)

def binstr2int(x):
    return int(x, 2)

def int2binstr(x):
    return "{0:b}".format(x)

def popcount(x):
    # x : int
    xs = int2binstr(x)
    pcount = sum([b == "1" for b in list(xs)])
    return pcount

def func(n):
    # n: int
    count = 0
    while n != 0:
        n = n % popcount(n)
        count += 1
    return count

# 10^5クラスのmodはコストが大きいので最初の一回だけ計算してあとは差分だけ修正する
xp = binstr2int(X)
ipc = sum([b == "1" for b in list(X)])   # Xのpopcount

# 重要! 1ビットを反転させたときの変化は高々1なので判定後のpopcountの値はpopcount(X)±1しかありえない
xp_mod_plus = xp % (ipc+1)    # 予めmodを計算O(N)  0->1の場合
xp_mod_minus = xp % (ipc-1)   # 予めmodを計算O(N)  1->0の場合
xs = list(X)

for i in range(1, N+1):
    p = 2**(N-i)
    if xs[i-1] == "1":
        diff = -(p % (ipc-1))
        x = (xp_mod_minus + diff) % (ipc-1)   # bit反転の修正分だけ反映
    else:
        diff = p % (ipc+1)
        x = (xp_mod_plus + diff) % (ipc+1)    # bit反転の修正分だけ反映
    print(func(x)+1)

Submission status: Runtime Error

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)
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: Runtime Error

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

pnumber = 0
pcount = 0
for i in range(n):
  if x[i] == '1':
    pnumber += 2 ** (n - i - 1)
    pcount += 1
d1 = pnumber % (pcount + 1)
lst = [(pcount + 1), (pcount - 1), d1]
if lst[1] > 0:
  d2 = pnumber % (pcount - 1)
  lst.append(d2)

for i in range(n):
  ans = 0
  d = 2 ** (n - i - 1)
  if x[i] == '0':
    count = lst[0]
    number = (lst[2] + d) % count
    ans += 1
  if x[i] == '1':
    count = lst[1]
    if count > 0:
      number = (lst[3] - d) % count
      ans += 1
  while number > 0 and count > 0:
    d = number
    count = 1
    while d > 1:
      if d % 2 == 1:
        count += 1
      d //= 2
    number %= count
    ans += 1
  print(ans)

Submission status: Runtime Error

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

pnumber = 0
pcount = 0
for i in range(n):
  if x[i] == '1':
    pnumber += 2 ** (n - i - 1)
    pcount += 1
d1 = pnumber % (pcount + 1)
d2 = pnumber % (pcount - 1)
lst = [(pcount + 1), (pcount - 1), d1, d2]

for i in range(n):
  ans = 0
  if x[i] == '0':
    count = lst[0]
    d = 2 ** (n - i - 1) % count
    number = (lst[2] + d) % count
  if x[i] == '1':
    count = lst[1]
    if count > 0:
      d = 2 ** (n - i - 1) % count
      number = (lst[3] - d) % count
  if count > 0:
    ans += 1
    while number > 0:
      d = number
      count = 1
      while d > 1:
        if d % 2 == 1:
          count += 1
        d //= 2
      number %= count
      ans += 1
  print(ans)

Submission status: Runtime Error

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

for i in range(n):
  number = 0
  ans = 0
  count = 0
  for j in range(n):
    if j == i:
      if x[i] == '0':
        number += 2 ** (n - i - 1)
        count += 1
    else:
      if x[j] == '1':
        number += 2 ** (n - j - 1)
        count += 1
  while True:
    number %= count
    ans += 1
    if number == 0:
      break
    d = number
    count = 1
    while d != 1:
      if d % 2 == 1:
        count += 1
      d //= 2
  print(ans)

Submission status: Runtime Error

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

for i in range(n):
  number = 0
  ans = 0
  for j in range(n):
    if j == i:
      if x[i] == '0':
        number += 2 ** (n - i - 1)
      if x[i] == '1':
        number += 0
    else:
      number += int(x[j]) * 2 ** (n - j - 1)
  while True:
    d = number
    count = 0
    while True:
      if d % 2 == 1:
        count += 1
      d = d // 2
      if d == 1:
        count += 1
        break
      if d == 0:
        break
    number = number % count
    ans += 1
    if number == 0:
      break
  print(ans)

Submission status: Runtime Error

Solution code:
import math

N=int(input())
ARRAY=[[[-1] * (N+1) for i in range(N+1)] for j in range(N+1)]

for i in range(1,N+1):
    count=0
    for x in range(1,int(math.sqrt(i))+1):
        for y in range(1,int(math.sqrt(i-x))+1):
            for z in range(1,int(math.sqrt(i-x-y))+1):

                if ARRAY[x][y][z]==-1:
                    res=x**2+y**2+z**2+x*y+y*z+z*x
                    ARRAY[x][y][z]=res
                    if res==i:
                        count+=1
                else:
                    res=ARRAY[x][y][z]
                    if res==i:
                        count+=1

    print(count)

Submission status: Runtime Error

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: Runtime Error

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

for i in range(n):
  number = 0
  ans = 0
  if x[i] == '0':
    a = 1
  if x[i] == '1':
    a = 0
  number += a * 2 ** (n - i - 1)
  if i > 0:
    for j in range(i):
      number += int(x[j]) * 2 ** (n - j - 1)
  if i < n - 1:
    for j in range(i + 1, n):
      number += int(x[j]) * 2 ** (n - j - 1)
  while True:
    d = number
    count = 0
    while True:
      if d % 2 == 1:
        count += 1
      d = d // 2
      if d == 1:
        count += 1
        break
      if d == 0:
        break
    number = number % count
    ans += 1
    if number == 0:
      break
  print(ans)

Submission status: Runtime Error

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

x0 = int('0b'+x,0)

ceil = 2*10**5+2
ppc = [0]*(ceil)

def popcount(n):    
  if n == 0:
    return 0
  if ppc[n] != 0:
    return ppc[n]
    
  b = bin(n).count('1')  
  tmp = n%b
  ppc[n] = popcount(tmp) + 1
  return ppc[n]

c1 = bin(x0).count('1')  
for i in range(n):
  p = 2 ** (n - i - 1)
  if x[i] == '1':    
    tmp = x0 - p
    tmp2 = tmp % (c1 - 1)
  else:
    tmp = x0 + p  
    tmp2 = tmp % (c1 + 1)
    
  if tmp > ceil:      
    print(popcount(tmp2)+1)
  else:
    print(popcount(tmp))

Submission status: Runtime Error

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 = pc+1
pc_minus = pc-1
#print(n,s,s_int,pc,pc_plus,pc_minus)

l_plus = [2**(n-i-1) % (pc+1) for i in range(n)]
l_minus = [2**(n-i-1) % (pc-1) for i in range(n)]
#print(l_plus)
#print(l_minus)

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

Submission status: Runtime Error

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)
pc_minus = s_int % (pc-1)
#print(n,s,s_int,pc,pc_plus,pc_minus)

l_plus = [2**(n-i-1) % (pc+1) for i in range(n)]
l_minus = [2**(n-i-1) % (pc-1) for i in range(n)]
#print(l_plus)
#print(l_minus)

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

Submission status: Runtime Error

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 = pc+1
pc_minus = pc-1
#print(n,s,s_int,pc,pc_plus,pc_minus)

l_plus = [2**(n-i-1) % (pc_plus) for i in range(n)]
l_minus = [2**(n-i-1) % (pc_minus) for i in range(n)]
#print(l_plus)
#print(l_minus)

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

Submission status: Runtime Error

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):
    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':
        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:
        x=(summ-bitm[i]+c-1)%(c-1)
        ans.append(count[x]+1)
print(*ans[::-1],sep='\n')

Submission status: Runtime Error

Solution code:
jello..world

Submission status: Runtime Error

Solution code:
n=int(input())
x=input()
for i in range(n):
    y=list(x)
    y[i]=str(1-int(y[i]))
    p=int("".join(y),2)
    a=0
    q=y.count("1")
    while True:
        a+=1
        p=p%q
        if p==0:
            print(a)
            break
        q=bin(p).count("1")

Submission status: Runtime Error

Solution code:
N = int(input())
X = str(input())
motosuji = int(X,2)
X = list(X)
motokosu = X.count("1")
#print(motosuji,motokosu)

base = [0 for _ in range(20)] #0から19までの答えを保存
for i in range(20):
  now = i
  temp = 0
  while now != 0:
    ones = 0
    tnow = now*1
    for t in range(5):
      if (now>>t)&1 == 1:
        ones += 1
    #print(i,ones,now)
    now = now%ones
    temp += 1
  base[i] = temp
#print(base)
A = []
for i in range(N): #i桁目を入れ替える
  if X[i] == "0": #その桁が0なら1にする
    suji = motosuji + pow(2,N-1-i)
    kosu = motokosu + 1
  else: #その桁が1なら0にする
    suji = motosuji - pow(2,N-1-i)
    kosu = motokosu - 1
    
  #print(suji,kosu)
  if suji == 0:
    nxt = 0
  else:
    nxt = suji%kosu
  ans = 1+base[nxt]
  A.append(ans)

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

Submission status: Runtime Error

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

base = [0 for _ in range(20)] #0から19までの答えを保存
for i in range(20):
  now = i
  temp = 0
  while now != 0:
    ones = 0
    tnow = now*1
    for t in range(5):
      if (now>>t)&1 == 1:
        ones += 1
    #print(i,ones,now)
    now = now%ones
    temp += 1
  base[i] = temp
#print(base)
A = []
for i in range(N): #i桁目を入れ替える
  suji = 0
  onekazu = 0
  for j in range(N):
    if i != j and X[j] == "1":
      suji += pow(2,N-1-j)
      onekazu += 1
    elif i == j and X[j] == "0":
      suji += pow(2,N-1-j)
      onekazu += 1
  #print(suji,onekazu)
  #if suji == 0:
  #  nxt = 0
  nxt = suji%onekazu
  ans = 1+base[nxt]
  A.append(ans)

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

Submission status: Runtime Error

Solution code:
# coding: utf-8

def popcount(x, ans):
    count = x.count("1")
    # print("x, count", x, count)
    x_10 = int(x, 2)
    x_10 = x_10 % count
    # print("x_10", x_10)
    ans += 1
    if x_10==0:
        # print("return", ans)
        return ans
    else:
        x_10 = str(bin(x_10)).lstrip("0b")
        ans = popcount(x_10, ans)
    # print("return", ans)
    return ans
    
def main(x):
    for i in range(len(x)):
        tmp = x.copy()
        tmp[i] = "1" if tmp[i]=="0" else "0"
        ans = 0
        tmp = "".join(tmp)
        # print(tmp)
        ans = popcount(tmp, ans)
        # print("ans", ans)
        print(ans)
        
if __name__ == "__main__":
    n = int(input())
    x = list(input())
    
    main(x)

Submission status: Runtime Error

Solution code:


def popcount(a):
    sum=0
    while(a!=0):
        sum=sum+x%10
        a=x/10
    print(sum)
    f(n,sum)


    
def f(N,X):
    remainder=N%X
    if(remainder>0):
        print(remainder)
        n=remainder
        popcount(remainder)
    elif(reminder==0):
        exit()

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

popcount(x)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(1000000000)
import math
from math import gcd
def lcm(a, b): return a * b // gcd(a, b)
from itertools import count, permutations, chain, product
from functools import lru_cache
from collections import deque, defaultdict
from pprint import pprint
ii = lambda: int(input())
mis = lambda: map(int, input().split())
lmis = lambda: list(mis())
INF = float('inf')
N1097 = 10**9 + 7

def meg(f, ok, ng):
    while abs(ok-ng)>1:
        mid = (ok+ng)//2
        if f(mid):
            ok=mid
        else:
            ng=mid
    return ok

def get_inv(n, modp):
    return pow(n, modp-2, modp)

def factorials_list(n, modp):    # 10**6
    fs = [1]
    for i in range(1, n+1):
        fs.append(fs[-1] * i % modp)
    return fs

def invs_list(n, fs, modp):     # 10**6
    invs = [get_inv(fs[-1], modp)]
    for i in range(n, 1-1, -1):
        invs.append(invs[-1] * i % modp)
    invs.reverse()
    return invs

def comb(n, k, modp):
    num = 1
    for i in range(n, n-k, -1):
        num = num * i % modp
    den = 1
    for i in range(2, k+1):
        den = den * i % modp
    return num * get_inv(den, modp) % modp

def comb_from_list(n, k, modp, fs, invs):   
    return fs[n] * invs[n-k] * invs[k] % modp

#

class UnionFindEx:
    def __init__(self, size):
        #正なら根の番号、負ならグループサイズ
        self.roots = [-1] * size
    def getRootID(self, i):
        r = self.roots[i]
        if r < 0:   #負なら根
            return i
        else:
            r = self.getRootID(r)
            self.roots[i] = r
            return r
    def getGroupSize(self, i):
        return -self.roots[self.getRootID(i)]
    def connect(self, i, j):
        r1, r2 = self.getRootID(i), self.getRootID(j)
        if r1 == r2:
            return False
        if self.getGroupSize(r1) < self.getGroupSize(r2):
            r1, r2 = r2, r1
        self.roots[r1] += self.roots[r2]    #サイズ更新
        self.roots[r2] = r1
        return True

Yes = 'Yes'
No = 'No'


def main():
    N = ii()
    X = input()
    X_POP = X.count('1')
    X_POP_P = X_POP + 1
    X_POP_N = X_POP - 1
    FX_P = 0
    FX_N = 0
    for i, b in enumerate(X):
        FX_P <<= 1
        FX_N <<= 1
        if b=='1':
            FX_P += 1
            FX_N += 1
        FX_P %= X_POP_P
        FX_N %= X_POP_N
    #
    def popcount(n):
        return bin(n).count('1')
    @lru_cache(None)
    def f(n):
        if n==0:
            return 0
        else:
            return f(n % popcount(n)) + 1
    ans = []
    for i, b in enumerate(reversed(X)):
        if b=='0':
            fx = (FX_P + pow(2, i, X_POP_P)) % X_POP_P
        else:
            fx = (FX_N - pow(2, i, X_POP_N)) % X_POP_N
        ans.append(f(fx)+1)
    print(*reversed(ans))



main()

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(1000000000)
import math
from math import gcd
def lcm(a, b): return a * b // gcd(a, b)
from itertools import count, permutations, chain, product
from functools import lru_cache
from collections import deque, defaultdict
from pprint import pprint
ii = lambda: int(input())
mis = lambda: map(int, input().split())
lmis = lambda: list(mis())
INF = float('inf')
N1097 = 10**9 + 7

def meg(f, ok, ng):
    while abs(ok-ng)>1:
        mid = (ok+ng)//2
        if f(mid):
            ok=mid
        else:
            ng=mid
    return ok

def get_inv(n, modp):
    return pow(n, modp-2, modp)

def factorials_list(n, modp):    # 10**6
    fs = [1]
    for i in range(1, n+1):
        fs.append(fs[-1] * i % modp)
    return fs

def invs_list(n, fs, modp):     # 10**6
    invs = [get_inv(fs[-1], modp)]
    for i in range(n, 1-1, -1):
        invs.append(invs[-1] * i % modp)
    invs.reverse()
    return invs

def comb(n, k, modp):
    num = 1
    for i in range(n, n-k, -1):
        num = num * i % modp
    den = 1
    for i in range(2, k+1):
        den = den * i % modp
    return num * get_inv(den, modp) % modp

def comb_from_list(n, k, modp, fs, invs):   
    return fs[n] * invs[n-k] * invs[k] % modp

#

class UnionFindEx:
    def __init__(self, size):
        #正なら根の番号、負ならグループサイズ
        self.roots = [-1] * size
    def getRootID(self, i):
        r = self.roots[i]
        if r < 0:   #負なら根
            return i
        else:
            r = self.getRootID(r)
            self.roots[i] = r
            return r
    def getGroupSize(self, i):
        return -self.roots[self.getRootID(i)]
    def connect(self, i, j):
        r1, r2 = self.getRootID(i), self.getRootID(j)
        if r1 == r2:
            return False
        if self.getGroupSize(r1) < self.getGroupSize(r2):
            r1, r2 = r2, r1
        self.roots[r1] += self.roots[r2]    #サイズ更新
        self.roots[r2] = r1
        return True

Yes = 'Yes'
No = 'No'


def main():
    N = ii()
    X = input()
    X_POP = X.count('1')
    X_POP_P = X_POP + 1
    X_POP_N = X_POP - 1
    FX_P = 0
    FX_N = 0
    for i, b in enumerate(X):
        FX_P <<= 1
        FX_N <<= 1
        if b=='1':
            FX_P += 1
            FX_N += 1
        FX_P %= X_POP_P
        FX_N %= X_POP_N
    #
    def popcount(n):
        return bin(n).count('1')
    def f(n):
        if n==0:
            return 0
        else:
            return f(n % popcount(n)) + 1
    ans = []
    for i, b in enumerate(reversed(X)):
        if b=='0':
            fx = (FX_P + pow(2, i, X_POP_P)) % X_POP_P
        else:
            fx = (FX_N - pow(2, i, X_POP_N)) % X_POP_N
            if i==1:
                print(fx)
        ans.append(f(fx)+1)
    print(*reversed(ans))



main()

Submission status: Runtime Error

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

cnt = [0]*(200001)
for i in range(1,200001):
    pc = bin(i).count('1')
    cnt[i] = cnt[i%pc] + 1
    
plus = X.count("1")+1
minus = X.count("1")-1

defp = int(X, 2)%plus
defm = int(X, 2)%minus

pl = 1
mi = 1
ans = []
for i, x in enumerate(X[::-1]):
    if x == "0":
        ans.append(cnt[(defp+pl)%plus]+1)
    else:
        if minus:
            ans.append(cnt[(defm-mi)%minus]+1)
        else:
            ans.append(0)
    pl = 2*pl%plus
    if minus:
        mi = 2*mi%minus

print(*ans[::-1], sep="\n")

Submission status: Runtime Error

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

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

plus = [0]*n
minus = [0]*n
plus[0] = 1%(cnt_1+1)
minus[0] = 1%(cnt_1-1)
for i in range(1,n):
    plus[i] = (plus[i-1]*2)%(cnt_1+1)
    minus[i] = (minus[i]*2)%(cnt_1-1)

cnt = [0]*(200001)

for i in range(1,200001):
    pc = bin(i).count('1')
    cnt[i] = cnt[i%pc] + 1

ans = []
for i,x in enumerate(X[::-1]):
    if x == "0":
        res = plus[n-1] + plus[i]
        ans.append(cnt[res]+1)
    else:
        res = minus[n-1] + minus[i]
        ans.append(cnt[res]+1)

print(*ans[::-1],sep="\n")

Submission status: Runtime Error

Solution code:
def cal(v,m,popcnt):
  ans=0
  #print('val is {} and m is{}'.format(v,m))
  while v:
    v=v%m
    m=popcnt[v%m]
    ans+=1
  return ans


n=int(input())
s=input()
init=int(s,2)
cnt=s.count('1')
popcnt=[0]*33

for v in range(33):
  popcnt[v]=bin(v)[2:].count('1')

for i in range(n):
  if s[i]=='0':
    print(cal(init+2**(n-1-i),cnt+1,popcnt))
  else:
    print(cal(init-2**(n-1-i),cnt-1,popcnt))

Submission status: Runtime Error

Solution code:
def cal(v,m,popcnt):
  ans=0
  while v:
    v=v%m
    m=popcnt[v%m]
    ans+=1
  return ans


n=int(input())
s=reversed(input())
cnt=bin(b)[2:].count('1')
popcnt=[0]*33
for v in range(33):
  popcnt[v]=bin(v)[2:].count('1')
 
  
for i in range(n):
  if s[i]=='0':
    print(cal(n+2**i,cnt+1,popcnt))
  else:
    print(cal(n-2**i,cnt-1,popcnt))

Submission status: Runtime Error

Solution code:
n=int(input())
x=input()
count_x=x.count("1")
px10=0
nx10=0
xi=[0]*n
ans=[0]*(n+1)
for i in range(1,n+1):
    popcount=format(i,"b").count("1")
    fx=i%popcount
    ans[i]=ans[fx]+1
for i in range(n):
    px10+=(int(x[i])*pow(2,n-1-i,count_x+1))%(count_x+1)
    if count_x!=0 and count_x!=1:
        nx10+=int(x[i])*pow(2,n-1-i,count_x-1)%(count_x-1)
for i in range(n):
    if x[i]=="0":
        xi10=(px10+pow(2,n-1-i,count_x+1))%(count_x+1)
        print(ans[xi10]+1)
    else:
        xi10=(nx10-pow(2,n-1-i,count_x-1))%(count_x-1)
        print(ans[xi10]+1)

Submission status: Runtime Error

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

def conv(a):
    if isinstance(a, str):
        cona = 0
        for idx, s in enumerate(a[::-1]):
            cona += (2 ** idx) * int(s)
        return cona
    else:
        b = ''
        while a > 0:
            if a%2:
                b = '1' + b
            else:
                b = '0' + b
            a = a // 2
        return b

def pc(num):
    if num % conv(num).count('1') == 0:
        return 1
    return 1 + pc(num % conv(num).count('1'))
    

for i in range(n):
    if x[i] == '1':
        x_ = x[:i] + '0' + x[i+1:]
    else:
        x_ = x[:i] + '1' + x[i+1:]
    xnum = conv(x_)
    print(pc(xnum))

Submission status: Runtime Error

Solution code:
import sys
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
read = sys.stdin.buffer.read
sys.setrecursionlimit(10 ** 7)
INF = float('inf')

N = int(input())
Xs = input()
Xint = eval("0b"+Xs)
X = list(map(int, list(Xs)))

def popcount(Xi):
    return Xi.count(1)

x_pc = popcount(X)
if x_pc == 0:
    for _ in range(0, N):
        print(0)
        quit()
x_pc1 = x_pc + 1
x_pc2 = x_pc - 1
# print("Xs: {} x_pc1: {} x_pc2: {}".format(Xs, x_pc1, x_pc2))

x_mod1 = Xint % x_pc1
x_mod2 = Xint % x_pc2
# print("x_mod1: {} x_mod2: {}".format(x_mod1, x_mod2))

anss = [0] * N
for i in range(N):
    j = N - i - 1
    if X[i] == 0:
        mod = (x_mod1 + ((1 << j) % x_pc1)) % x_pc1
        # mod = (Xint + (1 << j)) % x_pc1
        anss[i] = mod
    else:
        if x_pc2 == 0:
            continue
        mod = ((x_mod2 - ((1 << j) % x_pc2)) + x_pc2) % x_pc2
        # mod = (Xint - (1 << j)) % x_pc2
        anss[i] = mod

# print(anss)
# quit()
for Xi in anss:
    if Xi == 0:
        print(1)
        continue

    pc = bin(Xi).count("1")
    ans = 1
    while pc:
        Xi = Xi % pc
        pc = bin(Xi).count("1")
        ans += 1
    print(ans)

Submission status: Runtime Error

Solution code:
import sys
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
read = sys.stdin.buffer.read
sys.setrecursionlimit(10 ** 7)
INF = float('inf')

N = int(input())
Xs = input()
Xint = eval("0b"+Xs)
X = list(map(int, list(Xs)))

def popcount(Xi):
    return Xi.count(1)

x_pc = popcount(X)
if x_pc == 0:
    for _ in range(0, N):
        print(0)
        quit(t)
x_pc1 = x_pc + 1
x_pc2 = x_pc - 1
# print("Xs: {} x_pc1: {} x_pc2: {}".format(Xs, x_pc1, x_pc2))

x_mod1 = Xint % x_pc1
x_mod2 = Xint % x_pc2
# print("x_mod1: {} x_mod2: {}".format(x_mod1, x_mod2))

anss = [0] * N
for i in range(N):
    j = N - i - 1
    if X[i] == 0:
        mod = (x_mod1 + ((1 << j) % x_pc1)) % x_pc1
        # mod = (Xint + (1 << j)) % x_pc1
        anss[i] = mod
    else:
        if x_pc2 == 0:
            continue
        mod = ((x_mod2 - ((1 << j) % x_pc2)) + x_pc2) % x_pc2
        # mod = (Xint - (1 << j)) % x_pc2
        anss[i] = mod

# print(anss)
# quit()
for Xi in anss:
    if Xi == 0:
        print(1)
        continue

    pc = bin(Xi).count("1")
    ans = 1
    while pc:
        Xi = Xi % pc
        pc = bin(Xi).count("1")
        ans += 1
    print(ans)

Submission status: Runtime Error

Solution code:
import sys
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
read = sys.stdin.buffer.read
sys.setrecursionlimit(10 ** 7)
INF = float('inf')

N = int(input())
Xs = input()
Xint = eval("0b"+Xs)
X = list(map(int, list(Xs)))

def popcount(Xi):
    return Xi.count(1)

x_pc = popcount(X)
if x_pc == 0:
    for _ in range(N):
        print(0)
    quit()
x_pc1 = x_pc + 1
x_pc2 = x_pc - 1
# print("Xs: {} x_pc1: {} x_pc2: {}".format(Xs, x_pc1, x_pc2))

x_mod1 = Xint % x_pc1
x_mod2 = Xint % x_pc2
# print("x_mod1: {} x_mod2: {}".format(x_mod1, x_mod2))

anss = []
for i in range(N):
    j = N - i - 1
    if X[i] == 0:
        mod = (x_mod1 + ((1 << j) % x_pc1)) % x_pc1
        # mod = (Xint + (1 << j)) % x_pc1
        anss.append(mod)
    else:
        mod = (x_mod2 - ((1 << j) % x_pc2)) % x_pc2
        # mod = (Xint - (1 << j)) % x_pc2
        anss.append(mod)

# print(anss)
# quit()
for Xi in anss:
    if Xi == 0:
        print(1)
        continue

    pc = bin(Xi).count("1")
    ans = 1
    while pc:
        Xi = Xi % pc
        pc = bin(Xi).count("1")
        ans += 1
    print(ans)