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

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

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

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

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

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

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

#

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

Yes = 'Yes'
No = 'No'


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



main()

Submission status: Accepted

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

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

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

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

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

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

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

#

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

Yes = 'Yes'
No = 'No'


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



main()

Submission status: Accepted

Solution code:
it = lambda: list(map(int, input().strip().split()))


def count(num):
    cnt = 0
    while num > 0:
        if num & 1:
            cnt += 1
        num = num >> 1
    return cnt

def find(num):
    ans = 0
    while num > 0:
        ans += 1
        cnt = count(num)
        num = num % cnt
    return ans

def create(N, cnt):
    cur = 1
    two = [0] * N
    for i in range(N):
        two[i] = cur % cnt
        cur = (cur << 1) % cnt
    return two

def getRem(N, A, cnt, two):
    rem = 0
    for i in range(N):
        if A[i] == '1':
            rem = (rem + two[N - i - 1]) % cnt
    return rem

def solve():
    N = int(input())
    A = list(input().strip())

    popcount = 0
    for i in range(N):
        if A[i] == '1':
            popcount += 1
    
    more = popcount + 1
    less = popcount - 1

    if less != 0:
        less_two = create(N, less)
        rem_less = getRem(N, A, less, less_two)
    more_two = create(N, more)
    rem_more = getRem(N, A, more, more_two)
    
    nums = []
    for i in range(N):
        if A[i] == '1':
            if less == 0:
                nums.append(-1)
            else:
                nums.append((rem_less - less_two[N - i - 1]) % less)
        else:
            nums.append((rem_more + more_two[N - i - 1]) % more)
    # print(nums)

    for num in nums:
        if num == -1:
            print(0)
        else:
            print(find(num) + 1)


solve()

Submission status: Accepted

Solution code:
from sys import stdin,stdout                           #
import math                                            #
import heapq                                           #
                                                       #
t = 1                                                  #
def aint():                                            #
	return int(input().strip())                        #
def lint():                                            #
	return list(map(int,input().split()))              #
def fint():                                            #
	return list(map(int,stdin.readline().split()))     #
                                                       #	
########################################################
def f(n):
	if n==0:
		return 0
#	print(n)
	N=n
	cnt=0
	while(N):
		cnt+=N&1
		N>>=1
	return f(n%cnt)+1

def main():
	n=aint()
	x=input()
	c=x.count("1")
	if(c==0):
		for i in range(n):
			print("1")
		return
	elif(c==1):
		for i in range(n):
			if(x[i]=="1"):
				print(0)
			elif x[i]=="0":
				if x[n-1]=="1"or i==(n-1):
					print("2")
				else:
					print(1)
		return
	mod1=c+1
	mod2=c-1
	mul1=1
	mul2=1
	rem1=0
	rem2=0
	for i in range(n-1,-1,-1):
		if(x[i]=='1'):
			rem1=(rem1+mul1)%mod1
			rem2=(rem2+mul2)%mod2
		mul1=(2*mul1)%mod1
		mul2=(2*mul2)%mod2
	ans=[]
	mul1=1
	mul2=1
#	print(mod1,mod2)
#	print(rem1,rem2)
	for i in range(n-1,-1,-1):
		if(x[i]=='0'):
#			print("At index",i,"val",(rem1+mul1)%mod1)
			ans.append(f((rem1+mul1)%mod1)+1)
		else:
#			print("At index",i,"val",(rem2-mul2)%mod2)
			ans.append(f((rem2-mul2)%mod2)+1)
		mul1=(2*mul1)%mod1
		mul2=(2*mul2)%mod2
#	print("Ans:")
	for i in range(n-1,-1,-1):
		print(ans[i])
	return

#t=int(input())

########################################################
for i in range(t):                                     #
	#print("Case #"+str(i+1)+":",end=" ")		       #
	main()                                             #

Submission status: Accepted

Solution code:
def main():
    n=int(input())
    X=input().strip()
    cnt_1=X.count('1')
    k1,k2=int(X,2)%(cnt_1-1) if cnt_1!=1 else 0,int(X,2)%(cnt_1+1)
    for i,x in enumerate(X):
        ans=0
        if x=='0':
            k=k2+pow(2,n-i-1,cnt_1+1)
            k%=cnt_1+1
            ans+=1
            while k:
                num=bin(k).count('1')
                k%=num
                ans+=1
        elif x=='1' and cnt_1!=1:
            k=k1-pow(2,n-i-1,cnt_1-1)
            k%=cnt_1-1
            ans+=1
            while k:
                num=bin(k).count('1')
                k%=num
                ans+=1
        else:
            ans=0
        print(ans)
    
