Problem:


Score : 400 points

Problem Statement

Let \mathrm{popcount}(n) be the number of 1s in the binary representation of n.
For example, \mathrm{popcount}(3) = 2, \mathrm{popcount}(7) = 3, and \mathrm{popcount}(0) = 0.

Let f(n) be the number of times the following operation will be done when we repeat it until n becomes 0: "replace n with the remainder when n is divided by \mathrm{popcount}(n)." (It can be proved that, under the constraints of this problem, n always becomes 0 after a finite number of operations.)

For example, when n=7, it becomes 0 after two operations, as follows:

\mathrm{popcount}(7)=3, so we divide 7 by 3 and replace it with the remainder, 1.

\mathrm{popcount}(1)=1, so we divide 1 by 1 and replace it with the remainder, 0.

You are given an integer X with N digits in binary.
For each integer i such that 1 \leq i \leq N, let X_i be what X becomes when the i-th bit from the top is inverted.
Find f(X_1), f(X_2), \ldots, f(X_N).

Constraints

1 \leq N \leq 2 \times 10^5

X is an integer with N digits in binary, possibly with leading zeros.

Input

Input is given from Standard Input in the following format:

N
X

Output

Print N lines. The i-th line should contain the value f(X_i).

Sample Input 1

3
011

Sample Output 1

2
1
1

X_1 = 7, which will change as follows: 7 \rightarrow 1 \rightarrow 0. Thus, f(7) = 2.

X_2 = 1, which will change as follows: 1 \rightarrow 0. Thus, f(1) = 1.

X_3 = 2, which will change as follows: 2 \rightarrow 0. Thus, f(2) = 1.

Sample Input 2

23
00110111001011011001110

Sample Output 2

2
1
2
2
1
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
1
3



Sample input:
3
011


Sample output:
2
1
1

Submission status: Accepted

Solution code:
import sys
import numpy as np
import numba
from numba import njit
i8 = numba.int64

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N = int(readline())
X = np.array(list(read().rstrip()), np.int64) - ord('0')

@njit((i8, ), cache=True)
def popcount(n):
    ret = 0
    while n:
        ret += n & 1
        n >>= 1
    return ret


@njit((i8, ), cache=True)
def f(n):
    t = 0
    while n:
        t += 1
        n %= popcount(n)
    return t

@njit(cache=True)
def main(X):

    popX = X.sum()
    MOD1 = popX + 1
    MOD2 = popX - 1
    if popX == 1:
        MOD2 = 1
    pow1 = np.ones_like(X)
    pow2 = np.ones_like(X)
    for n in range(1, len(X)):
        pow1[n] = 2 * pow1[n - 1] % MOD1
        pow2[n] = 2 * pow2[n - 1] % MOD2

    X1, X2 = 0, 0
    for x in X:
        X1 = (2 * X1 + x) % MOD1
        X2 = (2 * X2 + x) % MOD2

    ans = np.empty(N, np.int64)
    for i in range(N):
        x = X[N - 1 - i]
        if x == 0:
            nxt = (X1 + pow1[i]) % (popX + 1)
            ans[i] = 1 + f(nxt)
        elif x == 1:
            if popX == 1:
                ans[i] = 0
            else:
                nxt = (X2 - pow2[i]) % (popX - 1)
                ans[i] = 1 + f(nxt)
    return ans[::-1]

ans = main(X)
print('\n'.join(map(str, ans.tolist())))

Submission status: Accepted

Solution code:
def find(x,ones):
    if ones == 0:
        return 0
    total = 0
    n = len(x)
    for i in range(n):
        total += int(x[i])*pow(2,n-i-1,ones)
        total %= ones

    return total

def solve(x,mod):
    x %= mod
    moves = 1
    while x != 0:
        x = x%(bin(x)[2:].count('1'))
        moves += 1

    return moves

