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

_INPUT = """\
23
00110111001011011001110

3
011

"""
sys.stdin = io.StringIO(_INPUT)
####################################################################
import sys
def _p(*_a):
  #return
  _s=" ".join(map(str,_a))
  #print(_s)
  sys.stderr.write(_s+"\n")
####################################################################
def _pa(_aa):
  #return
  for _a in _aa: _p(_a)
####################################################################
N = int(input())
X = input()

from collections import defaultdict
d = defaultdict(int)
dCnt = defaultdict(int)

def popcount(n):
  if d[n] > 0: return d[n]

  rtn = 0
  while n > 0:
    if n % 2 == 1: rtn += 1
    n = n >> 1

  d[n] = rtn
  return d[n]

Z = "1"*N
for n in range(N):
  s = Z[-n-1:]
  a = b = int(s, 2)
  cnt = 0
  while a>0:
    if dCnt[a] > 0:
      cnt += dCnt[a]
      break
    else:
      cnt += 1
      a = a % popcount(a)
      # _p(n, i, x, a)

  dCnt[b] = cnt

for n in range(N)[::-1]:
  i = 1 << n
  x = int(X, 2)
  a = b = x^i
  # _p(n, i, x, a)

  cnt = 0
  while a>0:
    if dCnt[a] > 0:
      cnt += dCnt[a]
      break
    else:
      cnt += 1
      a = a % popcount(a)
      # _p(n, i, x, a)

  dCnt[b] = cnt

  print(cnt)

Submission status: Wrong Answer

Solution code:
import sys
from functools import lru_cache, cmp_to_key
from heapq import merge, heapify, heappop, heappush
# from math import *
from collections import defaultdict as dd, deque, Counter as C
from itertools import combinations as comb, permutations as perm
from bisect import bisect_left as bl, bisect_right as br, bisect
from time import perf_counter
from fractions import Fraction
# import numpy as np
# sys.setrecursionlimit(int(pow(10,6)))

mod = int(pow(10, 9) + 7)
mod2 = 998244353
def data(): return sys.stdin.readline().strip()
def out(*var, end="\n"): sys.stdout.write(' '.join(map(str, var))+end)
def L(): return list(sp())
def sl(): return list(ssp())
def sp(): return map(int, data().split())
def ssp(): return map(str, data().split())
def l1d(n, val=0): return [val for i in range(n)]
def l2d(n, m, val=0): return [l1d(n, val) for j in range(m)]

try:
    sys.stdin = open("input.txt", "r")
    sys.stdout = open("out.txt", "w")
except:
    pass


# @lru_cache(None)

n=L()[0]
X=input()
if X=="0"*n:
    for i in range(n):
        print(1)
    exit()
if X=="1":
    print(0)
    exit()
curr=curr2=1
nao=mnao=0
bit=X.count("1")+1
bit2=X.count("1")-1
if bit==2:
    if X[n-1]=="1":
        for i in range(n):
            if X[i]=="0":
                print(2)
                exit()
            else:
                print(1)
                exit()
    else:
        for i in range(n):
            if i==n-1:
                print(2)
            elif X[i]=="0":
                print(1)
            else:
                print(0)
        exit()

for i in range(n-1,-1,-1):
    if X[i]=="1":
        nao+=curr%bit
        nao%=bit
        mnao+=curr2%bit2
        mnao%=bit2
    curr*=2
    curr%=bit
    curr2*=2
    curr2%=bit2
print(curr,curr2,bit,bit2,nao,mnao)
for  i in range(n):
    FN=0
    if X[i]=="0":
        FN=nao
        ex=pow(2,n-i-1,bit)
        FN+=ex
        FN%=bit
    else:
        FN=mnao
        ex=pow(2,n-i-1,bit2)
        FN-=ex
        FN%=bit2
        if FN<0:
            FN+=bit2
    step=1
    # print(FN)
    while(FN):
        bitcnt=bin(FN).count("1")
        FN%=bitcnt
        step+=1
    print(step)

Submission status: Wrong Answer

Solution code:
import sys
import  math
from heapq import *
import fractions
import bisect
stdin = sys.stdin
     
ns = lambda: stdin.readline().rstrip()
ni = lambda: int(stdin.readline().rstrip())
nm = lambda: map(int, stdin.readline().split())
nl = lambda: list(map(int, stdin.readline().split()))

