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: Wrong Answer

Solution code:
n = int(input())
x = '0b' + input()
f = [-1]*n

num = int(x, 2)
xcnt1 = x.count('1')
if xcnt1 == 0:
    print(0)
    exit()

for i in range(n):
    if x[i+2] == '0':
        f[i] = (num + 2**(n-i-1)) % (xcnt1 + 1)
    else:
        if xcnt1 - 1 == 0:
            continue
        f[i] = (num - 2**(n-i-1)) % (xcnt1 - 1)

for i in range(n):
    if f[i] == -1:
        print(0)
        continue

    intx = f[i]
    x = bin(intx)
    len1 = x.count('1')
    cnt = 1
    while True:
        if intx == 0:
            print(cnt)
            break
        
        intx = intx % len1
        x = bin(intx)
        len1 = x.count('1')
        cnt += 1

Submission status: Wrong Answer

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


B_1 = B.count("1")
mod_list_m1 = []
mod_list_p1 = []
if B_1 == 1:
    for i in range(N):
        print(0)
else:
    mod_m1 = 0
    mod_p1 = 0
    for i in range(N):
        mm1 = (2**(N-i-1)) % (B_1-1)
        mp1 = (2**(N-i-1)) % (B_1+1)
        mod_list_m1.append(mm1)
        mod_list_p1.append(mp1)
        mod_m1 += int(B[i])*mm1
        mod_p1 += int(B[i])*mp1

    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):
        mod = (mod_m1 - mod_list_m1[i]) % (B_1-1) if int(B[i]) == 1 else (mod_p1 + mod_list_p1[i]) % (B_1+1)
        iter = 1
        if mod == 0:
            print(iter)
        else:
            print(calc_small(mod, iter))

Submission status: Wrong Answer

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