def main():
    n = int(input())
    x = input()
    ones = x.count('1')
    less = find(x,ones-1)
    more = find(x,ones+1)
    for i in range(n):
        if x[i] == '0':
            print(solve(more+pow(2,n-i-1,ones+1),ones+1))
        else:
            if ones-1 == 0:
                print(0)
            else:
                print(solve(less-pow(2,n-i-1,ones-1),ones-1))


main()

Submission status: Accepted

Solution code:
from functools import lru_cache


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


n = int(input())
x = input()
d = x.count('1')
y = int(x, base=2)
y0 = y % (d + 1)
y1 = y % (d - 1) if d > 1 else 0
buf = []

for i in range(n):
    if x[i] == '0':
        m = d + 1
        z = (y0 + pow(2, n - i - 1, m)) % m
        # print(0, y0, pow(2, n - i - 1, m))
    else:
        m = d - 1
        if m == 0:
            buf.append(0)
            continue
        z = (y1 - pow(2, n - i - 1, m)) % m
        # print(1, y1, pow(2, n - i - 1, m))
    # print(i, z)
    buf.append(f(z) + 1)

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

Submission status: Accepted

Solution code:
def popcount(i): # i < 2^32
    i = i - ((i >> 1) & 0x55555555)
    i = (i & 0x33333333) + ((i >> 2) & 0x33333333)
    return (((i + (i >> 4) & 0xF0F0F0F) * 0x1010101) & 0xffffffff) >> 24



# coding: utf-8
# Your code here!
import sys
read = sys.stdin.read
readline = sys.stdin.readline

#n,k,*a = map(int,read().split())
n, = map(int,readline().split())
x = input()

p = x.count("1")
p0 = p-1
p1 = p+1

if p0 != 0:
    r0 = int(x,2)%p0
else:
    r0 = 0
r1 = int(x,2)%p1


#print(f"r0={r0},r1={r1}","p",p0,p1)


for i in range(n):
    if x[i]=="0":
        v = (r1 + pow(2,n-i-1,p1))%p1
    else:
        if p0 == 0:
            print(0)
            continue
        v = (r0 - pow(2,n-i-1,p0))%p0
        
    ans = 1
    while v:
        #print(v,i)
        ans += 1
        v %= popcount(v)
    print(ans)

Submission status: Accepted

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

popcnt = X.count('1')

if popcnt == 0:
    for _ in range(N):
        print(1)
    exit()

pop1 = popcnt + 1
pop2 = popcnt - 1

x_int = int(X, base = 2)
x_mod_pop1 = x_int % pop1
if pop2 != 0:
    x_mod_pop2 = x_int % pop2

for i, c in enumerate(X):
    if c == '1':
        if popcnt == 1:
            print(0)
        else:
            mod = x_mod_pop2 - pow(2, N-i-1, pop2) 
            mod %= pop2
            c = 1
            while mod:
                mod %= format(mod, 'b').count('1')
                c += 1
            print(c)
    else:
        mod = x_mod_pop1 + pow(2, N-i-1, pop1) 
        mod %= pop1
        c = 1
        while mod:
            mod %= format(mod, 'b').count('1')
            c += 1
        print(c)

Submission status: Accepted

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

original_pop_count = x.count('1')
one_pop_count = original_pop_count - 1
zero_pop_count = original_pop_count + 1

one_mod = 0
zero_mod = 0
for b in x:
    if one_pop_count != 0:
        one_mod = (one_mod * 2 + int(b)) % one_pop_count
    zero_mod = (zero_mod * 2 + int(b)) % zero_pop_count


#f の前計算

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

#pow2 の前計算
one_pow2 = [1] * 220000
zero_pow2 = [1] * 220000
for i in range(1, 220000):
    if one_pop_count != 0:
        one_pow2[i] = one_pow2[i-1] * 2 % one_pop_count
    zero_pow2[i] = zero_pow2[i-1] * 2 % zero_pop_count
    