if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    N = int(input())
    X = input()
    t = X.count("1")
    x1, x2 = int(X, 2) % (t-1) if t != 1 else 0, int(X, 2) % (t+1)
    for i in range(N):
        ans = 0
        if X[i] == "0":
            # 反転してt += 1
            x = x2 + pow(2, N-i-1, t+1)
            x %= t+1
            ans += 1
            while x > 0:
                b = "{:0b}".format(x).count("1")
                x %= b
                ans += 1
        elif X[i] == "1" and t != 1:
            # 反転してt -= 1
            x = x1 - pow(2, N-i-1, t-1)
            x %= t-1
            ans += 1
            while x > 0:
                b = "{:0b}".format(x).count("1")
                x %= b
                ans += 1
        else:
            # X[i] == "1" and t == 1
            ans = 0
        print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

defp = int(X, 2)%plus
if minus:
    defm = int(X, 2)%minus
else:
    defm = None

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

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

Submission status: Accepted

Solution code:
def pc(x):
    return format(x, 'b').count('1')


N = int(input())
X = input()
Xo = int(X, 2)

count = 0
ans = 0
ori = pc(Xo)
X = list(X)

Xp = Xo%(ori + 1)
if ori == 1:
    Xm = 0
else:
    Xm = Xo % (ori - 1)

# for i in range(N-1, -1, -1):
for i in range(N):
    if ori == 1 and X[i] == '1':
        print(0)
        continue
    else:
        if X[i] == '1':
            # ans = Xm - pow(2, i, ori - 1)
            ans = Xm - pow(2, N-1-i, ori - 1)
            ans %= ori - 1
        else:
            # ans = Xp - pow(2, i, ori + 1)
            ans = Xp + pow(2, N-1-i, ori + 1)
            ans %= ori + 1
    count = 1
    while ans > 0:
        # count += 1
        # if ans == 1:
        #     break
        ans %= pc(ans)
        count += 1

   
    print(count)
    count = 1

Submission status: Accepted

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

cnt_x = x.count("1")
px10 = 0
nx10 = 0
ans = [0] * (N+1)

for i in range(1, N+1): #Nまで先に出しておく
    popcnt = format(i,"b").count("1")
    fx = i % popcnt
    ans[i] = ans[fx] + 1

for i in range(N):
    px10 += (int(x[i]) * pow(2,N-1-i, cnt_x+1)) % (cnt_x+1)#0⇒1となった場合の合計
    if cnt_x != 0 and cnt_x != 1:
        nx10 += int(x[i])*pow(2,N-1-i,cnt_x-1) % (cnt_x-1)#1⇒0となった場合の合計
#print(px10)
#print(nx10)
for i in range(N):
    if x[i] == "0":
        xi10 = (px10+pow(2,N-1-i,cnt_x+1))%(cnt_x+1)
        print(ans[xi10]+1)
    else:
        if cnt_x != 1:
            xi10 = (nx10-pow(2,N-1-i,cnt_x-1))%(cnt_x-1)
            print(ans[xi10]+1)
        else:
            print(0)

Submission status: Accepted

Solution code:
def f(n):
  ans=1
  while n!=0:
    ans+=1
    n%=bin(n).count("1")
  return ans
n=int(input())
x=input()
o=x.count("1")
if o==0:exit(print(*[1]*n))
if o==1:
  if x[-1]=="1":
    ans=[2]*n
    ans[-1]=0
  else:
    ans=[1]*n
    ans[-1]=2
    ans[x.index("1")]=0
  exit(print(*ans))
mo=0
mz=0
for i in range(n):
  if x[n-i-1]=="1":
    mo=(pow(2,i,o+1)+mo)%(o+1)
    mz=(pow(2,i,o-1)+mz)%(o-1)