N=int(input())
X=list(ns())

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

mlist_num_1up=[0]*N
mlist_num_1down=[0]*N
mlist_num_1up[0]=1
mlist_num_1down[0]=1


if(1<num_1):
    for i in range(1,N):
        mlist_num_1up[i]=(mlist_num_1up[i-1]*2)%(num_1+1)
        mlist_num_1down[i]=(mlist_num_1down[i-1]*2)%(num_1-1)
elif(num_1==1):
    for i in range(1,N):
        mlist_num_1up[i]=(mlist_num_1up[i-1]*2)%(num_1+1)

    upmod_ori=0
    for i in range(N):
        if(X[i]=='1'):
            upmod_ori+=mlist_num_1up[i]
    mlist_num_1up.reverse()
    for i in range(N):
        if(X[i]=='1'):
            a=0
            print(a)
        else:
            mod=upmod_ori+mlist_num_1up[i]
            mod%=(num_1+1)
            print(1 if mod==0 else 2)
    sys.exit(0)




mlist_num_1up.reverse()
mlist_num_1down.reverse()

upmod_ori=0
downmod_ori=0
for i in range(N):
    if(X[i]=='1'):
        upmod_ori+=mlist_num_1up[i]
        downmod_ori+=mlist_num_1down[i]


fans=[0]*31
fans[0]=0
fans[1]=1
for i in range(2,31):
    mod=0
    for p in range(7):
        if((i>>p) & 1):
            mod+=1
    fans[i]=fans[i%mod]+1
    
if(num_1==2):
    for i in range(N):
        if(X[i]=='1'):
            print(2)
        else:
            mod=upmod_ori+mlist_num_1up[i]
            mod%=(num_1+1)
            mod1=0
            for p in range(31):
                if((mod>>p) & 1):
                    mod1+=1
            print(fans[mod1]+1)
    sys.exit(0)
for i in range(N):
    if(X[i]=='1'):
        mod=downmod_ori-mlist_num_1down[i]
        mod%=(num_1-1)
    else:
        mod=upmod_ori+mlist_num_1up[i]
        mod%=(num_1+1)
    mod1=0
    for p in range(31):
        if((mod>>p) & 1):
            mod1+=1
    print(fans[mod1]+1)

Submission status: Wrong Answer

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

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
x_pop = popcount(x)
for i in reversed(range(0,n)):
    try:
        if x&(1<<i):
            tmp_pop = x_pop - 1
        else:
            tmp_pop = x_pop + 1
        tmp = (x^(1<<i)) % tmp_pop
        if tmp <= 0:
            print(1)
            continue
        cnt = 2
        tmp2 = tmp % popcount(tmp)
        while tmp2 > 0:
            tmp %= popcount(tmp)
            cnt += 1
            tmp2 %= popcount(tmp2)
        print(cnt)
    except:
        print(0)

Submission status: Wrong Answer

Solution code:
def popcount(x0):
  tmp=x0
  count=0
  while tmp != 0:
    if tmp % 2 == 1:
      count+=1
    tmp=tmp >> 1
  return count

def f(x1):
  c1=0
  tmp1=x1
  while tmp1 != 0:
    tmp1=tmp1 % popcount(tmp1)
    c1+=1
  return c1

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



for i in range(1,n+1):
  str=list(x)
  if str[i-1] == '1':
    str[i-1]='0'
  else:
    str[i-1]='1'
  x="".join(str)
  
  xx=0
  for i in range(n):
    if x[i] == '1':
      xx+=2**(n-i-1)
      
  print(f(xx))

Submission status: Wrong Answer

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

