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 numpy as np

N = int(input())
X = str(input())
num_one = X.count("1")

dp = [-1] * N
dp[0] = 0
def dfs(n):
    if dp[n] == -1:
        dp[n] = 1 + dfs(n % bin(n).count('1'))
    return dp[n]

num_one = X.count("1")
bool_arr = np.array([True if X[N-i-1] == "1" else False for i in range(N)])
zero_ver = np.array([pow(2,  i, num_one + 1) for i in range(N)])
zero_ver_sum = sum(zero_ver[bool_arr])

one_ver = -1
one_ver_sum = 0
flag = False
if num_one != 1:
    one_ver = np.array([pow(2,  i, num_one - 1) for i in range(N)])
    one_ver_sum = sum(one_ver[bool_arr])
else:
    flag = True
for i in range(1,N+1):
    start = 0
    if bool_arr[N-i] == False:
        start = (zero_ver_sum + pow(2, N - i, num_one + 1)) % (num_one + 1)
        print(dfs(start)+1)
    else:
        if flag:
            print(0)
        else:
            start = (one_ver_sum - pow(2, N - i, num_one - 1))  %  (num_one - 1)
            print(dfs(start)+1)

Submission status: Accepted

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


n=int(input())
x=input()
num=int(x,2)
cnt=popcount(num)

A=[]
for i in range(n):
    number=num
    if x[i]=="1" and cnt==1:A.append(-1)
    elif x[i]=="1":
        number %=cnt-1
        A.append((number-pow(2,n-i-1,cnt-1))%(cnt-1))
    else:
        number %=cnt+1
        A.append((number+pow(2,n-i-1,cnt+1))%(cnt+1))

for i in A:
    ans=i
    if ans==-1:print(0)
    else:
        point=1
        while ans!=0:
            ans %=popcount(ans)
            point +=1
        print(point)

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines


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


def f(n):
    cnt = 0
    while n != 0:
        n = n % pop_cnt(n)
        cnt += 1
    return cnt
 
n = int(readline())
x2 = list(readline().decode().rstrip())
x10 = int(''.join(x2), 2)

c = x2.count('1')
mod1 = x10 % (c + 1)
mod2 = x10 % (c - 1) if c-1 != 0 else 0

for i in range(n):
    ans = 0
    if x2[i] == '0':
        t = (mod1 + pow(2, n-i-1, c+1)) % (c+1)
    else:
        if c-1 != 0:
            t = (mod2 - pow(2, n-i-1, c-1)) % (c-1)
        else:
            print(0)
            continue
    
    ans = f(t) + 1
    print(ans)

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines


def popcnt(n):
    return bin(n).count("1")


def mod(n, cnt):
    if n == 0:
        return cnt
    n = n % popcnt(n)
    cnt += 1
    return mod(n, cnt)


n = int(readline())
x2 = list(readline().decode().rstrip())
x10 = int(''.join(x2), 2)

c = x2.count('1')
mod1 = x10 % (c + 1)
mod2 = x10 % (c - 1) if c - 1 != 0 else 0

for i in range(n):
    if x2[i] == '0':
        t = (mod1 + pow(2, n - i - 1, c + 1)) % (c + 1)
    else:
        if c - 1 != 0:
            t = (mod2 - pow(2, n - i - 1, c - 1)) % (c - 1)
        else:
            print(0)
            continue
    print(mod(t, 1))

Submission status: Accepted