for i in range(n):
  if x[i]=="1":
    m=(mz-pow(2,n-i-1,o-1))%(o-1)
  else:
    m=(mo+pow(2,n-i-1,o+1))%(o+1)
  print(f(m))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def main():
    N = int(input())
    X = input()
    
    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

    ans = []
   
    f = [0] * N
    # preprocess 1
    for i in range(1, N):
        pc = popcount(i)
        j =  i % pc
        f[i] = f[j] + 1
    
    # preprocess 2
    X_COUNT = X.count("1")
    X = tuple(map(int, tuple(X)))
    rem_plus = [0] * N
    rem_minus = [0] * N
    two_factor = 1
    for i in range(N):
        rem_plus[i] = two_factor
        two_factor *= 2
        two_factor %= (X_COUNT+1)

    if X_COUNT > 1:
        two_factor = 1
        for i in range(N):
            rem_minus[i] = two_factor
            two_factor *= 2
            two_factor %= (X_COUNT-1)


    X_rem_plus = 0
    X_rem_minus = 0
    two_factor = 1
    for c in X[::-1]:
        X_rem_plus += two_factor*c
        X_rem_plus %= (X_COUNT+1)
        two_factor *= 2
        two_factor %= (X_COUNT+1)
    
    if X_COUNT > 1:
        two_factor = 1
        for c in X[::-1]:
            X_rem_minus += two_factor*c
            X_rem_minus %= (X_COUNT-1)
            two_factor *= 2
            two_factor %= (X_COUNT-1)
    
    for i, c in enumerate(X):
        if c:
            if X_COUNT > 1:
                rem = X_rem_minus - rem_minus[N-1-i]
                rem %= (X_COUNT-1)
                ans.append(f[rem]+1)
            elif X_COUNT == 1:
                ans.append(0)
            else:
                ans.append(0)
        else:
            rem = X_rem_plus + rem_plus[N-1-i]
            rem %= (X_COUNT+1)
            ans.append(f[rem]+1)
   
    print(*ans, sep="\n")

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
### 解答
def popcount(X):
  pc = 0
  while X>0:
    pc += X%2
    X = X//2
  return pc

N = int(input())
B = input()
X = int(B, 2)

pcx = popcount(X)
pc0to1 = pcx + 1
pc1to0 = pcx - 1
if pc0to1 > 0:
  r0to1 = X%pc0to1
  r20to1 = [1]
  for i in range(1,N):
    r20to1.append((r20to1[-1]*2)%pc0to1)
if pc1to0 > 0:
  r1to0 = X%pc1to0
  r21to0 = [1]
  for i in range(1,N):
    r21to0.append((r21to0[-1]*2)%pc1to0)

for i in range(N):
  b = B[i]
  if b == "0":
    pc = pc0to1
  else:
    pc = pc1to0
  if pc == 0:
    print(0)
    continue

  if b == "0":
    x = r0to1 + r20to1[-(i+1)]
  else:
    x = r1to0 - r21to0[-(i+1)]
  x = x%pc

  ans = 1
  while x > 0:
    pc = popcount(x)
    x = x%pc
    ans += 1
  print(ans)

Submission status: Accepted

Solution code:
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    def solve(p):
        cur = p
        cnt = 1
        while cur > 0:
            pop = f'{cur:b}'.count("1")
            cur = cur % pop
            cnt += 1

        return cnt

    n = int(readline())
    s = input()

    c = s.count("1")
    cp = c + 1
    cm = c - 1

    fp = 0
    fm = 0

    for i, x in enumerate(s[::-1]):
        if x == "1":
            if cp <= n:
                fp += pow(2, i, cp)
                fp %= cp
            if cm > 0:
                fm += pow(2, i, cm)
                fm %= cm

    for i in range(n):
        if s[i] == "0":
            a = pow(2, n - (i + 1), cp)
            cur = (fp + a) % cp
            print(solve(cur))
        else:
            if cm > 0:
                a = pow(2, n - (i + 1), cm)
                cur = (fm - a) % cm
                print(solve(cur))
            else:
                print(0)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,copy,functools
import time,random,resource

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)
def pe(s): return print(str(s), file=sys.stderr)
def JA(a, sep): return sep.join(map(str, a))
def JAA(a, s, t): return s.join(t.join(map(str, b)) for b in a)