# n-1, n-2, ,, 0
for i in range(n-1, -1, -1):
    if x[n-1-i] == '1':
        if one_pop_count != 0:
            nxt = one_mod
            nxt -= one_pow2[i]
            nxt %= one_pop_count
            print(f[nxt] + 1)
        else:
            print(0)
    if x[n-1-i] == '0':
        nxt = zero_mod
        nxt += zero_pow2[i]
        nxt %= zero_pop_count
        print(f[nxt] + 1)

Submission status: Accepted

Solution code:
mod = 1000000007
eps = 10**-9


def main():
    import sys
    input = sys.stdin.readline

    N = int(input())
    X = input().rstrip('\n')

    M = X.count("1")
    flg = 0
    if M == 1:
        flg = 1
    x_major = 0
    x_minor = 0
    for i in range(N):
        add = int(X[i])
        x_major = (x_major * 2 + add)%(M+1)
        if flg == 0:
            x_minor = (x_minor * 2 + add)%(M-1)
    for i in range(N):
        if X[i] == "1":
            if flg:
                print(0)
                continue
            val = (x_minor - pow(2, N-i-1, M-1)) % (M-1)
        else:
            val = (x_major + pow(2, N-i-1, M+1)) % (M + 1)
        cnt = 1
        while val:
            val = val % bin(val).count("1")
            cnt += 1
        print(cnt)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

N = int(input())
S = input().rstrip()

num = S.count('1')

n1 = num + 1
n2 = num - 1

def count(m):
    ret = 1
    while m != 0:
        k = bin(m).count("1")
        m %= k
        ret += 1
    return ret


if n2 != 0:
    start1 = 0
    start2 = 0
    pow1 = [1]
    pow2 = [1]
    for i in range(N):
        s = int(S[-1-i])
        start1 = (start1 + pow1[-1] * s) % n1
        start2 = (start2 + pow2[-1] * s) % n2
        pow1.append(pow1[-1] * 2 % n1)
        pow2.append(pow2[-1] * 2 % n2)


    ans = []
    for i in range(N):
        s = int(S[i])
        if s == 0:
            l = (start1 + pow1[-i-2]) % n1
            ans.append(count(l))
        else:
            l = (start2 - pow2[-i-2]) % n2
            ans.append(count(l))

    print(*ans, sep="\n")
else:
    start1 = 0
    pow1 = [1]
    for i in range(N):
        s = int(S[-1-i])
        start1 = (start1 + pow1[-1] * s) % n1
        pow1.append(pow1[-1] * 2 % n1)

        


    ans = []
    for i in range(N):
        s = int(S[i])
        if s == 0:
            l = (start1 + pow1[-i-2]) % n1
            ans.append(count(l))
        else:
            ans.append(0)

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

Submission status: Accepted

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

def ans(x):
    ANS=0
    while x:
        x%=bin(x).count("1")
        ANS+=1
    return ANS

LEN=int(input())
S=input().strip()
ONE=S.count("1")

ONEP=ONE+1
ONEM=ONE-1

PANS=0
MANS=0
for i in range(LEN):
    if S[i]=="1":
        PANS+=pow(2,LEN-1-i,ONEP)
        if ONEM<=0:
            continue
        MANS+=pow(2,LEN-1-i,ONEM)

for i in range(LEN):
    if S[i]=="0":
        print(ans((PANS+pow(2,LEN-1-i,ONEP))%ONEP)+1)
    else:
        if ONEM==0:
            print(0)
        else:
            print(ans((MANS-pow(2,LEN-1-i,ONEM))%ONEM)+1)

Submission status: Accepted

Solution code:
#!/usr/bin/env python
#pyrival orz
import os
import sys
from io import BytesIO, IOBase

"""
    for _ in range(int(input())):
    n,m=map(int,input().split())
    n=int(input())
    a = [int(x) for x in input().split()]
"""