from collections import Counter
cnt1 = Counter( list(x) )['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

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

Submission status: Wrong Answer

Solution code:
def resolve():
  N = int(input())
  X = input()
  base_1_count = X.count("1")

  for i in range(N):
    tar_X = list(X)
    first_1_count = base_1_count
    if tar_X[i] == "1":
      first_1_count -= 1
      tar_X[i] = "0"
    else:
      first_1_count += 1
      tar_X[i] = "1"
    target_int = int(''.join(tar_X), 2)
    count = 0
    num_of_1 = first_1_count
    while target_int != 0:
      target_int = target_int % num_of_1
      num_of_1 = bin(target_int).count("1")
      print(bin(target_int))
      count += 1
    print(count)

if __name__ == "__main__":
  resolve()

Submission status: Wrong Answer

Solution code:
n=int(input())
x=input()
xx=x.count('1')
if xx!=1 and xx!=0:
    xx2=int(x,2)
    a1=xx2%(xx-1)
    a2=xx2%(xx+1)
    for i in range(n):
        k=2**(n-1-i)
        if x[i]=='0':
            k=k%(xx+1)
            aa1=(a2+k)%(xx+1)
            aa2=str(bin(aa1)).count('1')
        else:
            k=k%(xx-1)
            aa1=(a2+k)%(xx-1)
            aa2=str(bin(aa1)).count('1')
        if aa1==0:
            print(1)
        else:
            count=1
            while aa1!=0:
                aa1%=aa2
                aa2=str(bin(aa1)).count('1')
                count+=1
            print(count)
elif xx==0:
    for i in range(n):
        print(1)
else:
    x1=int(x,2)
    for i in range(n):
        k=2**(n-1-i)
        if x[i]=='1':
            print(0)
        else:
            x1+=k
            x2=2
            count=0
            while x1!=0:
                x1%=x2
                x2=str(bin(x1)).count('1')
                count+=1
            print(count)

Submission status: Wrong Answer

Solution code:
N = int(input())
x = list(input())[::-1]
num = 0
nump = 0
numm = 0
pop_num = 0
for i in range(N):
        if x[i] == "1":
            pop_num += 1
for i in range(N):
    if x[i] == "1":
        num += pow(2,i,pop_num)
        num %= pop_num 
        nump += pow(2,i,pop_num+1)
        nump %= pop_num  + 1
        if pop_num-1 != 0:
            numm += pow(2,i,pop_num - 1)
            numm %= pop_num - 1



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

x = x[::-1]
def calc(i,depth,n):
    if depth == 0:
        if x[i] == "1":
            tmp = numm
            if pop_num - 1 != 0:
                tmp -= pow(2,N-i-1,pop_num-1)
                tmp %= (pop_num - 1)
            else:
                return 1
            return calc(i,depth+1,tmp)
        else:
            tmp = nump
            tmp += pow(2,N-i-1,pop_num+1)
            tmp %= (pop_num + 1)
            return calc(i,depth+1,tmp)
    else:
        if n == 0: return depth
        return calc(i,depth+1, n % popcnt(n))
        

for i in range(N):
    print(calc(i,0,0))

Submission status: Wrong Answer

Solution code:
N = int(input())
x = list(input())[::-1]
print(x)
num = 0
nump = 0
numm = 0
pop_num = 0
for i in range(N):
        if x[i] == "1":
            pop_num += 1
for i in range(N):
    if x[i] == "1":
        num += pow(2,i,pop_num)
        num %= pop_num 
        nump += pow(2,i,pop_num+1)
        nump %= pop_num  + 1
        if pop_num-1 != 0:
            numm += pow(2,i,pop_num - 1)
            numm %= pop_num - 1



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

x = x[::-1]
def calc(i,depth,n):
    if depth == 0:
        if x[i] == "1":
            tmp = numm
            if pop_num - 1 != 0:
                tmp -= pow(2,N-i-1,pop_num-1)
                tmp %= (pop_num - 1)
            else:
                return 1
            return calc(i,depth+1,tmp)
        else:
            tmp = nump
            tmp += pow(2,N-i-1,pop_num+1)
            tmp %= (pop_num + 1)
            return calc(i,depth+1,tmp)
    else:
        if n == 0: return depth
        return calc(i,depth+1, n % popcnt(n))
        

for i in range(N):
    print(calc(i,0,0))

Submission status: Wrong Answer

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



B_array = list(map(int, list(B)))
B_1 = B.count("1")
mod_list_m1 = []
mod_list_p1 = []
if B_1 == 1:
    for i in range(N):
        print(0)
else:
    mod_m1 = 0
    mod_p1 = 0
    for i in range(N):
        mm1 = (2**(N-i-1)) % (B_1-1)
        mp1 = (2**(N-i-1)) % (B_1+1)
        mod_list_m1.append(mm1)
        mod_list_p1.append(mp1)
        mod_m1 += B_array[i]*mm1
        mod_p1 += B_array[i]*mp1

    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):
        mod = (mod_m1 - mod_list_m1[i]) % (B_1-1) if B_array[i] == 1 else (mod_p1 + mod_list_p1[i]) % (B_1+1)
        iter = 1
        if mod == 0:
            print(iter)
        else:
            print(calc_small(mod, iter))

Submission status: Wrong Answer

Solution code:
def bitcount(N):  # 立ってるbitの数
    bitcnt = [0]
    for _ in range(N):
        bitcnt += [i + 1 for i in bitcnt]
    return bitcnt


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

num, cnt = int(x, 2), x.count('1')
lbit = bitcount(18)
for i in range(n):
    ans = 1
    num1 = num % (cnt + 1)
    print(ans)

Submission status: Wrong Answer

Solution code:
def bitcount(N):  # 立ってるbitの数
    bitcnt = [0]
    for _ in range(N):
        bitcnt += [i + 1 for i in bitcnt]
    return bitcnt


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

num, cnt = int(x, 2), x.count('1')
num0, num1 = num % (cnt + 1), num % max(cnt - 1, 1)
lbit = bitcount(18)
for i in range(n):
    ans = 1
    print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
x = list(input())[::-1]
print(x)
num = 0
nump = 0
numm = 0
pop_num = 0
for i in range(N):
        if x[i] == "1":
            pop_num += 1
for i in range(N):
    if x[i] == "1":
        num += pow(2,i,pop_num)
        num %= pop_num 
        nump += pow(2,i,pop_num+1)
        nump %= pop_num  + 1
        if pop_num-1 != 0:
            numm += pow(2,i,pop_num - 1)
            numm %= pop_num - 1



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