def main():
    n = I()
    s = S()

    m = {}
    m[0] = 0
    def f(i):
        if i in m:
            return m[i]

        c = 0
        ii = i
        while ii > 0:
            c += ii % 2
            ii //= 2

        t = i % c
        m[i] = f(t) + 1
        return m[i]

    c = len([_ for _ in s if _ == '1'])
    t = int(s, 2)
    cm = (c+1) * c * (c-1)
    if c > 1:
        t %= cm

    r = []
    k = 1
    for i in range(n-1,-1,-1):
        if t == k:
            r.append(0)
        elif s[i] == '1':
            r.append(f((t - k) % (c-1)) + 1)
        else:
            r.append(f((t + k) % (c+1)) + 1)
        k *= 2
        if c > 1:
            k %= cm

    return JA(r[::-1], "\n")


print(main())

Submission status: Accepted

Solution code:
def resolve():
    N = int(input())
    X = input()
    Xint = int(X,2)
    popX = X.count("1")
    if popX == 1:
        idx = X.find("1")
        for i in range(N):
            if i == idx:
                print(0)
            else: 
                if i != N-1:
                    if X[-1] == "0":
                        print(1)
                    else:
                        print(2)
                else:
                    print(2)
        return

    Xmod_plus =  Xint % (popX+1)
    Xmod_minus = Xint % (popX-1)

    pop_2expi_p = {0:1}
    pop_2expi_m = {0:1}
    for i in range(1,N):
        pop_2expi_p[i] = pop_2expi_p[i-1] * 2 % (popX+1)
        pop_2expi_m[i] = pop_2expi_m[i-1] * 2 % (popX-1)

    for i in range(N):
        count = 1
        if X[i] == "1":
            nX = (Xmod_minus - pop_2expi_m[N-1-i] ) % (popX-1) 
        if X[i] == "0":
            nX = (Xmod_plus + pop_2expi_p[N-1-i] ) % (popX+1) 
        for j in range(N):
            if nX == 0:
                break
            else:
                nX %= bin(nX).count("1")              
                count += 1
        print(count)
resolve()

Submission status: Accepted

Solution code:
#!/usr/bin python3
# -*- coding: utf-8 -*-

def pc(x):
    return format(x, 'b').count('1')

N = int(input())
X = input()
Xn = int(X,2)
p = pc(Xn)
X = list(X)

Xp = Xn%(p+1)
if p==1:
    Xm = 0
else:
    Xm = Xn%(p-1)

def f(i):
    if p==1 and X[i]=='1':
        #Xi == 0 > POPcount ==0
        return 0
    else:
        if X[i]=='1':
            # p->p-1
            ret = Xm - pow(2, N-1-i, p-1)
            ret %= p-1
        else:
            # p->p+1
            ret = Xp + pow(2, N-1-i, p+1)
            ret %= p+1
        cnt = 1
        while ret > 0:
            ret %= pc(ret)
            cnt += 1
        return cnt

def main():
    for i in range(N):
        ret = f(i)
        print(ret)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6)

n = int(input())
s = input()

def pcnt(x):
    return bin(x).count('1')

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

x = [0]*n

for i in range(n):
    x[i] = int(s[i])

# 元のpopcountを求める
pc = sum([x[i] for i in range(n)])

ans = [0]*n

# b: 元のbit
for b in range(2):
    npc = pc
    if b == 0: npc += 1
    else: npc -= 1
        
    if npc <= 0: continue # 0除算が発生するため
    
    # 元の数をpopcountで割ったあまりを求める
    # 例えば2進数1101を10進数に変換するには、1, 1の2倍の2に1を足して3, 3の2倍の6に0を足して6, 6の2倍に1を足して13、と計算できる。今回はこれを%npcする操作が加わる
    r0 = 0
    for i in range(n):
        r0 = (r0*2)%npc
        r0 += x[i]
    
    # 一番下の桁からループを回す
    # i桁目をフリップしたときのあまりを求める
    # 下からi桁目をフリップすると2^i変わる。その値をkとして計算する。同じループの中で2^i(k)のあまりも求める
    k = 1
    for i in range(n-1, -1, -1):
        if x[i] == b:
            r = r0
            if b == 0: r = (r+k)%npc
            else: r = (r-k+npc)%npc # r-kだけだとマイナスになることがある
            ans[i] = f(r)+1
        k = (k*2)%npc

print(*ans)

Submission status: Accepted

Solution code:
import sys
import math
import heapq
from collections import defaultdict, deque
from decimal import *
def r():
    return int(input())