def main():
    from functools import lru_cache

    @lru_cache(None)
    def solve(n):
        if n==0:
            return 0
        c=bin(n).count('1')
        return 1+solve(n%c)
    n=int(input())
    s=input()

    ct=s.count('1')

    mod=1
    if ct>1:
        mod*=ct-1
    mod*=ct+1

    p,g=1,0
    for x in s:
        g*=2
        if x=='1':
            g+=1
        g%=mod

    s=s[::-1]
    ans=[0]*len(s)
    for i,x in enumerate(s):
        p%=mod
        if x=='1':
            if ct==1:
                p*=2
                continue
            else:
                ans[i]=1+solve((g-p)%(ct-1))
        else:
            ans[i]=1+solve((g+p)%(ct+1))
        p*=2
    ans=ans[::-1]
    for x in ans:
        print(x)
# region fastio

BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")

# endregion

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def solve(X):
    cnt = X.count('1')

    memo = [0]*(cnt+2)

    for v in range(1,cnt+2):
        memo[v] = memo[v%(bin(v).count('1'))]+1

    res = [None]*len(X)
    if cnt > 1:
        m = int(X,2)%(cnt-1)

        r = 1
        for i,c in enumerate(reversed(X)):
            if c == '1':
                res[i] = memo[(m-r)%(cnt-1)]+1
            r *= 2
            r %= cnt-1
    else:
        for i,c in enumerate(reversed(X)):
            if c == '1':
                res[i] = 0

    m = int(X,2)%(cnt+1)

    r = 1
    for i,c in enumerate(reversed(X)):
        if c == '0':
            res[i] = memo[(m+r)%(cnt+1)]+1
        r *= 2
        r %= cnt+1

    return '\n'.join(map(str,reversed(res)))



if __name__ == '__main__':
    N = int(input())
    X = input()
    print(solve(X))

Submission status: Accepted

Solution code:
def popcount(n):
    return str(bin(n)).count('1')
def f(n):
    if n==0:
        return 0
    else:
        return f(n%popcount(n))+1
N=int(input())
X=input()
K=X.count("1")
#k桁目がone,zeroのとき
ONE=0#K-1
ZERO=0#K+1
tmp1=1
tmp0=1
for i in range(N):
    if X[-i-1]=="1":
        if K>1:
            ONE+=tmp1
            ONE%=(K-1)
        ZERO+=tmp0
        ZERO%=(K+1)
    if K>1:
        tmp1*=2
        tmp1%=(K-1)
    tmp0*=2
    tmp0%=(K+1)
for i in range(N):
    nextnumber=-1
    if X[i]=="1":
        if K==1:
            print(0)
            continue
        else:
            nextnumber=(ONE-pow(2,N-i-1,K-1))%(K-1)
    else:
        nextnumber=(ZERO+pow(2,N-i-1,K+1))%(K+1)
    print(f(nextnumber)+1)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
#from math import gcd
import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache

#############
# Constants #
#############

MOD = 10**9+7
INF = float('inf')
AZ = "abcdefghijklmnopqrstuvwxyz"

#############
# Functions #
#############

######INPUT######
def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]

######OUTPUT######
def P(arg): print(arg); return
def Y(): print("Yes"); return
def N(): print("No"); return
def E(): exit()
def PE(arg): print(arg); exit()
def YE(): print("Yes"); exit()
def NE(): print("No"); exit()

#####Shorten#####
def DD(arg): return defaultdict(arg)

#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n): return kaijo_memo[n]
  if(len(kaijo_memo) == 0): kaijo_memo.append(1)
  while(len(kaijo_memo) <= n): kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n): return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0): gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n): gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if n == r: return 1
  if n < r or r < 0: return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1: arr.append([temp, 1])
  if arr==[]: arr.append([n, 1])
  return arr

#####MakeDivisors######
def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors

#####MakePrimes######
def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum

#####GCD#####
def gcd(a, b):
    while b: a, b = b, a % b
    return a