def popcount(x):
    x = x - ((x >> 1) & 0x5555555555555555)
    x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)
    x = (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f # 8bitごと
    x = x + (x >> 8) # 16bitごと
    x = x + (x >> 16) # 32bitごと
    x = x + (x >> 32) # 64bitごと = 全部の合計
    return x & 0x0000007f

def counter(memo, count, X_current, X_one_current):
    if X_current in memo:
        return memo[X_current] + count

    X_prev = X_current

    X_current = X_current % X_one_current
    X_one_current = popcount(X_current)
    count += 1

    if X_current == 0:
        memo[X_prev] = 1
        return count
    else:
        value = counter(memo, count, X_current, X_one_current)
        memo[X_prev] = value
        return value


def solve(N, X):
    X_oct = int(X, 2)
    X_one_count = X.count("1")

    memo = {}
    for i, x in enumerate(X):
        if x == '1':
            X_current = X_oct - 2 ** (N-1-i)
            X_one_current = X_one_count - 1
        elif x == '0':
            X_current = X_oct + 2 ** (N - 1 - i)
            X_one_current = X_one_count + 1

        if X_one_current == 0:
            print(0)
            continue

        count = counter(memo, 0, X_current, X_one_current)
        print(count)

    return

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

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/python3
# -*- coding: utf-8 -*-
def funk(x, temp_count):
    if x in log_dict:
        ans = log_dict[x]
        return ans
    x_temp = x % temp_count
    if x_temp == 0:
        log_dict[x] = 1
        return 1
    temp_count = bin(x_temp).count("1")
    ans = funk(x_temp, temp_count)
    ans += 1
    log_dict[x] = ans
    return ans
n = int(input())
bit = input()
bit_list = list(bit)
count = bit.count("1")
log_dict = {0: 0, 1: 1, 2: 1, 8: 1, 6002382: 2, 3905230: 1, 10: 1, 759502: 2, 6: 1, 1283790: 2, 2070222: 1, 1677006: 2, 1742542: 2, 1775310: 2, 1824462: 2, 1816270: 2, 1803982: 2, 1810126: 2, 1807054: 2, 1807566: 2, 1808334: 2, 1807950: 2, 1808014: 2, 1808110: 2, 1808094: 2, 1808070: 2, 1808074: 2, 1808076: 1, 7: 2, 1808079: 3, 6002190: 2, 3905038: 2, 759310: 1, 1283598: 2, 2070030: 2, 4: 1, 1676814: 2, 1742350: 1, 1775118: 2, 1824270: 2, 1816078: 2, 1803790: 1, 1809934: 2, 1806862: 2, 1807374: 2, 1808142: 2, 1807918: 2, 1807902: 2, 1807878: 2, 1807882: 2, 1807884: 2, 3: 2, 1807887: 3, 6002178: 2, 3905026: 2, 759298: 2, 1283586: 2, 2070018: 2, 1676802: 2, 1742338: 2, 1775106: 2, 1824258: 2, 1816066: 2, 1803778: 2, 1809922: 2, 1806850: 2, 1807362: 2, 1808130: 1, 1808002: 2, 1807938: 2, 1807906: 2, 1807890: 1, 1807872: 1, 5: 2, 1807875: 3, 9: 2, 192069700: 3, 124960836: 1, 24297540: 2, 41074756: 3, 66240580: 2, 53657668: 2, 55754820: 1, 56803396: 2, 58376260: 2, 58114116: 3, 57720900: 3, 57917508: 1, 57819204: 1, 57835588: 2, 57860164: 2, 57856068: 2, 57854020: 2, 57852996: 3, 57852484: 2, 57852228: 3, 57852100: 3, 57851908: 3, 57852004: 2, 57851988: 3, 57851980: 2, 57851968: 2, 57851974: 2, 57851973: 3, 225624132: 2, 242401348: 2, 267567172: 2, 254984260: 3, 257081412: 3, 258129988: 2, 259702852: 2, 259440708: 3, 259047492: 1, 11: 2, 259244100: 3, 259145796: 2, 259162180: 2, 259186756: 2, 259182660: 3, 259180612: 2, 259179588: 3, 259179076: 1, 259178820: 2, 259178692: 2, 259178500: 3, 259178596: 2, 259178580: 3, 259178572: 3, 259178560: 3, 259178566: 2, 259178565: 3, 527614020: 3, 796049476: 2, 930267204: 3, 997376068: 1, 1030930500: 2, 1047707716: 3, 1072873540: 2, 1060290628: 3, 12: 1, 1062387780: 2, 1063436356: 2, 1065009220: 2, 1064747076: 2, 1064353860: 3, 1064550468: 3, 1064452164: 3, 1064468548: 1, 1064493124: 2, 1064489028: 3, 1064486980: 2, 1064485956: 2, 1064485444: 2, 1064485188: 3, 1064485060: 2, 1064484868: 3, 1064484964: 2, 1064484948: 3, 1064484940: 2, 1064484928: 1, 1064484934: 2, 1064484933: 3}



for i in range(n):
    temp_count = count
    if bit[i] == "1":
        temp_count -= 1
        bit_list[i] = "0"
        x_bit = ''.join(bit_list)
        bit_list[i] = "1"
    else:
        temp_count += 1
        bit_list[i] = "1"
        x_bit = ''.join(bit_list)
        bit_list[i] = "0"
    x = int(x_bit, 2)
    ans = funk(x, temp_count)
    # print(ans)
print(log_dict)

Submission status: Wrong Answer

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

# popcount(n) -> 1 - N の値
# 0でないとpopcount(n) = 0 にならない
# n % popcunct(n) -> N - 1の値
# N - 1までの値がどうなるかしらべておけばOK
# 011 : 3
# 111 : 7 -> 7 % 3 = 1 ->
# 001 : 1
# 010 : 2


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


P = [-1] * (N + 1)
P[0] = 0
for i in range(1, len(P)):
    # print(f'{i=}')
    # print(f'{P=}')
    if P[i] != -1:
        continue
    n = i
    cnt = 0
    while True:
        cnt += 1
        n = n % popcount(i)
        # print(f'{n=}')
        if P[n] != -1:
            cnt += P[n]
            break
        if n == 0:
            break
        # exit()
    P[i] = cnt
# print(f'{P=}')

for i in range(len(X)):
    s1 = X[i]
    if s1 == '0':
        X[i] = '1'
        v = 0
        for j in range(N - 1, -1, -1):
            # print('j', j)
            v += int(X[j]) * (2**j)
        # print('v', v)
        if v > N:
            # print('v', v)
            v = v % popcount(v)
            # print('v', v)
            print(P[v] + 1)
        else:
            print(P[v])
        X[i] = '0'
    else:
        X[i] = '0'
        v = 0
        for j in range(N - 1, -1, -1):
            # print('j', j)
            v += int(X[j]) * (2**j)
        # print('v', v)
        if v > N:
            v = popcount(v)
            print(P[v] + 1)
        else:
            print(P[v])
        X[i] = '1'

Submission status: Wrong Answer

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

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

data = []
for d in X:
  data.append(d)

for i in range(N):
  temp = []
  temp = data
  ans = 0
  #i番目のビット反転
  if temp[i] == "1":
    temp[i] = "0"
  else:
    temp[i] = "1"
  print(data)
  
  #10進数に変換(str -> int)
  bin_n = str("".join(map(str, temp)))
  int_n = int(bin_n,2)
  #print("int_n = " + str(int_n))

  while int_n > 0:
    ans += 1
    j = popcount(int_n)
    int_n = int_n % j

  print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
two_num = list(map(int, list(input())))
# N = 3
# two_num = [0,1,1]
ans = [[0]*N]
import copy

for i in range(N):
    bin_list = copy.deepcopy(two_num)
    if bin_list[i] == 0:
        bin_list[i] = 1
    else:
        bin_list[i] = 0
    if bin_list.count(1):
        num=1
        ans = 0
        while num:
            ans+=1
            num = 0
            for i, j in enumerate(reversed(bin_list)):
                num += (2**i) * j
            count = bin_list.count(1)
            num = num % count
            bin_list = list(map(int, list(format(num, 'b'))))
        print(ans)
    else:
        print(1)

Submission status: Wrong Answer

Solution code:
import collections

n = int(input())
x = input()
dic = collections.defaultdict(int)
#dic_count = collections.defaultdict(int)
one_count = x.count("1")

ls_p = []
ls_m = []

for i in range(1,n+1):
    cnt = 0
    nm = bin(i).count("1")
    tmp = i
    while tmp:
        tmp %= nm
        nm = bin(tmp).count("1")
        cnt += 1
    dic[i] = cnt

if one_count == 1:
    for i in range(n):
        if i == 0:
            ls_p.append(2 ** i % (one_count+1))
        else:
            ls_p.append(ls_p[-1] * 2 % (one_count+1))
    ls_p.reverse()
    cnt = 0
    num_p = 0
    for i in range(n):
        if x[i]:
            num_p += ls_p[i]
            num_p %= (one_count+1)
    for i in range(n):
        num_p_copied = num_p
        if x[i] == "1":
            print(0)
        else:
            num_p_copied += ls_p[i]
            num_p_copied %= (one_count+1)
            if num_p_copied != 0:
                print(dic[num_p_copied]+1)
            else:
                print(1)
else:
    for i in range(n):
        if i == 0:
            ls_p.append(2 ** i % (one_count+1))
            ls_m.append(2 ** i % (one_count-1))
        else:
            ls_p.append(ls_p[-1] * 2 % (one_count+1))
            ls_m.append(ls_m[-1] * 2 % (one_count-1))
    ls_p.reverse()
    ls_m.reverse()
    num_p = 0
    num_m = 0
    for i in range(n):
        if x[i]:
            num_p += ls_p[i]
            num_p %= (one_count+1)
            num_m += ls_m[i]
            num_m %= (one_count-1)
    for i in range(n):
        num_p_copied = num_p
        num_m_copied = num_m
        if x[i] == "1":
            num_m_copied -= ls_m[i]
            num_m_copied %= (one_count-1)
            if num_m_copied != 0:
                print(dic[num_m_copied]+1)
            else:
                print(1)
        else:
            num_p_copied += ls_p[i]
            num_p_copied %= (one_count+1)
            if num_p_copied != 0:
                print(dic[num_p_copied]+1)
            else:
                print(1)

Submission status: Wrong Answer

Solution code:
n = int(input())

def f(num,nn):#bit反転関数
  return num ^ (1 << nn)

def popcnt(x):#1の数数える
    return bin(x).count("1")

def g(y):#割れる回数数える
  cnt=0
  while y!=0:
    y=y%popcnt(y)
    cnt+=1
  return cnt

for i in range(n)[::-1]:
  print(g(f(n,i)))

Submission status: Wrong Answer

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip()

n= int(input())
a=list(input())

v=a.count('1')

ans=[0]*n
A=[0]*n
# n以下の残り回数を記録
for i in range(v+1):
    x=i
    cnt=0


# 各桁をv＋１で割ったあまり
q = [0]*n
# 各桁をv-1で割ったあまり
r = [0]*n
for i in range(n):
    if a[i]=='1':
        if v!=0:
            q[i] = pow(2, n-i-1) % (v + 1)
        if v!=1:
            r[i] += pow(2, n-i-1) % (v - 1)
qq=sum(q)
rr=sum(r)

for i in range(n):
    if a[i]=='1':
        if v!=1:
            z = rr - pow(2,n-i-1)%(v-1)
            cnt = z % (v - 1)
            A[i] = 1 + ans[cnt]
    else:
        z=qq+pow(2,n-i-1)%(v+1)
        cnt=z%(v+1)
        A[i]=1+ans[cnt]

for i in A:
    print(i)

Submission status: Wrong Answer

Solution code:
def get_popcount(n):
    ret = 0
    while n > 0:
        if n & 1 == 1:
            ret += 1
        n >>= 1
    return ret


def main():
    N = int(input())
    X = input()
    ans = [0] * N
    # (1) 最初の1ステップ(n <- n % popconut(n))を行う
    X_popcount = len([x for x in X if x == '1'])
    popcounts = [X_popcount] * N
    for i, x in enumerate(X):
        if x == '1':
            popcounts[i] -= 1
        else:
            popcounts[i] += 1
    # X % popcount(X_i)を計算 (popcount(X_i)は2パターン)
    X_nexts = [0, 0]  # [X % (popcount(X) - 1), X % (popcount(X) + 1)]
    pows = [1, 1]
    for x in X[::-1]:
        if x == '1':
            if X_popcount - 1 > 0:
                X_nexts[0] += pows[0]
                X_nexts[0] %= X_popcount - 1
            X_nexts[1] += pows[1]
            X_nexts[1] %= X_popcount + 1
        if X_popcount - 1 > 0:
            pows[0] *= 2
            pows[0] %= X_popcount - 1
        pows[1] *= 2
        pows[1] %= X_popcount + 1
    # X % popcount(X_i) から余分な要素を差し引いて X_i % popcount(X_i) を求める
    xs = [0] * N
    pows = [1, 1]
    for j, x in enumerate(X[::-1]):
        i = N - 1 - j
        if x == '1' and X_popcount - 1 > 0:
            xs[i] = X_nexts[0] - pows[0]
            xs[i] %= X_popcount - 1
            ans[i] += 1
        else:
            xs[i] = X_nexts[1] - pows[1]
            xs[i] %= X_popcount + 1
            ans[i] += 1
        if X_popcount - 1 > 0:
            pows[0] *= 2
            pows[0] %= X_popcount - 1
        pows[1] *= 2
        pows[1] %= X_popcount + 1
    # (2) 以降繰り返し(popcounts, xsを利用)
    while sum(xs) > 0:
        for i, x in enumerate(xs):
            if x == 0:
                continue
            xs[i] = x % get_popcount(x)
            ans[i] += 1
    # 答え
    for a in ans:
        print(a)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import itertools
import decimal
import math
import collections
import sys
#input = sys.stdin.readline
import copy

# S=(input())
# N=int(input())
# N,K=map(int,input().split())
# ListA=list(map(int,input().split()))
# ListA.sort()#reverse=True)

def popcount(x):
    '''xの立っているビット数をカウントする関数
    (xは64bit整数)'''

    # 2bitごとの組に分け、立っているビット数を2bitで表現する
    x = x - ((x >> 1) & 0x5555555555555555)

    # 4bit整数に 上位2bit + 下位2bit を計算した値を入れる
    x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)

    x = (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f # 8bitごと
    x = x + (x >> 8) # 16bitごと
    x = x + (x >> 16) # 32bitごと
    x = x + (x >> 32) # 64bitごと = 全部の合計
    return x & 0x0000007f

def resolve():
    
    N=int(input())
    X=(input())
    #N=200000
    #X="1"*200000

    cnt=0
    for i in range(N):
        tmprev='1'
        if(X[i]=='1'):
            tmprev='0'
        if(i==0):
            tmp=tmprev+X[i+1:]    
        elif(i==N):
            tmp=X[:i]+tmprev    
        else:
            tmp=X[:i]+tmprev+X[i+1:]

        if(i!=0 and N-i>18):
            print(cnt)
            continue
            
        orgpop=tmp.count("1")
        orgpop2=1
        shift=0
        while(True):
            orgpop2*=2
            shift+=1
            if(orgpop2>orgpop):
                break

        #tmp=tmp[N-shift:]
        
        Xi=int(tmp,2)
        
        cnt=0
        first=True
        while True:
            if(Xi==0):
                print(cnt)
                break
            if(first):
                pop=orgpop
                first=False
            else:
                pop=popcount(Xi)
            Xi=Xi%pop
            cnt+=1




resolve()

Submission status: Wrong Answer

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

xre = x[::-1]

cou = x.count('1')

if cou == 0:
    for _ in range(n):
        print(1)
    exit()

if cou == 1:
    for i in range(n):
        if i == n and x[i] == '0':
            print(2)
        elif  x[i] == '0' and x[n-1] == '1':
            print(2)
        elif  x[i] == '0' and x[n-1] == '0':
            print(1)
        else:
            print(0)
    exit()

basepl = int(x, 2) % (cou+1)
basemi = int(x, 2) % (cou-1)

li = [0]*n
pl = 1
mi = 1


for i in range(n):
    if xre[i] == '0':
        li[i] = (basepl + pl)  % (cou+1)
    else:
        li[i] = (basemi - mi)  % (cou-1)
    mi = (mi * 2) % (cou-1)
    pl = (pl * 2) % (cou+1)

def f(n):
    m = n
    k = 1
    while m > 0:
        co = str(bin(m)).count('1')
        m = m % co
        k +=1
    return k


for x in li[::-1]:
    print(f(x))

Submission status: Wrong Answer

Solution code:
N = int(input())
X = int(input(),2)
count = 0
for i in range(N):
    T = X
    T = T ^ (1<<N-1-i)
    while True:
        if T == 0:
            break
        T = T % bin(T).count('1')
        count += 1
        if T == 0:
            print(count)
            break
    count = 0

Submission status: Wrong Answer

Solution code:
save_list = [idx for idx in range(200010)]

def cal_nums(number, flag=0):
    if number == 0:
        return 0
    if number <= 200000 and flag==1:
        return number % save_list[number]
    cp = number
    cnt = 0
    pos = 0
    # print(num_one)
    while cp != 0:
        cnt += cp % 2
        cp //= 2
    # print(cnt)
    
    return number % cnt

def func(number, flag=0):
    # print(num_one)
    if number == 0:
        return 0
    cnt = 0
    tmp = number
    while(1):
        cnt += 1
        tmp = cal_nums(tmp, flag)
        if tmp == 0:
            break
    return cnt

# print('ok')
for idx in range(1, 200000):
    # print('!')
    save_list[idx] = func(idx)
    # print(save_list[idx])
    # print('??')
    # print(save_list[idx])

# print('ok')

n = int(input())
string = input()
length = len(string)
tmp = 0
for i in range(length):
    tmp *= 2
    if string[i] == '1':
        tmp += 1

cnt_0 = 0
cnt_1 = 0

for idx in range(length):
    if string[idx] == '0':
        cnt_0 += 1
    else:
        cnt_1 += 1

# print('ok')
for idx in range(length):
    if string[idx] == '0':
        print(tmp+(1<<(length-idx-1)))
        print(func(tmp+(1<<(length-idx-1)), 1))
        # print(tmp+(1<<(length-idx-1)))
    else:
        print(tmp+(1<<(length-idx-1)))
        print(func(tmp-(1<<(length-idx-1)), 1))
        # print(tmp-(1<<(length-idx-1)))

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
n = int(input())
x = input()
cnt = x.count("1")
x_cnt_plus = 0
x_cnt_minus = 0
for i in range(n):
    if x[i] == "1":
        x_cnt_plus += pow(2, n - i - 1, cnt + 1)
        x_cnt_plus %= cnt + 1
    else:
        if cnt > 1:
            x_cnt_minus += pow(2, n - i - 1, cnt - 1)
            x_cnt_minus %= cnt - 1
for i in range(n):  # 上からi 桁目に注意
    if x[i] == "0":
        f = x_cnt_plus + pow(2, n - i - 1, cnt + 1)
        f %= cnt + 1
    else:
        if cnt == 1:
            print(0)
            continue
        f = x_cnt_minus - pow(2, n - i - 1, cnt - 1)
        f %= cnt - 1
    ans = 1
    while f != 0:
        cnt_f_1 = 0
        k = f
        while k:
            if k % 2:
                cnt_f_1 += 1
            k //= 2
        f = f % cnt_f_1
        ans += 1
    print(ans)
"""
step1; 1を数える cnt_1 
step2 : 全体の計算をする cnt1 + 1 とcnt1 -1 それぞれ
step3 : それぞれの桁に対して0 なら cnt+ 1 を適用 + 2**k mod cnt + 1
            1ならcnt - 1　を適用 - 2**k mod (cnt-1)
step4 : その中でf(x)を0になるまで計算
"""

Submission status: Wrong Answer

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

def main():
    N = int(input())
    X = [None] * N
    l = list(input())
    Xc = 0
    for i in range(N):
        X[i] = int(l[i])
        Xc += X[i]
    if Xc == 0:
        print(0)
        exit()
    elif Xc == 1:
        print(1)
        exit()

    ans1 = 0
    ans2 = 0
    for j in range(N):
        if X[j]==1:
            ans1 += pow(2,N-1-j,Xc+1)
            ans1 %= Xc+1
            ans2 += pow(2,N-1-j,Xc-1)
            ans2 %= Xc-1

    for i in range(N):
        if X[i]==0:# 0->1
            ans = (ans1 + pow(2,N-1-i,Xc+1)) % (Xc+1)
        else:# 1-> 0
            ans = (ans2 - pow(2,N-1-i,Xc-1)) % (Xc-1)
        count = 1
        while ans > 0:
            tmp = str(bin(ans)).count('1')
            ans %= tmp
            count += 1
        print(count)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
from functools import lru_cache

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

@lru_cache(maxsize=None)
def popctmod(n):
  return n % bin(n).count('1')

memo = {}
for i in range(N):
  if X[i]=='1':
    bitStr = X[:i] + '0' + X[i+1:]
  else:
    bitStr = X[:i] + '1' + X[i+1:]
  num = int(bitStr, 2)
  tempnum = num
  if num in memo:
    print(memo[num])
    continue
  res = 0
  while num!=0:
    num = popctmod(num)
    res += 1
  memo[num] = res
  print(res)

Submission status: Wrong Answer

Solution code:
def popcount(u):
    t = bin(u)
    h = t.count("1")
    return u % h 
    
pri = [-1 for i in range(2*(10**5) + 1)]
pri[0] = 0
for i in range(1,2*(10**5)+1):
    if pri[i] == -1:
        now =  popcount(i)
        pri[i] = pri[now] + 1
    
n = int(input())
x = list(input())
c = x.count("1") + 1
d = c - 2
if d == -1:
    for i in range(n):
        print(1)
    exit()
elif d == 0:
    p = x.index("1")
    if p == n-1:
        for i in range(n-1):
            print(2)
        print(0)
        exit()
    elif p != n-1:
        for i in range(n):
            if i != p:
                print(1)
            elif i == p:
                print(0)
        exit()
    
    

amaric = [1 % c]
amarid = [1 % d]
for i in range(n-1):
    amaric.append((amaric[-1]*2)%c)
    amarid.append((amarid[-1]*2)%d)

motoc = 0
motod = 0
for i in range(n):
    if x[i] == "1":
        motoc += amaric[n-1-i]
        motod += amarid[n-1-i]

for i in range(n):
    if x[i] == "0":
        op = motoc
        op += amaric[n-1-i]
        op %= c
    elif x[i] == "1":
        op = motod
        op -= amarid[n-1-i]
        op %= d
    print(pri[op]+1)

Submission status: Wrong Answer

Solution code:
import sys
readline = sys.stdin.buffer.readline
def even(n): return 1 if n%2==0 else 0

n = int(readline())
lst1 = list(readline().rstrip().decode('utf-8'))


res = lst1.copy()
res = "".join(res)
ct = res.count("1")
res = int(res,2)
if ct == 0:
    for i in range(n):
        print(1)
    exit()
if ct == 1:
    amari_of_m = -1
else:
    amari_of_m = res%(ct-1)
amari_of_p = res%(ct+1)

def pow(n,p,mod): #繰り返し二乗法(nのp乗)
    res = 1
    while p > 0:
        if p % 2 == 0:
            n = n ** 2 % mod
            p //= 2
        else:
            res = res * n % mod
            p -= 1
    return res % mod

def func(res):
    ans = 1
    while True:
        ct = 0
        for i in range(len(bin(res))):
            if res>>i&1:
                ct += 1
        if res%ct == 0:
            print(ans+1)
            return
        else:
            res %= ct
            ans += 1

for i in range(n):
    if lst1[i] == "1" and amari_of_m == -1:
        print(1)
        continue
    else:
        resres = pow(2,n-i-1,ct-1) if lst1[i] == "1" else pow(2,n-i-1,ct+1)
    if lst1[i] == "1":
        resres = amari_of_m - resres
        resres %= ct-1
    else:
        resres = amari_of_p + resres
        resres %= ct+1
    if not resres:
        print(1)
    else:
        func(resres)

Submission status: Wrong Answer

Solution code:
n=int(input())
s=input()
cc=s.count("1")
flg=[False for i in range(n)]
for i in range(n):
    if s[i]=="1":
        flg[i]=True
xx=int(s,2)
for i in range(n):
    ans=0
    x=xx^(1<<n-i-1)
    if flg[i]==True:
        c=cc-1
    if flg[i]==False:
        c=cc+1
    while x>0:
        x%=c
        ans+=1
        if x==0:
            print(ans)
            break
        two=bin(x)
        c=two.count("1")

Submission status: Wrong Answer

Solution code:
n = int(input())
_x = list(reversed(list(input())))
x = 0
for i in range(n-1, -1, -1):
    x += int(_x[i]) * (2**(n-i-1))

def popcount(n):
    c = 0
    while(n != 0):
        n = n%str(bin(n)[2:]).count('1')
        c += 1
    return c

for i in range(n):
    if ('{:' + str(n) + 'b}').format(x)[i] == '1':
        print(popcount(int(x - 2**(n-i-1))))
    else:
        print(popcount(int(x + 2**(n-i-1))))

Submission status: Wrong Answer

Solution code:
import math
# from collections import defaultdict
import time
def steps(n,p):
  c = 0
  while n:
    c += 1
    n = n%p
    p = bin(n).count('1')
  return c

n = 200000
x = "1"*n
# n = int(input())
# x = input()
incs = [1]
decs = [1]
p = x.count('1')
for i in range(1,n):
  incs.append((incs[-1]*2)%(p+1))
  decs.append((decs[-1]*2)%(p-1))
num = int(x,2)
inc = num%(p+1)
dec = num%(p-1)
start = time.time()
k = -1
for i in range(n):
  cp = p
  if x[i] == '0':
    cp += 1
    new = (inc+incs[k])%cp
  else:
    cp -= 1
    new = (dec-decs[k])%cp
  k -= 1
  ans = steps(new,cp)
  if ans==0:
    ans=1
  print(ans)
  # steps(new,cp)
#print(time.time()-start)