x = x[::-1]
def calc(i,depth,n):
    if depth == 0:
        if x[i] == "1":
            tmp = numm
            tmp -= pow(2,N-i-1,pop_num-1)
            tmp %= (pop_num - 1)
            return calc(i,depth+1,tmp)
        else:
            tmp = nump
            tmp += pow(2,N-i-1,pop_num+1)
            tmp %= (pop_num + 1)
            return calc(i,depth+1,tmp)
    else:
        if n == 0: return depth
        return calc(i,depth+1, n % popcnt(n))
        

for i in range(N):
    exit()
    print(calc(i,0,0))

Submission status: Wrong Answer

Solution code:
import sys

input = sys.stdin.readline


def main():
    N = int(input())
    X = input()

    popcount_X = X.count("1")
    if popcount_X == 0:
        ans = [1] * N
    elif popcount_X == 1:
        ans = [1] * N
        ans[X.index("1")] = 0
        ans[-1] = 2
    else:
        X_mod_popcount_X_p = int(X, 2) % (popcount_X + 1)
        X_mod_popcount_X_m = int(X, 2) % (popcount_X - 1)
        ans = [0] * N
        for i in range(N):
            if X[i] == "0":
                Y = X_mod_popcount_X_p + pow(2, N - 1 - i, mod=popcount_X + 1)
                Y = Y % (popcount_X + 1)
            else:
                Y = X_mod_popcount_X_m - pow(2, N - 1 - i, mod=popcount_X - 1)
                Y = Y + (popcount_X - 1)
                Y = Y % (popcount_X - 1)
            count = 1
            while Y > 0:
                popcount = bin(Y).count("1")
                Y = Y % popcount
                count += 1
            ans[i] = count

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


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
N = int(input())
x = list(input())[::-1]
print(x)
num = 0
nump = 0
numm = 0
pop_num = 0
for i in range(N):
        if x[i] == "1":
            pop_num += 1
try:
    for i in range(N):
        if x[i] == "1":
            num += pow(2,i,pop_num)
            num %= pop_num 
            nump += pow(2,i,pop_num+1)
            nump %= pop_num  + 1
            numm += pow(2,i,pop_num - 1)
            numm %= pop_num - 1

except:
    while True:
        print("a",end='')


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

x = x[::-1]
def calc(i,depth,n):
    if depth == 0:
        if x[i] == "1":
            tmp = numm
            tmp -= pow(2,N-i-1,pop_num-1)
            tmp %= (pop_num - 1)
            return calc(i,depth+1,tmp)
        else:
            tmp = nump
            tmp += pow(2,N-i-1,pop_num+1)
            tmp %= (pop_num + 1)
            return calc(i,depth+1,tmp)
    else:
        if n == 0: return depth
        return calc(i,depth+1, n % popcnt(n))
        

for i in range(N):
    exit()
    print(calc(i,0,0))

Submission status: Wrong Answer

Solution code:
N = int(input())
x = list(input())[::-1]
print(x)
num = 0
nump = 0
numm = 0
pop_num = 0
try:
    for i in range(N):
            if x[i] == "1":
                pop_num += 1
    for i in range(N):
        if x[i] == "1":
            num += pow(2,i,pop_num)
            num %= pop_num 
            nump += pow(2,i,pop_num+1)
            nump %= pop_num  + 1
            numm += pow(2,i,pop_num - 1)
            numm %= pop_num - 1

except:
    while True:
        print("a",end='')


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

x = x[::-1]
def calc(i,depth,n):
    if depth == 0:
        if x[i] == "1":
            tmp = numm
            tmp -= pow(2,N-i-1,pop_num-1)
            tmp %= (pop_num - 1)
            return calc(i,depth+1,tmp)
        else:
            tmp = nump
            tmp += pow(2,N-i-1,pop_num+1)
            tmp %= (pop_num + 1)
            return calc(i,depth+1,tmp)
    else:
        if n == 0: return depth
        return calc(i,depth+1, n % popcnt(n))
        

for i in range(N):
    exit()
    print(calc(i,0,0))

Submission status: Wrong Answer

Solution code:
import sys

input = sys.stdin.readline