#####LCM#####
def lcm(a, b):
    return a * b // gcd (a, b)

#####BitCount#####
def count_bit(n):
  count = 0
  while n:
    n &= n-1
    count += 1
  return count

#####ChangeBase#####
def base_10_to_n(X, n):
  if X//n: return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

def base_10_to_n_without_0(X, n):
  X -= 1
  if X//n: return base_10_to_n_without_0(X//n, n)+[X%n]
  return [X%n]

#####IntLog#####
def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count

#############
# Main Code #
#############
N = I()
S = S()

from functools import lru_cache
def count(X):
  if X == 0:
    return 0
  else:
    return count(X%count_bit(X))+1


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

FUEAMARI = 0
HERIAMARI = 0
for i in range(N):
  if S[i] == "1":
    FUEAMARI += pow(2,N-1-i,MOD+1)
    if MOD!=1:
      HERIAMARI += pow(2,N-1-i,MOD-1)
for i in range(N):
  if S[i] == "1":
    if MOD!=1:
      X = (HERIAMARI-pow(2,N-1-i,MOD-1))%(MOD-1)
      print(count(X)+1)
    else:
      print(0)
  else:
    X = (FUEAMARI+pow(2,N-1-i,MOD+1))%(MOD+1)
    print(count(X)+1)

Submission status: Accepted

Solution code:
import sys

def popcount(i):
    K = i
    d = 0
    while K > 0:
        d += K % 2
        K //= 2
    return d

def solve():
    input = sys.stdin.readline
    N = int(input())
    X = input().strip("\n")
    countOne = X.count("1")
    modM = [0] * N
    modP = [0] * N
    minusS, plusS = 0, 0
    for i in range(N):
        if X[N-i-1] == "1":
            if countOne > 1: 
                modM[i] = pow(2, i, countOne - 1)
                minusS += modM[i]
                minusS %= (countOne - 1)
            modP[i] = pow(2, i, countOne + 1)
            plusS += modP[i]
            plusS %= (countOne + 1)
    Ans = [0] * N
    for i in range(N):
        if X[i] == "0":
            start = (plusS + pow(2, N - i - 1, countOne + 1)) % (countOne + 1)
            Ans[i] = 1
            while start > 0:
                d = popcount(start)
                Ans[i] += 1
                start %= d
        else:
            if countOne > 1:
                start = (minusS - modM[N - i -1]) % (countOne - 1)
                Ans[i] = 1
                while start > 0:
                    d = popcount(start)
                    Ans[i] += 1
                    start %= d
    print(*Ans, sep = "\n")

    return 0

if __name__ == "__main__":
    solve()

Submission status: Accepted

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

popcnt = 0
for c in s:
    if c == '1':
        popcnt += 1

if popcnt == 0:
    for i in range(n):
        print(1)
    exit()
if popcnt == 1:
    if s[-1] == '0':
        for i in range(n - 1):
            if s[i] == '1':
                print(0)
            else:
                print(1)
        print(2)
    else:
        for i in range(n - 1):
            print(2)
        print(0)
    exit()

xm = x % (popcnt - 1)
xp = x % (popcnt + 1)


def pp(k):
    cnt = 0
    while k > 0:
        cnt += k & 1
        k >>= 1
    return cnt


for i in range(n):
    if s[i] == '0':
        # xp
        rem = xp + pow(2, n - 1 - i, popcnt + 1)
        rem %= popcnt + 1
        cnt = 1
        while rem != 0:
            rem %= pp(rem)
            cnt += 1
        print(cnt)
    else:
        # xm
        rem = xm - pow(2, n - 1 - i, popcnt - 1)
        rem %= popcnt - 1
        cnt = 1
        while rem != 0:
            rem %= pp(rem)
            cnt += 1
        print(cnt)

Submission status: Accepted

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