Solution code:
import bisect, collections, copy, heapq, itertools, math, string, sys
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = float('inf')
def I(): return int(input())
def F(): return float(input())
def SS(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LSS(): return input().split()

def resolve():
    N = I()
    X = SS()

    # 一回の操作でnはN以下になる
    # 2回目以降の操作はメモ化再帰
    # 初回popcountは2種類しかない Xのpopcountから足し引きすればよい

    pc_X = X.count('1')

    if pc_X == 0:
        for i in range(N):
            print(1)
    elif pc_X == 1:
        for i in range(N):
            if i == X.index('1'):
                print(0)
            else:
                # 1が2つある場合、最後の位が1の場合、奇数
                if i == N - 1 or X.index('1') == N - 1:
                    print(2)
                else:
                    print(1)
    else:
        next_X_m1 = 0
        next_X_p1 = 0
        pc_m1 = pc_X - 1
        pc_p1 = pc_X + 1
        for i in range(N):
            if X[i] == '1':
                next_X_m1 += pow(2, N - 1 - i, pc_m1)
                next_X_p1 += pow(2, N - 1 - i, pc_p1)

        dp = [-1] * N
        dp[0] = 0

        def dfs(n):
            if dp[n] == -1:
                dp[n] = 1 + dfs(n % bin(n).count('1'))
            return dp[n]

        for i in range(N):
            next = 0
            if X[i] == '0':
                next = (next_X_p1 + pow(2, N - 1 - i, pc_p1)) % pc_p1
            else:
                next = (next_X_m1 - pow(2, N - 1 - i, pc_m1)) % pc_m1
            ans = dfs(next) + 1
            print(ans)
    # print(dp)

if __name__ == '__main__':
    resolve()

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines


def popcnt(n):
    return bin(n).count("1")


def mod(n, cnt):
    if n == 0:
        return cnt
    n = n % popcnt(n)
    cnt += 1
    return mod(n, cnt)


n = int(readline())
x2 = list(readline().decode().rstrip())
x10 = int(''.join(x2), 2)

c = x2.count('1')
mod1 = x10 % (c + 1)
mod2 = x10 % (c - 1) if c - 1 != 0 else 0

for i in range(n):
    if x2[i] == '0':
        t = (mod1 + pow(2, n - i - 1, c + 1)) % (c + 1)
    else:
        if c - 1 != 0:
            t = (mod2 - pow(2, n - i - 1, c - 1)) % (c - 1)
        else:
            print(0)
            continue
    print(mod(t, 1))

Submission status: Accepted

Solution code:
import bisect, collections, copy, heapq, itertools, math, string, sys
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = float('inf')
def I(): return int(input())
def F(): return float(input())
def SS(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LSS(): return input().split()

def resolve():
    N = I()
    X = SS()

    # 一回の操作でnはN以下になる
    # 2回目以降の操作はメモ化再帰
    # 初回popcountは2種類しかない Xのpopcountから足し引きすればよい

    pc_X = X.count('1')

    if pc_X == 0:
        for i in range(N):
            print(1)
    elif pc_X == 1:
        for i in range(N):
            if i == X.index('1'):
                print(0)
            else:
                # 1が2つある場合、最後の位が1の場合、奇数
                if i == N - 1 or X.index('1') == N - 1:
                    print(2)
                else:
                    print(1)
    else:
        next_X_m1 = 0
        next_X_p1 = 0
        pc_m1 = pc_X - 1
        pc_p1 = pc_X + 1
        for i in range(N):
            if X[i] == '1':
                next_X_m1 += pow(2, N - 1 - i, pc_m1)
                next_X_p1 += pow(2, N - 1 - i, pc_p1)
        dp = [-1] * N
        dp[0] = 0

        def dfs(n):
            if dp[n] == -1:
                dp[n] = 1 + dfs(n % bin(n).count('1'))
            return dp[n]

        for i in range(N):
            next = 0
            if X[i] == '0':
                next = (next_X_p1 + pow(2, N - 1 - i, pc_p1)) % pc_p1
            else:
                if pc_m1 >= 1:
                    next = (next_X_m1 - pow(2, N - 1 - i, pc_m1)) % pc_m1
                else:
                    next = next_X_m1 - pow(2, N - 1 - i)

            if pc_X == 1 and X[i] == '1' and i == N - 1:
                ans = 0
            else:
                ans = dfs(next) + 1
            print(ans)
    # print(dp)

if __name__ == '__main__':
    resolve()

Submission status: Accepted

Solution code:
import bisect, collections, copy, heapq, itertools, math, string, sys
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = float('inf')
def I(): return int(input())
def F(): return float(input())
def SS(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LSS(): return input().split()

def resolve():
    N = I()
    X = SS()

    # 一回の操作でnはN以下になる
    # 2回目以降の操作はメモ化再帰
    # 初回popcountは2種類しかない Xのpopcountから足し引きすればよい

    pc_X = X.count('1')

    if pc_X == 0:
        for i in range(N):
            print(1)
    elif pc_X == 1:
        for i in range(N):
            if i == X.index('1'):
                print(0)
            else:
                # 1が2つある場合、最後の位が1の場合、奇数
                if i == N - 1 or X.index('1') == N - 1:
                    print(2)
                else:
                    print(1)
    else:
        next_X_m1 = 0
        next_X_p1 = 0
        pc_m1 = pc_X - 1
        pc_p1 = pc_X + 1
        for i in range(N):
            if X[i] == '1':
                next_X_m1 += pow(2, N - 1 - i, pc_m1)
                next_X_p1 += pow(2, N - 1 - i, pc_p1)
        dp = [-1] * N
        dp[0] = 0

        # def dfs(n):
        #     if dp[n] == -1:
        #         dp[n] = 1 + dfs(n % bin(n).count('1'))
        #     return dp[n]

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

        for i in range(N):
            next = 0
            if X[i] == '0':
                next = (next_X_p1 + pow(2, N - 1 - i, pc_p1)) % pc_p1
            else:
                if pc_m1 >= 1:
                    next = (next_X_m1 - pow(2, N - 1 - i, pc_m1)) % pc_m1
                else:
                    next = next_X_m1 - pow(2, N - 1 - i)

            if pc_X == 1 and X[i] == '1' and i == N - 1:
                ans = 0
            else:
                # ans = dfs(next) + 1
                ans = f(next) + 1
            print(ans)
    # print(dp)

if __name__ == '__main__':
    resolve()

Submission status: Accepted

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

def e(x, y):
    t = [0] * len(x)
    if y <= 0: return (-1, t)
    if y == 1: return (0, t)
    res = 0
    z = 1
    for i in range(len(x) - 1, -1, -1):
        t[i] = z
        if x[i] == '1':
            res = (res + z) % y
        z = (z << 1) % y
    return (res, t)

def popcount(x):
    x = (x & 0x5555555555555555) + (x >> 1 & 0x5555555555555555)
    x = (x & 0x3333333333333333) + (x >> 2 & 0x3333333333333333)
    x = x + (x >> 4) & 0x0f0f0f0f0f0f0f0f
    x += x >> 8
    x += x >> 16
    x += x >> 32
    return x & 0x7f

fm = [-1] * (2 * (10 ** 5) + 1)
fm[0] = 0
def f(x):
    if fm[x] >= 0: return fm[x]
    fm[x] = 1 + f(x % popcount(x))
    return fm[x]


pc = X.count('1')
s0, t0 = e(X, pc + 1)
s1, t1 = e(X, pc - 1)

for i in range(N):
    t = 0
    if X[i] == '0':
        t = (s0 + t0[i]) % (pc + 1)
    else:
        if pc == 1:
            print(0)
            continue
        t = (s1 - t1[i]) % (pc - 1)
    print(1 + f(t))

Submission status: Accepted

Solution code:
def popcount(n):
    return bin(n).count("1")


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


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

c = X.count('1')
t1 = [0] * N
t1[0] = 1 % (c + 1)
for i in range(1, N):
    t1[i] = (t1[i - 1] << 1) % (c + 1)
x1 = 0
for i in range(N):
    if X[i] == '0':
        continue
    x1 += t1[N - 1 - i]

if c - 1 != 0:
    t2 = [0] * N
    t2[0] = 1 % (c - 1)
    for i in range(1, N):
        t2[i] = (t2[i - 1] << 1) % (c - 1)
    x2 = 0
    for i in range(N):
        if X[i] == '0':
            continue
        x2 += t2[N - 1 - i]

result = []
for i in range(N):
    if X[i] == '0':
        n = (x1 + t1[N - 1 - i]) % (c + 1)
    elif X[i] == '1':
        if c - 1 == 0:
            result.append(0)
            continue
        n = (x2 - t2[N - 1 - i]) % (c - 1)
    result.append(1 + f(n))
print(*result, sep='\n')

Submission status: Accepted

Solution code:
def popcount(x):
    xb = bin(x)
    return xb.count("1")
def solve(x, count_1):
    temp = x %count_1
    if(temp == 0):
        return 1
    else:
        return 1 + solve(temp, popcount(temp))
n = int(input())
x = input()
x_b = int(x, 2)
mod = x.count("1")
xm1 = x_b %(mod+1)
if(mod != 1):
    xm2 = x_b %(mod-1)
for i in range(n):
    if(x[i] == "0"):
        mi = (((pow(2, n-1-i, mod+1) + xm1) % (mod+1)))
        if(mi == 0):
            print(1)
        else:
            print(1 + solve(mi, popcount(mi)))
    else:
        if(mod == 1):
            print(0)
        else:
            mi = ((xm2-pow(2, n-1-i, mod-1)) % (mod-1))
            if((x_b - xm2 == 0)):
                print(0)
            elif(mi == 0):
                print(1)
            else:
                print(1 + solve(mi, popcount(mi)))

Submission status: Accepted

Solution code:
n = int(input())
s = input()
pw, pw1, pw2 = [0] * n, [0] * n, [0] * n
pw[0], pw1[0], pw2[0] = 1, 1, 1
v, mod1, mod2 = 0, 0, 0
for i in range(n):
    if s[i] == '1':
        v += 1
for i in range(1, n):
    pw1[i] = int(pw1[i - 1] * 2) % (v + 1)
    if v >= 2:
        pw2[i] = int(pw2[i - 1] * 2) % (v - 1)
for i in range(n):
    if s[i] == '1':
        mod1 = (mod1 + pw1[n - i - 1]) % (v + 1)
        if v >= 2:
            mod2 = (mod2 + pw2[n - i - 1]) % (v - 1)    
for i in range(n):
    copy, x, cnt = 0, v, 1
    
    if s[i] == '0':
        x += 1
        copy = (mod1 + pw1[n - i - 1]) % x
    else:
        x -= 1
        if x >= 1:
            copy = (mod2 - pw2[n - i - 1]) % x
        else:
            copy = -1
    if copy == -1:
        print(0)
    else:
        x = bin(copy).count('1')
        while copy > 0:
            copy %= x
            x = bin(copy).count('1')
            cnt += 1
        print(cnt)

Submission status: Accepted

Solution code:
def popcount(num):
    ans = 0
    while num:
        if num % 2 == 1:
            ans += 1
        num //= 2
    return ans


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

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

tmp4p = int(X, 2) % (popcount_X+1)
if popcount_X != 1:
    tmp4m = int(X, 2) % (popcount_X-1)

for i in range(N):
    bit = X[i]

    f = 0
    if (popcount_X == 1 and bit == "1"):
        print(f)
        continue
    
    if bit == "1":
        nxt = ( tmp4m - pow(2, N-i-1, (popcount_X-1))  + (popcount_X-1) ) % (popcount_X-1)
    else:
        nxt = ( tmp4p + pow(2, N-i-1, (popcount_X+1))  ) % (popcount_X+1)

    f += 1
    while nxt:
        pc = popcount(nxt)
        nxt = nxt % pc
        f += 1
    
    print(f)

Submission status: Accepted

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

  if N == 1:
    if X.count("1"):
      print(0)
    else:
      print(1)
    return True

  base_1_count = X.count("1")
  if base_1_count == 0:
    for _ in range(N):
      print(1)
    return True

  X_int = int(X, 2)
  X_int_p = X_int%(base_1_count + 1)

  # RE 対策
  if base_1_count == 1:
    for i in range(N):
      if X[i] == "1":
        print(0)
      else:
        if i == N - 1:
          Xi = X_int_p + 1
        else:
          Xi = X_int_p
        count = 1
        while Xi != 0:
          Xi %= bin(Xi).count("1")
          count += 1
        print(count)
    return True

  X_int_m = X_int%(base_1_count - 1)
  for i in range(N):
    # 初期値計算を高速にやる
    if X[i] == "1":
      temp_1_count = base_1_count-1
      pow_2 = pow(2, N-i-1, base_1_count-1)
      if X_int_m <= pow_2:
        Xi = X_int_m - pow_2 + base_1_count-1
      else:
        Xi = X_int_m - pow_2
    else:
      temp_1_count = base_1_count+1
      Xi = X_int_p + pow(2, N-i-1, base_1_count+1)
      while Xi >= base_1_count+1:
        Xi %= base_1_count+1

    # print("1_c={0}".format(temp_1_count))
    if temp_1_count == Xi:
      print(1)
      continue

    count = 1
    while Xi != 0:
      num_of_1 = bin(Xi).count("1")
      Xi %= num_of_1
      count += 1
    print(count)

if __name__ == "__main__":
    resolve()

Submission status: Accepted

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

count = x.count("1")

mod1 = 0 # 1少ない
mod2 = 0 # 1多い

#　初回の各桁のbitを反転させた場合のmod結果を格納するリスト
mod1_list = [0]*n
mod2_list = [0]*n

now1 = 1

x = x[::-1]

# mod1の計算
for i in range(n):
    mod1_list[i] = now1
    if x[i] == "1":
        mod1 += now1%(count+1)
    now1 *= 2
    now1 %= (count+1)

mod1 %= (count+1)

now2 = 1

# mod2の計算
if count >= 3:
    for i in range(n):
        mod2_list[i] = now2
        if x[i] == "1":
            mod2 += now2%(count-1)
        now2 *= 2
        now2 %= (count-1)
    
    mod2 %= (count-1)

mod1_list = mod1_list[::-1]
mod2_list = mod2_list[::-1]
x = x[::-1]

for i in range(n):
    total = 1
    if x[i] == "1":
        if count == 1:
            print(0)
            continue
        elif count == 2:
            print(1)
            continue
        now = mod2-mod2_list[i]
        now %= (count-1)
    else:
        now = mod1+mod1_list[i]
        now %= (count+1)

    while now != 0:
        now = now%(bin(now).count("1"))
        total += 1

    print(total)

Submission status: Accepted

Solution code:
import sys

def input(): return sys.stdin.readline().strip()
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 ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 19
MOD = 10 ** 9 + 7
EPS = 10 ** -10

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

N = INT()
S = list(map(int, input()))[::-1]

pcnt1 = S.count(1) - 1
pcnt2 = S.count(1) + 1
base1 = base2 = 0
for i in range(N):
    if S[i]:
        if pcnt1 != 0:
            base1 += pow(2, i, pcnt1)
        base2 += pow(2, i, pcnt2)

ans = [0] * N
for i in range(N):
    if S[i] and pcnt1 == 0:
        ans[i] = 0
        continue
    cur = 0
    if S[i]:
        cur += (base1 - pow(2, i, pcnt1)) % pcnt1
    else:
        cur += (base2 + pow(2, i, pcnt2)) % pcnt2
    cnt = 1
    while cur:
        cur %= popcount(cur)
        cnt += 1
    ans[i] = cnt
for a in ans[::-1]:
    print(a)

Submission status: Accepted

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

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

n = int(input())
x = input()
xx = int(x,2)
p = x.count("1")
stand1 = xx%(p+1)
if p != 1:
    stand2 = xx%(p-1)
for i in range(n):
    if x[i] == "1":
        if p != 1:
            k = stand2
            k -= pow(2,n-i-1,p-1) 
            k %= p-1
        else:
            print(0)
            continue
    else:
        k = stand1
        k += pow(2,n-i-1,p+1)
        k %= p+1
    print(f(k))

Submission status: Accepted

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

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

n = int(input())
x = input()
xx = int(x,2)
p = x.count("1")
stand1 = xx%(p+1)
if p != 1:
    stand2 = xx%(p-1)
for i in range(n):
    if x[i] == "1":
        if p != 1:
            k = stand2
            k -= pow(2,n-i-1,p-1) 
            k %= p-1
        else:
            print(0)
            continue
    else:
        k = stand1
        k += pow(2,n-i-1,p+1)
        k %= p+1
    print(1+f(k))

Submission status: Accepted

Solution code:
from copy import copy

def popcount(x):
    return bin(x).count("1")

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

n = int(input())
x = input()
xx = int(x,2)
p = x.count("1")
stand1 = xx%(p+1)
if p != 1:
    stand2 = xx%(p-1)
for i in range(n):
    if x[i] == "1":
        if p != 1:
            k = copy(stand2)
            k -= pow(2,n-i-1,p-1) 
            k %= p-1
        else:
            print(0)
            continue
    else:
        k = copy(stand1)
        k += pow(2,n-i-1,p+1)
        k %= p+1
    print(1+f(k))

Submission status: Accepted

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

if __name__ == "__main__":
    n = int(input())
    x = input()
    d = x.count('1')
    if d == 1:
        for i in x[:-1]:
            if i == '0':
                print(1)
            else:
                print(0)
        if x[-1] == '1':
            print(0)
        else:
            print(2)
        exit()

    ans = []
    M = 0
    for i in x:
        M <<= 1
        if i == '1':
            M += 1
    p = M % (d + 1)
    m = M % (d - 1)
    for i in range(n):
        if x[i] == '0':
            ans.append(f((p + pow(2, n - i - 1, d + 1)) % (d + 1)))
        else:
            ans.append(f((m - pow(2, n - i - 1, d - 1)) % (d - 1)))
    print(*ans, sep='\n')

Submission status: Accepted

Solution code:
def popcount(x):
    c = 0
    while x > 0:
        if x & 1: c += 1
        x //= 2
    return c

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

n = int(input())
X = input()
po = X.count('1')
pp = po + 1
pm = max(1, po - 1)
rp = rm = 0
for x in X:
    rp = (rp*2 + int(x)) % pp
    rm = (rm*2 + int(x)) % pm
bp = [0]*(n) # 2^i % (po+1)
bm = [0]*(n) # 2^i % (po-1)
bp[n-1] = 1 % pp
bm[n-1] = 1 % pm
for i in range(n-1, 0, -1):
    bp[i-1] = bp[i]*2 % pp
    bm[i-1] = bm[i]*2 % pm
for i in range(n):
    if X[i] == '0': ri = (rp + bp[i]) % pp
    else:
        if po-1 != 0: ri = (rm - bm[i]) % pm
        else:
            print(0)
            continue
    print(f(ri) + 1)

Submission status: Accepted

Solution code:
from logging import *
basicConfig(level=DEBUG, format='%(levelname)s: %(message)s')
disable(CRITICAL)

n = int(input())
X = input()
debug('n {}'.format(n))
debug('X {}'.format(X))
po = X.count('1')

# if po == 0:
#     print(0)
#     exit()

pp = po + 1
pm = max(1, po - 1)

rp = 0
rm = 0
for x in X:
    rp = (rp*2 + int(x)) % pp
    rm = (rm*2 + int(x)) % pm

bp = [0]*(n) # 2^i % (po+1)
bm = [0]*(n) # 2^i % (po-1)
bp[n-1] = 1 % pp
bm[n-1] = 1 % pm
for i in range(n-1,0,-1):
    bp[i-1] = bp[i]*2 % pp
    bm[i-1] = bm[i]*2 % pm

debug('po {}'.format(po))
debug('pp {}'.format(pp))
debug('pm {}'.format(pm))
debug('rp {}'.format(rp))
debug('rm {}'.format(rm))
debug('bp {}'.format(bp))
debug('bm {}'.format(bm))
debug('===')

def popcount(x):
    c = 0
    while x > 0:
        if x & 1: c += 1
        x //= 2
    return c

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

for i in range(n):
    if X[i] == '0':
        ri = (rp + bp[i]) % pp
    else: # '1'
        if po-1 != 0: ri = (rm - bm[i]) % pm
        else:
            print(0)
            continue
    debug('i {} ri {}'.format(i,ri))
    c = f(ri) + 1
    debug('c {}'.format(c))
    print(c)

Submission status: Accepted

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

from pprint import pprint
import sys

sys.setrecursionlimit(10 ** 6)
INF = float('inf')


n = int(input())
x = input()
x_pc = x.count('1')
x_pc_plus = x_pc + 1
x_pc_minus = x_pc - 1

# 2 ** i % x_pc_plus, 2 ** i % x_pc_minus を予め計算しておく
r_plus_list = [pow(2, i, x_pc_plus) for i in range(n+1)]
r_minus_list = [0] * (n+1)
if x_pc_minus > 0:
    r_minus_list = [pow(2, i, x_pc_minus) for i in range(n+1)]

x = x[::-1]
r_plus = 0
r_minus = 0
for i in range(n):
    if x[i] == '1':
        r_plus += r_plus_list[i]
        r_minus += r_minus_list[i]

for i in range(n-1, -1, -1):
    if x[i] == '0':
        diff = (r_plus + r_plus_list[i]) % x_pc_plus
    elif x_pc_minus >= 1:
        diff = (r_minus - r_minus_list[i]) % x_pc_minus
    else:
        print(0)
        continue
    ans = 1
    while diff > 0:
        diff = diff % bin(diff).count('1')
        ans += 1
    print(ans)

Submission status: Accepted

Solution code:
def popcount(n):
    return bin(n).count("1")

def f(n):
    cnt = 0
    while n != 0:
        n %= popcount(n)
        cnt += 1
    return cnt

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

pcnt_X = S.count("1")
X = int(S, 2)

Xm = X % (pcnt_X - 1) if pcnt_X - 1 > 0 else float("inf")
Xp = X % (pcnt_X + 1)

for i, s in enumerate(S):
    if s == "0":
        x = (Xp + pow(2, N - 1 - i, pcnt_X + 1)) % (pcnt_X + 1)
        print(1 + f(x))
    elif pcnt_X - 1 > 0:
        x = (Xm - pow(2, N - 1 - i, pcnt_X - 1)) % (pcnt_X - 1)
        print(1 + f(x))
    else:
        print(0)

Submission status: Accepted

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

n1 = X.count("1")
Xn = int(X, 2)

Xms = (Xn % (n1 - 1)) if n1 > 1 else 0
Xml = Xn % (n1 + 1)


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


dp = [0] * ((10 ** 5) * 2 + 1)
for i in range(1, len(dp)):
    dp[i] = f(i)


for i in range(N):
    cnt = 0
    Xim = 0

    if X[i] == "1" and n1 == 1:
        print(cnt)
    elif X[i] == "1":
        print(dp[(Xms - pow(2, N - i - 1, n1 - 1)) % (n1 - 1)] + 1)
    else:
        print(dp[(Xml + pow(2, N - i - 1, n1 + 1)) % (n1 + 1)] + 1)

Submission status: Accepted

Solution code:
def popcount(n):
    return bin(n).count('1')
    
N=int(input())
X=input()
xl=list(X)
X=int(X,2)
a=popcount(X)
#1が減った時
if a==1:
    xd=0
else:
    xd=X%(a-1)
#1が増えたとき
xi=X%(a+1)

for i in range(N):
    if xl[i]=='1':
        if a==1:
            print(0)
            continue
        else:
            k=pow(2,N-1-i,a-1)
            x=(xd-k)%(a-1)
    else:
        k=pow(2,N-1-i,a+1)
        x=(xi+k)%(a+1)
    count=1
    while x!=0:
        x%=popcount(x)
        count+=1
    print(count)

Submission status: Accepted

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

n1 = X.count("1")
Xn = int(X, 2)

Xms = (Xn % (n1 - 1)) if n1 > 1 else 0
Xml = Xn % (n1 + 1)


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


# dp = [0] * ((10 ** 5) * 2 + 1)
# for i in range(1, len(dp)):
#     dp[i] = f(i)


for i in range(N):
    cnt = 0
    xi = 0
    if X[i] == "1" and n1 == 1:
        print(cnt)
        continue
    elif X[i] == "1":
        xi = (Xms - pow(2, N - i - 1, n1 - 1)) % (n1 - 1)
    else:
        xi = (Xml + pow(2, N - i - 1, n1 + 1)) % (n1 + 1)
    cnt = 1
    while xi != 0:
        xi %= bin(xi).count("1")
        cnt += 1
    print(cnt)

Submission status: Accepted

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

popcount = x.count('1')
p = int(x, 2) % (popcount + 1)
q = int(x, 2) % (popcount - 1) if popcount != 1 else 0
for i in range(n):
    if x[i] == '0':
        y = (p + pow(2, n-i-1, popcount+1)) % (popcount + 1)
    else:
        if popcount != 1:
            y = (q - pow(2, n-i-1, popcount-1)) % (popcount - 1)
        else:
            print(0)
            continue
    cnt = 1
    while y != 0:
        y %= bin(y).count('1')
        cnt += 1
    print(cnt)

Submission status: Accepted

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

n1 = X.count("1")
Xn = int(X, 2)

Xms = (Xn % (n1 - 1)) if n1 > 1 else 0
Xml = Xn % (n1 + 1)

p2s = [1]
p2l = [1]
s2 = 1
l2 = 1
for i in range(N - 1):
    s2 = (s2 * 2) % (n1 - 1) if n1 > 1 else 0
    l2 = (l2 * 2) % (n1 + 1)
    p2s.append(s2)
    p2l.append(l2)


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


for i in range(N):
    cnt = 0
    p2 = 2 ** (N - i - 1)
    Xim = 0

    if X[i] == "1" and n1 == 1:
        print(cnt)
    elif X[i] == "1":
        print(f((Xms - p2s[-i - 1]) % (n1 - 1)) + 1)
    else:
        print(f((Xml + p2l[-i - 1]) % (n1 + 1)) + 1)

Submission status: Accepted

Solution code:
def count_pop(y):
  count = 0
  while y != 0:
    if y & 1 == 1:count+=1
    y = y >> 1
  return count
  
def main():
  N = int(input())
  X = input()
  X_val=int(X,2)
  X_pc=X.count('1')
  x_mod_pc_x_plus_1 = X_val % (X_pc + 1)
  x_mod_pc_x_minus_1 = X_val % max(X_pc - 1, 1)
  for i in range(N):
    if X[i] == '1':
      pc = X_pc - 1
      if pc == 0:
        print(0)
        continue
      val = (x_mod_pc_x_minus_1 - pow(2, N-i-1, pc)) % pc
    else:     
      pc = X_pc + 1
      val = (x_mod_pc_x_plus_1 + pow(2, N-i-1, pc)) % pc
    ans = 1   
    while val > 0:
      val %= bin(val).count('1')
      ans += 1
    print(ans)
  pass       
if __name__=='__main__':
  main()

Submission status: Accepted

Solution code:
n = int(input())
s = input()
x = int(s, 2)
p = s.count("1")
if p > 1:
	pre0 = x%(p-1)
pre1 = x%(p+1)

nxt = [i for i in range(n+10)]
for i in range(1, n+10):
	nxt[i] %= bin(i).count("1")

for i in range(n):
	if x == 1<<(n-1-i):
		print(0)
		continue
	if s[i] == "0":
		tmp = (pre1 + pow(2, n-1-i, p+1)) % (p+1)
	else:
		tmp = (pre0 - pow(2, n-1-i, p-1)) % (p-1)
	ans = 1
	while tmp > 0:
		ans += 1
		tmp = nxt[tmp]
	print(ans)

Submission status: Accepted

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

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

LIMIT = 5*10**5
dp = [0] * LIMIT
for i in range(1, LIMIT):
    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)