def main():
    N = int(input())
    X = input()

    popcount_X = X.count("1")
    if popcount_X == 0:
        ans = [1] * N
    elif popcount_X == 1:
        ans = [1] * N
        ans[X.index("1")] = 0
    else:
        X_mod_popcount_X_p = int(X, 2) % (popcount_X + 1)
        X_mod_popcount_X_m = int(X, 2) % (popcount_X - 1)
        ans = [0] * N
        for i in range(N):
            if X[i] == "0":
                Y = X_mod_popcount_X_p + pow(2, N - 1 - i, mod=popcount_X + 1)
                Y = Y % (popcount_X + 1)
            else:
                Y = X_mod_popcount_X_m - pow(2, N - 1 - i, mod=popcount_X - 1)
                Y = Y + (popcount_X - 1)
                Y = Y % (popcount_X - 1)
            count = 1
            while Y > 0:
                popcount = bin(Y).count("1")
                Y = Y % popcount
                count += 1
            ans[i] = count

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


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

cnt1 = sum( i=='1' for i in x )
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
    mod = x10mod_m
    cntx = cnt1-1
  else:
    mod = x10mod_p
    cntx = cnt1+1
  mod += (1<<i) % cntx
  cnt = 1
  mod = format(mod, 'b')
  
  while True:
    if mod == '0':
      break
    one_cnt = sum( j=='1' for j in mod )
    mod_10 = int(mod,10)
    mod = format( mod_10 % one_cnt, 'b')
    cnt += 1
  print(cnt)

Submission status: Wrong Answer

Solution code:
import sys

input = sys.stdin.readline


def main():
    N = int(input())
    X = input()

    popcount_X = X.count("1")
    if popcount_X == 0:
        ans = [1] * N
    elif popcount_X == 1:
        ans = [1] * N
        ans[X.index("1")] = 0
    else:
        X_mod_popcount_X_p = int(X, 2) % (popcount_X + 1)
        X_mod_popcount_X_m = int(X, 2) % (popcount_X - 1)
        ans = [0] * N
        for i in range(N):
            if X[i] == "0":
                Y = X_mod_popcount_X_p + pow(2, N - 1 - i, mod=popcount_X + 1)
                Y = Y % (popcount_X + 1)
            else:
                Y = X_mod_popcount_X_m - pow(2, N - 1 - i, mod=popcount_X - 1)
                Y = Y % (popcount_X - 1)
            count = 1
            while Y > 0:
                popcount = bin(Y).count("1")
                Y = Y % popcount
                count += 1
            ans[i] = count

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


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
from heapq import heappush, heappop, heapify
from collections import deque, defaultdict, Counter
import itertools
from itertools import permutations, combinations, accumulate, product, combinations_with_replacement
import sys
import bisect
import string
import math
import time


def I(): return int(input())
def S(): return input()
def MI(): return map(int, input().split())
def MS(): return map(str, input().split())
def LI(): return [int(i) for i in input().split()]
def LI_(): return [int(i)-1 for i in input().split()]
def StoI(): return [ord(i)-97 for i in input()]
def ItoS(nn): return chr(nn+97)
def input(): return sys.stdin.readline().rstrip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def print_matrix(mat):
    for i in range(len(mat)):
        print(*['IINF' if v == IINF else "{:0=4}".format(v) for v in mat[i]])


yn = {False: 'No', True: 'Yes'}
YN = {False: 'NO', True: 'YES'}
MOD = 10**9+7
inf = float('inf')
IINF = 10**19
l_alp = string.ascii_lowercase
u_alp = string.ascii_uppercase
ts = time.time()
sys.setrecursionlimit(10**6)
nums = ['1', '2', '3', '4', '5', '6', '7', '8', '9', '10']
show_flg = False
# show_flg = True