cnt1 = x.count("1")
p_cnt = cnt1 + 1
m_cnt = cnt1 - 1
p_amari = val % (cnt1 + 1)
if cnt1 - 1 != 0:
    m_amari = val % (cnt1 - 1)
else:
    m_amari = 0


for i in range(n):
    ans = 0
    if x[i] == "0":
        # pになる
        amari = p_amari + pow(2, n - i - 1, p_cnt)
        amari %= p_cnt
        ans += 1
    elif x[i] == "1":
        # mになる
        if cnt1 - 1 == 0:
            print(0)
            continue
        amari = m_amari - pow(2, n - i - 1, m_cnt)
        amari %= m_cnt
        ans += 1
    while amari != 0:
        amari %= bin(amari).count("1")
        ans += 1
    print(ans)

Submission status: Accepted

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


def count(n):
    ans = 0
    while n:
        ans += n % 2
        n //= 2
    return ans


ma = 5*10**5
dp = [0] * ma
for i in range(1, ma):
    dp[i] = dp[i % count(i)]+1

c = x.count("1")
a = int(x, 2) % (c+1)

if c==1:
    for i in range(n):
        if x[i] == "0":
            print(dp[(a + pow(2, n-i-1, c+1)) % (c+1)] + 1)
        else:
            print(0)
    exit()

b = int(x, 2) % (c-1)
for i in range(n):
    if x[i] == "0":
        print(dp[(a + pow(2,n-i-1,c+1))%(c+1)] + 1)
    else:
        print(dp[(b - pow(2, n-i-1, c-1)) % (c-1)] + 1)

Submission status: Accepted

Solution code:
N=int(input())
X=input()
Y=int(X,2)
Z=Y
C=X.count('1')
if C==1:
  for i in range(N):
    if X[i]=='1':
      print(0)
    elif i==N-1:
      print(2)
    else:
      print(1)
  exit()
Y,Z=Y%(C+1),Z%(C-1)
def f(x):
  if x==0:
    return 0
  return 1+f(x%bin(x).count('1'))

for i in range(N):
  if X[i]=='1':
    print(1+f((Z-pow(2,N-i-1,C-1))%(C-1)))
  else:
    print(1+f((Y+pow(2,N-i-1,C+1))%(C+1)))

Submission status: Accepted

Solution code:
n = int(input())
x = list(reversed(list(map(int, input()))))
s = sum(x)
md = [s + 1, s - 1]
bs = [0, 0]
for i in range(2):
    if not md[i]:
        continue
    t = 1
    for j in range(n):
        if x[j]:
            bs[i] = (bs[i] + t) % md[i]
        t = t * 2 % md[i]
def solve(u):
    ans = 0
    while u:
        u = u % bin(u).count('1')
        ans += 1
    return ans
for i in range(n - 1, -1, -1):
    if not md[x[i]]:
        print(0)
        continue
    dt = pow(2, i, md[x[i]]) * (-1 if x[i] else 1)
    print(solve((bs[x[i]] + dt) % md[x[i]]) + 1)

Submission status: Runtime Error

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

f = [-1] * (n+10)
f[0] = 0

for i in range(1, n+10):
    # python bitcount で見つけたこれを参考に https://ameblo.jp/316228/entry-10518720149.html
    f[i] = f[i % bin(i).count('1')] + 1

init_bitcount = x.count('1')
# Xを init_bitcount+1とinit_bitcount-1で割った余り

x_mod_01 = 0
x_mod_10 = 0
for digit in x:
    x_mod_01 *= 2
    x_mod_10 *= 2
    if digit == '1':
        x_mod_01 += 1
        x_mod_10 += 1
    x_mod_01 %= (init_bitcount+1)
    x_mod_10 %= (init_bitcount-1)

# print(x_mod_01, x_mod_10, init_bitcount)

power_mod_01 = [-1] * (n+10)
power_mod_01[0] = 1
for i in range(1, n+10):
    power_mod_01[i] = power_mod_01[i-1] * 2 % (init_bitcount + 1)