def rm():
    return map(int,input().split())
def rl():
    return list(map(int,input().split()))

'''D Anything Goes to zero'''
twoPowM1=[0]*(300000)
twoPowM2=[0]*(300000)
stepsSmall=[0]*(300000)

n=r()
s=input()
bitcount=0
for i in range(n):
    if s[i]=='1':
        bitcount+=1

mod=bitcount-1
if mod>0:
    twoPowM1[0]=1
    for i in range(1,len(twoPowM1)):
        twoPowM1[i]=(twoPowM1[i-1]+twoPowM1[i-1])%mod

mod=bitcount+1
twoPowM2[0]=1
for i in range(1,len(twoPowM2)):
    twoPowM2[i]=(twoPowM2[i-1]+twoPowM2[i-1])%mod

for i in range(1,len(stepsSmall)):
    stepsSmall[i]=1+stepsSmall[i%bin(i).count('1')]

valM1=0;valM2=0
for i in range(n):
    mod=bitcount-1
    if mod>0:
        valM1=((valM1*2)%mod+int(s[i]))%mod
    mod=bitcount+1
    valM2=((valM2*2)%mod+int(s[i]))%mod

for i in range(n):
    pow=n-1-i
    if s[i]=='0':
        mod=bitcount+1
        newVal=(valM2+twoPowM2[pow])%mod
        print(stepsSmall[newVal]+1)
    else:
        mod=bitcount-1
        if mod==0:
            print(0)
        else:
            newVal=(valM1-twoPowM1[pow])%mod
            print(stepsSmall[newVal]+1)

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!

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

ones=x.count("1")

a=ones+1
b=ones-1

xda=0
xdb=0
for i in range(n):
    if x[-1-i]=="1":
        xda+=pow(2,i,a)
        xda%=a
        if b==0:
            continue
        xdb+=pow(2,i,b)
        xdb%=b

xds=[-1]*n

for i in range(n):
    if x[-1-i]=="0":
        xds[-1-i]=(xda+pow(2,i,a))%a
    else:
        if b==0:
            continue
        xds[-1-i]=(xdb-pow(2,i,b))%b

    
def popcount(x):
    return bin(x).count("1")
    
def solve(x):
    if x<0:
        return -1
    if x==0:
        return 0
    cnt=0
    while x>0:
        cnt+=1
        x=x%popcount(x)
    return cnt

for xd in xds:
    print(1+solve(xd))

Submission status: Accepted

Solution code:
#0除算
import math
def popcount(x):
    s=0
    y=int(math.log2(x))+2
    for i in range(y):
        if(x>>i)&1:
            s+=1
    return x%s
n=int(input())
x=input()[::-1]
#1がなんこ出るのか
c=x.count("1")
#c+1とc-1だけ考えれば良い
#c=1の時場合分け
#m[i][j]:2^iまで考えたときのmod(c+j-1)
if c!=1:
    m=[[1%(c-1),1%(c+1)]]
    for i in range(n-1):
        m.append([(2*m[-1][0])%(c-1),(2*m[-1][1])%(c+1)])
    l=[0,0]
    for i in range(n):
        if x[i]=="1":
            l[0]+=m[i][0]
            l[1]+=m[i][1]
            l[0]%=(c-1)
            l[1]%=(c+1)
else:
    m=[[1%(c+1),1%(c+1)]]
    for i in range(n-1):
        m.append([(2*m[-1][0])%(c+1),(2*m[-1][1])%(c+1)])
    l=[0,0]
    for i in range(n):
        if x[i]=="1":
            l[0]+=m[i][0]
            l[1]+=m[i][1]
            l[0]%=(c+1)
            l[1]%=(c+1)
#一個だけ変えたいので全体を求める

#最初以外はpopcount使って間に合う
ans=[0]*n
for i in range(n):
    if x[i]=="1":
        if c-1==0:
            ans[i]=0
            continue
        p=(l[0]+(c-1)-m[i][0])%(c-1)
        ans[i]+=1
        while p!=0:
            p=popcount(p)
            ans[i]+=1
    else:
        p=(l[1]+m[i][1])%(c+1)
        ans[i]+=1
        while p!=0:
            p=popcount(p)
            ans[i]+=1
ans=ans[::-1]
for i in range(n):
    print(ans[i])

Submission status: Accepted