def main():
    N = I()
    X = S()
    bit_cnt = X.count('1')
    one_inv_cnt = bit_cnt - 1
    zero_inv_cnt = bit_cnt + 1
    MAX = 2 * 10 ** 5 + 1

    # 大きい数の余り
    # 繰り返し２乗法の発展？
    zero_inv_mod = 0
    one_inv_mod = 0
    # for i in range(len(X)-1, -1, -1):
    for i in range(0, len(X)):
        b = int(X[i])
        if one_inv_cnt != 0:
            one_inv_mod = (one_inv_mod * 2 + b) % one_inv_cnt
        zero_inv_mod = (zero_inv_mod * 2 + b) % zero_inv_cnt

    f = [0] * MAX
    pop_count = [0] * MAX
    for i in range(1, MAX):
        pop_count[i] = pop_count[i//2] + i % 2
        f[i] = f[i % pop_count[i]] + 1


    #pow2 の前計算
    one_pow2 = [1] * 220000
    zero_pow2 = [1] * 220000
    for i in range(1, 220000):
        if one_inv_cnt != 0:
            one_pow2[i] = one_pow2[i-1] * 2 % one_inv_cnt
        zero_pow2[i] = zero_pow2[i-1] * 2 % zero_inv_cnt

    for i in range(len(X)-1, -1, -1):
        if X[N-1-i] == '1':
            if one_inv_mod != 0:
                nxt = one_inv_mod
                # nxt -= pow(2, i, one_inv_cnt)
                nxt -= one_pow2[i]
                nxt %= one_inv_cnt
                print(f[nxt] + 1)
            else:
                print(0)
        else:
            nxt = zero_inv_mod
            # nxt += pow(2, i, zero_inv_cnt)
            nxt += zero_pow2[i]
            nxt %= zero_inv_cnt
            print(f[nxt] + 1)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from heapq import heappush, heappop, heapify
from collections import deque, defaultdict, Counter
import itertools
from itertools import permutations, combinations, accumulate, product, combinations_with_replacement
import sys
import bisect
import string
import math
import time


def I(): return int(input())
def S(): return input()
def MI(): return map(int, input().split())
def MS(): return map(str, input().split())
def LI(): return [int(i) for i in input().split()]
def LI_(): return [int(i)-1 for i in input().split()]
def StoI(): return [ord(i)-97 for i in input()]
def ItoS(nn): return chr(nn+97)
def input(): return sys.stdin.readline().rstrip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def print_matrix(mat):
    for i in range(len(mat)):
        print(*['IINF' if v == IINF else "{:0=4}".format(v) for v in mat[i]])


yn = {False: 'No', True: 'Yes'}
YN = {False: 'NO', True: 'YES'}
MOD = 10**9+7
inf = float('inf')
IINF = 10**19
l_alp = string.ascii_lowercase
u_alp = string.ascii_uppercase
ts = time.time()
sys.setrecursionlimit(10**6)
nums = ['1', '2', '3', '4', '5', '6', '7', '8', '9', '10']
show_flg = False
# show_flg = True


def main():
    N = I()
    X = S()
    bit_cnt = X.count('1')
    one_inv_cnt = bit_cnt - 1
    zero_inv_cnt = bit_cnt + 1
    MAX = 2 * 10 ** 5 + 1

    # 大きい数の余り
    # 繰り返し２乗法の発展？
    zero_inv_mod = 0
    one_inv_mod = 0
    # for i in range(len(X)-1, -1, -1):
    for i in range(0, len(X)):
        b = int(X[i])
        if one_inv_mod != 0:
            one_inv_mod = (one_inv_mod * 2 + b) % one_inv_cnt
        zero_inv_mod = (zero_inv_mod * 2 + b) % zero_inv_cnt

    f = [0] * MAX
    pop_count = [0] * MAX
    for i in range(1, MAX):
        pop_count[i] = pop_count[i//2] + i % 2
        f[i] = f[i % pop_count[i]] + 1


    #pow2 の前計算
    one_pow2 = [1] * 220000
    zero_pow2 = [1] * 220000
    for i in range(1, 220000):
        if one_inv_cnt != 0:
            one_pow2[i] = one_pow2[i-1] * 2 % one_inv_cnt
        zero_pow2[i] = zero_pow2[i-1] * 2 % zero_inv_cnt

    for i in range(len(X)-1, -1, -1):
        if X[N-1-i] == '1':
            if one_inv_mod != 0:
                nxt = one_inv_mod
                # nxt -= pow(2, i, one_inv_cnt)
                nxt -= one_pow2[i]
                nxt %= one_inv_cnt
                print(f[nxt] + 1)
            else:
                print(0)
        else:
            nxt = zero_inv_mod
            # nxt += pow(2, i, zero_inv_cnt)
            nxt += zero_pow2[i]
            nxt %= zero_inv_cnt
            print(f[nxt] + 1)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from heapq import heappush, heappop, heapify
from collections import deque, defaultdict, Counter
import itertools
from itertools import permutations, combinations, accumulate, product, combinations_with_replacement
import sys
import bisect
import string
import math
import time


def I(): return int(input())
def S(): return input()
def MI(): return map(int, input().split())
def MS(): return map(str, input().split())
def LI(): return [int(i) for i in input().split()]
def LI_(): return [int(i)-1 for i in input().split()]
def StoI(): return [ord(i)-97 for i in input()]
def ItoS(nn): return chr(nn+97)
def input(): return sys.stdin.readline().rstrip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def print_matrix(mat):
    for i in range(len(mat)):
        print(*['IINF' if v == IINF else "{:0=4}".format(v) for v in mat[i]])


yn = {False: 'No', True: 'Yes'}
YN = {False: 'NO', True: 'YES'}
MOD = 10**9+7
inf = float('inf')
IINF = 10**19
l_alp = string.ascii_lowercase
u_alp = string.ascii_uppercase
ts = time.time()
sys.setrecursionlimit(10**6)
nums = ['1', '2', '3', '4', '5', '6', '7', '8', '9', '10']
show_flg = False
# show_flg = True


def main():
    N = I()
    X = S()
    bit_cnt = X.count('1')
    one_inv_cnt = bit_cnt - 1
    zero_inv_cnt = bit_cnt + 1
    MAX = 2 * 10 ** 5 + 1

    # 大きい数の余り
    # 繰り返し２乗法の発展？
    zero_inv_mod = 0
    one_inv_mod = 0
    # for i in range(len(X)-1, -1, -1):
    for i in range(0, len(X)):
        b = int(X[i])
        if one_inv_mod != 0:
            one_inv_mod = (one_inv_mod * 2 + b) % one_inv_cnt
        zero_inv_mod = (zero_inv_mod * 2 + b) % zero_inv_cnt

    f = [0] * MAX
    pop_count = [0] * MAX
    for i in range(1, MAX):
        pop_count[i] = pop_count[i//2] + i % 2
        f[i] = f[i % pop_count[i]] + 1


    # print(zero_inv_cnt, zero_inv_mod)
    # print(one_inv_cnt, one_inv_mod)

    for i in range(len(X)-1, -1, -1):
        if X[N-1-i] == '1':
            if one_inv_mod != 0:
                nxt = one_inv_mod
                nxt -= pow(2, i, one_inv_cnt)
                nxt %= one_inv_cnt
                print(f[nxt] + 1)
            else:
                print(0)
        else:
            nxt = zero_inv_mod
            nxt += pow(2, i, zero_inv_cnt)
            nxt %= zero_inv_cnt
            print(f[nxt] + 1)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
LIM=200004
L=[0]*LIM

def bin_sum(Y):
    S=bin(Y)[2:]
    count=0
    for i in range(len(S)):
        count+=int(S[i])
    return count

def bin_sum2(Y):
    count=0
    for i in range(len(Y)):
        count+=int(Y[i])
    return count

for i in range(1,LIM):
    L[i]+=bin_sum(i)

def pop_num(N,b,L):
    if N==0:
        return 0
    v=N%b
    return pop_num(v,L[v],L)+1
    
M=[0]*200005
for i in range(1,200004):
    M[i]+=pop_num(i,L[i],L)
X=int(input())
Y=input()
d=bin_sum2(Y)
e=int(Y,2)%(d+1)
f=int(Y,2)%max(1,(d-1))
for i in range(X):
    if Y[i]=="0":
        b=d+1
        g=(e+2**(X-1-i))%b
    else:
        b=max(d-1,1)
        g=(f-2**(X-1-i)%b+b)%b
    if d==1 and X==1:
        print(0)
    elif g==0:
        print(1)
    else:
        print(M[g]+1)

Submission status: Wrong Answer

Solution code:
import sys
input=sys.stdin.readline
n=int(input())
x=input().rstrip()
pop=x.count("1")
def popcnt(x):
    cnt=str(bin(x)).count("1")
    x%=cnt
    return x

a=0
for i in range(n):
    if x[-i-1]=="1":
        a+=2**i
for i in range(n):
    if x[i]=="1":
        b=a-2**(n-i-1)
        q=pop-1
        if q==0:
            print(0)
            break
    else:
        b=a+2**(n-i-1)
        q=pop+1
    b%=q
    p=1
    while b>=1:
        b=popcnt(b)
        p+=1
    print(p)

Submission status: Wrong Answer

Solution code:
from heapq import *
import sys
from collections import *
from itertools import *
from decimal import *
import copy
from bisect import *
import math
sys.setrecursionlimit(4100000)
def gcd(a,b):
    if(a%b==0):return(b)
    return (gcd(b,a%b))
input=lambda :sys.stdin.readline().rstrip()


N=int(input())
X=input()
C=X.count("1")

lst=[]
lstcount=[]
for x in [C-1,C+1]:
    flg=0
    if x<=0:
        lst.append(0)
        lstcount.append(0)
    else:
        Z=0
        p=1
        for i in range(N):
            if X[-i-1]=="1":
                Z+=p
            p*=2
            if Z>=x:
                Z%=x
                flg=1
            if flg:
                p%=x
        lst.append(Z)
        lstcount.append(flg)
#print(lst)
fac1=[1]
fac2=[1]
C1=max(C-1,1)
C2=max(C+1,1)
for i in range(N):
    fac1.append(fac1[-1]*2%C1)
    fac2.append(fac2[-1]*2%C2)

for i in range(N):

    _C=C+(1 if X[i]=="0"  else -1 )
    if _C==0:
        print(0)
        continue
    if  X[i]=="0":
        lstidx=1
    else:
        lstidx=0

    idx=(N-1-i)

    value=lst[lstidx]+(fac2[idx] if  X[i]=="0" else fac1[idx])
    bit=value
    count=0
    while value and _C:
        count+=1
        value%=_C
        _C=0
        bit=value
        while bit:
            _C+=bit&1
            bit>>=1
    print(max(count,1))

Submission status: Wrong Answer

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

J=X.count("1")

A=[0]*N
A[-1]=1
for i in range(2,N+1):
    A[-i]=(A[-(i-1)]*2)%(J+1)

if J>1:
    B=[0]*N
    B[0]=1
    for j in range(2,N+1):
        B[-j]=(B[-(j-1)]*2)%(J-1)


H=[0]*N

if J==0:
    Q=R=0
else:
    Q,R=divmod(Y,J)

for i in range(N):
    if X[i]=="0":
        S=(R+A[i]-Q)%(J+1)
    else:
        if J==1:
            continue
        S=(R-B[i]+Q)%(J-1)
        
    I=1
    while S>0:
        S=S%bin(S).count("1")
        I+=1
    H[i]=I

print("\n".join(map(str,H)))

Submission status: Wrong Answer

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


N = int(input())
A = int(input().rstrip(), 2)


def f(n):
    ans = 0
    while n != 0:
        pc = bin(n).count('1')
        n = n % pc
        ans += 1
    return ans


AL = []
for n in range(N):
    AL.append(f(n))

# print(AL)

for i in range(N)[::-1]:
    a = A ^ (1 << i)
    n = bin(a).count('1')
    # print(bin(a), n)
    print(AL[n-1]+1)

Submission status: Wrong Answer

Solution code:
## 最初のmodをどうにか高速にやりたい → modの性質を使う
## xiのpopcount（1の数）はxのpopcount+1または-1
n=int(input())
x_str=input()
x_popcount=x_str.count('1')
dp=[0]*(x_popcount+1)
for i in range(1,x_popcount+1):
    popcount=format(i,'b').count('1')
    dp[i]=dp[i%popcount]+1
# print(dp)
x=int(x_str,2)
if x_popcount>1:
    pows_minus=[pow(2,i,(x_popcount-1)) for i in range(n)]
    # x_minus=x%(x_popcount-1)
    x_minus=0
    for i in range(n):
        if x_str[i]=='1':
            x_minus+=pows_minus[n-1-i]
pows_plus=[pow(2,i,(x_popcount+1)) for i in range(n)]
# x_plus=x%(x_popcount+1)
x_plus=0
for i in range(n):
    if x_str[i]=='1':
        x_plus+=pows_plus[n-1-i]

for i in range(len(x_str)):
    ## xi=xi mod popcount(x)+-1
    xi=0
    if x_str[i]=='1':
        if x_popcount>1: ## else: xi=0
            xi=(x_minus-pows_minus[n-1-i])%(x_popcount-1)
    else:
        xi=(x_plus+pows_plus[n-1-i])%(x_popcount+1)
    if xi==0:
        print(0)
    else:
        print(dp[xi]+1)