power_mod_10 = [-1] * (n+10)
power_mod_10[0] = 1
for i in range(1, n+10):
    power_mod_10[i] = power_mod_10[i-1] * 2 % (init_bitcount - 1)


for i in range(n):
    if x[i] == '0':
        # 0→1
        first_residue = (x_mod_01 + power_mod_01[n - i - 1]) % (init_bitcount+1)
        print(f[first_residue] + 1)
    else:
        # 1→0
        first_residue = (x_mod_10 - power_mod_10[n - i - 1]) % (init_bitcount-1)
        print(f[first_residue] + 1)

Submission status: Runtime Error

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

f = [-1] * (n+10)
f[0] = 0

for i in range(1, n+10):
    # python bitcount で見つけたこれを参考に https://ameblo.jp/316228/entry-10518720149.html
    f[i] = f[i % bin(i).count('1')] + 1

init_bitcount = x.count('1')
# Xを init_bitcount+1とinit_bitcount-1で割った余り

x_mod_01 = 0
x_mod_10 = 0
for digit in x:
    x_mod_01 *= 2
    x_mod_10 *= 2
    if digit == '1':
        x_mod_01 += 1
        x_mod_10 += 1
    x_mod_01 %= (init_bitcount+1)
    x_mod_10 %= (init_bitcount-1)

# print(x_mod_01, x_mod_10, init_bitcount)

for i in range(n):
    if x[i] == '0':
        # 0→1
        first_residue = (x_mod_01 + 2**(n - i - 1)) % (init_bitcount+1)
        print(f[first_residue] + 1)
    else:
        # 1→0
        first_residue = (x_mod_10 - 2**(n - i - 1)) % (init_bitcount-1)
        print(f[first_residue] + 1)

Submission status: Runtime Error

Solution code:
import sys
read = sys.stdin.read
#readlines = sys.stdin.readlines
from collections import defaultdict

def main():
    def from10to2(p):
        res = []
        while p:
            p, t = divmod(p, 2)
            res.append(str(t))
        return "".join(res[::-1])

    def from2to10(p):
        res = 0
        num2 = 1
        for c in p[::-1]:
            if c == '1':
                res += num2
            num2 *= 2
        return res

    def f(p):
        if p == 0:
            return 0
        elif d1[p] > 0:
            return d1[p]
        else:
            ppop = from10to2(p).count('1')
            p2 = p % ppop
            fp = f(p2) + 1
            d1[p] = fp
            return fp

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

    numof1 = x.count('1')
    bin2_p = [0] * n
    num2 = 1
    for i1 in range(1, n+1):
        bin2_p[-i1] = num2
        num2 = (num2 * 2) % (numof1 + 1)

    bin2_m = [0] * n
    num2 = 1
    if numof1 == 1:
        pass
    else:
        for i1 in range(1, n+1):
            bin2_m[-i1] = num2
            num2 = (num2 * 2) % (numof1 - 1)

    xas10 = from2to10(x)
    xas10_p = xas10 % (numof1 + 1)
    if numof1 == 1:
        xas10_m = 0
    else:
        xas10_m = xas10 % (numof1 - 1)
    d1 = defaultdict(int)
    d1[0] = 0
    for j1 in range(n):
        if x[j1] == '1':
            t0 = xas10_m - bin2_m[j1]
            t0 = t0 % (numof1 - 1)
            if t0 == 0:
                print(1)
            else:
                print(f(t0) + 1)
        else:
            t0 = xas10_p + bin2_p[j1]
            t0 = t0 % (numof1 + 1)
            if t0 == 0:
                print(1)
            else:
                print(f(t0) + 1)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import sys
read = sys.stdin.read
#readlines = sys.stdin.readlines
from collections import defaultdict