Solution code:
def main():
    def f(n):
        if n == 0: return 0
        return f(n % bin(n).count('1')) + 1
    n = int(input())
    X = list(input())
    c = sum(list(map(int, X)))
    m = int(''.join(X), 2)
    mp, mm = m % (c + 1), m % (c - 1) if c - 1 != 0 else 0
    jp, jm = 1, 1
    ans = [0] * n
    for i in range(n - 1, -1, -1):
        if X[i] == '0':
            mod = c + 1
            ans[i] = f((mp + jp) % mod) + 1
        else:
            ans[i] = f((mm - jm + mod) % mod) + 1 if (mod := c - 1) != 0 else 0
        jp, jm = (jp << 1) % (c + 1), (jm << 1) % (c - 1) if c - 1 != 0 else 0
    [print(a) for a in ans]
if __name__ == '__main__':
    main()

Submission status: Accepted

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

memo = {}


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


def f(n):
    if n == 0:
        return 0
    if n in memo:
        return memo[n]
    memo[n] = 1 + f(n % popcount(n))
    return memo[n]


def solve(N, X):
    Xint = int(X, 2)
    p = popcount(Xint)
    if 1 < p:
        x1 = Xint % (p - 1)
    x2 = Xint % (p + 1)
    ans = []
    b = 1
    if 1 < p:
        bmod1 = b % (p - 1)
    bmod2 = b % (p + 1)
    for i in range(N):
        if X[-1 - i] == '1':
            if 1 < p:
                ans.append(1 + f((x1 - bmod1) % (p - 1)))
            else:
                ans.append(0)
        else:
            ans.append(1 + f((x2 + bmod2) % (p + 1)))
        b <<= 1
        if 1 < p:
            bmod1 = bmod1 * 2 % (p - 1)
        bmod2 = bmod2 * 2 % (p + 1)

    return list(reversed(ans))


for x in solve(N, X):
    print(x)

Submission status: Accepted

Solution code:
# 数のbitに含まれる1の数をカウント
def bitsoncount(x):
    return bin(x).count('1')

def solve(x):
    global ans
    bx = bitsoncount(x)
    if bx == 0:
        return ans
    else:
        ans += 1
        x = x % bx
        solve(x)


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

Xb = bitsoncount(int(X, 2))
if (Xb - 1) != 0:
    X0 = int(X, 2) % (Xb-1)
X1 = int(X, 2) % (Xb+1)

for x, i in zip(X, reversed(range(N))):
    x = int(x)
    if x == 0:
        temp = (X1 + pow(2, i, Xb+1)) % (Xb+1)
        ans = 1
    else:
        if Xb - 1 == 0:
            print(0)
            continue
        temp = (X0 - pow(2, i, Xb-1)) % (Xb-1)
        ans = 1
    
    solve(temp)
    print(ans)

Submission status: Accepted

Solution code:
from sys import stdin,stdout
def INPUT():return list(int(i) for i in stdin.readline().split())
def inp():return stdin.readline()
def out(x):return stdout.write(x)
import math
###############################################################################\
def power(a,p,m):
    if m==0:
        return 0
    res=1
    while(p>0):
        if p&1:
            res=(res*a)%m
        a=(a*a)%m
        p//=2
    return res%m
n=int(input())
s=input()
A=list(int(i) for i in s)
R=[]
for i in range(n-1,-1,-1):
    R.append(A[i])
one=0
for e in A:
    if e==1:
        one+=1
max=one+1
min=one-1
ansmax=0
ansmin=0
#print(one)
for i in range(n):
    ansmax=(ansmax+power(2,i,max)*(R[i]))%max
    if min!=0:
        ansmin=(ansmin+power(2,i,min)*R[i])%min
def popcount(z):
    ans=0
    while(z!=0):
        if z%2==1:
            ans+=1
        z//=2
    return ans
#print(ansmax,ansmin)
B=[]
for i in range(n):
    if R[i]==1:
        if min!=0:
            r=(ansmin-power(2,i,min))%min
            count=1
            while(r!=0):
                count+=1
                r=r%popcount(r)
        else:
            count=0
        B.append(count)
    else:
        r=(ansmax+power(2,i,max))%max
        count=1
        while(r!=0):
            count+=1
            r=r%popcount(r)
        B.append(count)
B.reverse()
for ele in B:
    print(ele)