def main():
    def from10to2(p):
        res = []
        while p:
            p, t = divmod(p, 2)
            res.append(str(t))
        return "".join(res[::-1])

    def from2to10(p):
        res = 0
        num2 = 1
        for c in p[::-1]:
            if c == '1':
                res += num2
            num2 *= 2
        return res

    def f(p):
        if p == 0:
            return 0
        elif d1[p] > 0:
            return d1[p]
        else:
            ppop = from10to2(p).count('1')
            p2 = p % ppop
            fp = f(p2) + 1
            d1[p] = fp
            return fp

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

    numof1 = x.count('1')
    bin2_p = [0] * n
    num2 = 1
    for i1 in range(1, n+1):
        bin2_p[-i1] = num2
        num2 = (num2 * 2) % (numof1 + 1)

    bin2_m = [0] * n
    num2 = 1
    for i1 in range(1, n+1):
        bin2_m[-i1] = num2
        num2 = (num2 * 2) % (numof1 - 1)

    xas10 = from2to10(x)
    xas10_p = xas10 % (numof1 + 1)
    xas10_m = xas10 % (numof1 - 1)
    d1 = defaultdict(int)
    d1[0] = 0
    for j1 in range(n):
        if x[j1] == '1':
            t0 = xas10_m - bin2_m[j1]
            t0 = t0 % (numof1 - 1)
            if t0 == 0:
                print(1)
            else:
                print(f(t0) + 1)
        else:
            t0 = xas10_p + bin2_p[j1]
            t0 = t0 % (numof1 + 1)
            if t0 == 0:
                print(1)
            else:
                print(f(t0) + 1)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import sys
read = sys.stdin.read
#readlines = sys.stdin.readlines
from collections import defaultdict

def main():
    def from10to2(p):
        res = []
        while p:
            p, t = divmod(p, 2)
            res.append(str(t))
        return "".join(res[::-1])

    def from2to10(p):
        res = 0
        num2 = 1
        for c in p[::-1]:
            if c == '1':
                res += num2
            num2 *= 2
        return res

    def f(p):
        if p == 0:
            return 0
        elif d1[p] > 0:
            return d1[p]
        else:
            ppop = from10to2(p).count('1')
            p2 = p % ppop
            fp = f(p2) + 1
            d1[p] = fp
            return fp

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

    numof1 = x.count('1')
    bin2_p = [0] * n
    num2 = 1
    for i1 in range(1, n+1):
        bin2_p[-i1] = num2
        num2 = (num2 * 2) % (numof1 + 1)

    bin2_m = [0] * n
    num2 = 1
    for i1 in range(1, n+1):
        bin2_m[-i1] = num2
        num2 = (num2 * 2) % (numof1 - 1)

    xas10 = from2to10(x)
    xas10_p = xas10 % (numof1 + 1)
    xas10_m = xas10 % (numof1 - 1)
    d1 = defaultdict(int)
    d1[0] = 0
    for j1 in range(n):

        if x[j1] == '1':
            t0 = xas10_m - bin2_m[j1]
            if t0 < 0:
                t0 += bin2_m[j1]
            print(f(t0) + 1)
        else:
            t0 = xas10_p + bin2_p[j1]
            t0 = t0 % (numof1 + 1)
            print(f(t0) + 1)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import copy

n = int(input())
X = list(input())

popcount = [0]*(2*10**5)

num = int("".join(X), 2)
cnt = X.count("1")

for i in range(1,2*10**5):
    tmp_cnt = bin(i).count("1")
    popcount[i] = i%tmp_cnt

for i,x in enumerate(X):
    tmp = copy.deepcopy(X)
    ans = 1
    if x == "0":
        tmp[i] = "1"
        now = int("".join(tmp), 2)
        now = now%(cnt+1)
    else:
        tmp[i] = "0"
        now = int("".join(tmp), 2)
        now = now%(cnt-1)
    while now:
        now = popcount[now]
        ans += 1
    print(ans)