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:
#! /usr/bin/env python3

import sys
import numpy as np
from functools import lru_cache
int1 = lambda x: int(x) - 1
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(500000)


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


N = int(readline())
X = readline().decode().rstrip()
X_ = int(X, 2)
X_cnt = X.count('1')
p1 = X_ % (X_cnt + 1)
m1 = X_ % (X_cnt - 1) if X_cnt > 1 else 0

for i in range(N):
    if X[i] == '0':
        cnt = X_cnt + 1
        acc = (p1 + pow(2, N - i - 1, cnt)) % cnt

    else:
        cnt = X_cnt - 1
        if cnt == 0:
            print(0)
            continue
        acc = (m1 - pow(2, N - i - 1, cnt)) % cnt
    print(f(acc) + 1)

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict, deque, Counter, OrderedDict
from functools import reduce, lru_cache
import collections, heapq, itertools, bisect
import math, fractions
import sys, copy

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI1(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline().rstrip())
def LS(): return [list(x) for x in sys.stdin.readline().split()]
def S(): return list(sys.stdin.readline().rstrip())
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
dire = [[1, 0], [0, 1], [-1, 0], [0, -1]]
dire8 = [[1, 0], [1, 1], [0, 1], [-1, 1], [-1, 0], [-1, -1], [0, -1], [1, -1]]
MOD = 1000000007

def main():
    N = I()
    X = S()
    original_popcount = X.count("1")

    upper_popcount = original_popcount + 1
    lower_popcount = original_popcount - 1

    if original_popcount == 0:
        for i in range(N):
            print(1)
        return

    if original_popcount == 1:
        for i in range(N):
            if X[-1] == "1":
                if i != N-1:
                    print(2)
                else:
                    print(0)
            else:
                if X[i] == "1":
                    print(0)
                elif i == N-1:
                    print(2)
                else:
                    print(1)
        return

    # Xが0の可能性
    upper = [0] * N
    lower = [0] * N
    upper[-1] = 1 % upper_popcount
    lower[-1] = 1 % lower_popcount

    for i in range(1, N)[::-1]:
        upper[i-1] = (2 * upper[i]) % upper_popcount
        lower[i-1] = (2 * lower[i]) % lower_popcount

    mu = 0
    ml = 0
    for i in range(N):
        if X[i] == "1":
            mu = (mu + upper[i]) % upper_popcount
            ml = (ml + lower[i]) % lower_popcount

    for i in range(N):
        if X[i] == "0":
            m = (mu + upper[i]) % upper_popcount
        else:
            m = (ml - lower[i]) % lower_popcount

        ans = 1
        while m:
            tmp = m
            ones = 0
            while tmp:
                if tmp & 1 == 1:
                    ones += 1
                tmp //= 2
            m %= ones
            ans += 1

        print(ans)



if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import copy
n=int(input())
x=list(input())
b=[]
for i in range(2**18):
  b.append(format(i,'0'+str(18)+'b'))
  if i>n+1:
    break
ct=[0]*(n+1)
for i in range(1,n):
  ct1=0
  for j in range(len(b[i])):
    if b[i][j]=='1':
      ct1+=1
  ct[i]=i%ct1

CT=0
for i in range(n):
  if x[i]=='1':
    CT+=1

moda=[1]
modb=[1]
modc=[1]
for i in range(n-1):
  if CT>=2:
    moda.append(moda[-1]*2%(CT-1))
  if CT>=1:
    modb.append(modb[-1]*2%CT)
  modc.append(modc[-1]*2%(CT+1))


x.reverse()
za=0
zb=0
zc=0
for i in range(n):
  if x[i]=='1':
    if CT>=2:
      za+=moda[i]
      za%=(CT-1)
    if CT>=1:
      zb+=modb[i]
      zb%=CT
    zc+=modc[i]
    zc%=(CT+1)
x.reverse()
moda.reverse()
modc.reverse()

for i in range(n):
  y2=x[i]
  if y2=='1':
    ct1=CT-1
  else:
    ct1=CT+1
  if ct1==0:
    print(0)
  else:
    if y2=='1':
      z=za
      z-=moda[i]
      z%=ct1
    else:
      z=zc
      z+=modc[i]
      z%=ct1
    
    ans=1
    while z!=0:
      z=ct[z]
      ans+=1
    print(ans)

Submission status: Accepted

Solution code:
n=int(input())
x=input()
p=x.count("1")
Ma=[1]+[0]*(n-1)
Mb=[1]+[0]*(n-1)
for i in range(1,n):
  if p>1:
    Ma[i]=Ma[i-1]*2%(p-1)
  else:
    Ma[i]=0
    Ma[0]=0
  Mb[i]=Mb[i-1]*2%(p+1)
Sa=Sb=0
for i in range(n):
  if x[i]=="1":
    Sa+=Ma[n-1-i]
    Sb+=Mb[n-1-i]
for i in range(n):
  a=0
  if x[i]=="1":
    if p==1:
      s=0
    else:
      s=(Sa-Ma[n-1-i])%(p-1)
      a+=1
  else:
    s=(Sb+Mb[n-1-i])%(p+1)
    a+=1
  while(s>0):
    t=0
    r=s
    while(r>0):
      t+=r&1
      r//=2
    s%=t
    a+=1
  print(a)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000000)
def popcount(x):
    '''xの立っているビット数をカウントする関数
    (xは64bit整数)'''

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

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

    x = (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f # 8bitごと
    x = x + (x >> 8) # 16bitごと
    x = x + (x >> 16) # 32bitごと
    x = x + (x >> 32) # 64bitごと = 全部の合計
    return x & 0x0000007f
def main():
    N = int(input())
    X = input()
    d = {}
    dd = {}
    x1 = X.count('1')
    xn = int(X, 2)
    def hoge(i):
        if i in dd:
            return dd[i]
        if i not in d:
            j = popcount(i)
            d[i] = i % j
            if d[i] == 0:
                dd[i] = 1
            else:
                dd[i] = 1 + hoge(d[i])
        return dd[i]
    if N == 1:
        if X == '1':
            print(0)
            return 0
        else:
            print(1)
            return 1
    if x1 == 1:
        xn1 = 0
    else:
        xn1 = xn % (x1-1)
    xn2 = xn % (x1 + 1)
    for i in range(N):
        if X[i] == '1':
            t = xn1
            if x1-1 == 0:
                print(0)
                continue
            t -= pow(2, N-1-i, x1-1)
            t %= (x1-1)
        else:
            t = xn2
            t += pow(2, N-1-i, x1+1)
            t %= (x1 + 1)
        if t == 0:
            print(1)
        else:
            print(1 + hoge(t))
main()

Submission status: Accepted

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


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


if __name__ == '__main__':
    main()

Submission status: Accepted

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


n=int(input())
X=str(input())

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



def culc(x):
    bin_x=str(bin(x)[2:])
    one=0
    for i in range(len(bin_x)):
        if bin_x[i]=='1':
            one+=1
    return x%one
        



#dp[i](0<=i<=number)
dp=[-1]*(number+1)
dp[0]=0
def rec(x):
    if dp[x]>=0:
        return dp[x]
    else:
        dp[x]=rec(culc(x))+1
        return dp[x]



if number==0:
    for i in range(n):
        print(1)
    sys.exit()



base1=0
for i in range(n):
    if X[i]=='1':
        base1=(base1+pow(2,n-i-1,number+1))%(number+1)

if number==1:
    for i in range(n):
        if X[i]=='1':
            print(0)
        else:
            temp=(base1+pow(2,n-i-1,number+1))%(number+1)
            ans=rec(temp)+1
            print(ans)
    sys.exit()



base2=0
for i in range(n):
    if X[i]=='1':
        base2=(base2+pow(2,n-i-1,number-1))%(number-1)






for i in range(n):
    #base1
    if X[i]=='0':
        temp=(base1+pow(2,n-i-1,number+1))%(number+1)
        ans=rec(temp)+1
        print(ans)
    #base2
    if X[i]=='1':
        temp=(base2-pow(2,n-i-1,number-1))%(number-1)
        ans=rec(temp)+1
        print(ans)

Submission status: Accepted

Solution code:
def fast_powmod(n, m):
    pow2 = 2
    result = 1
    while n > 0:
        if n % 2 == 1:
            result = (result * pow2) % m
        pow2 = (pow2 * pow2) % m
        n >>= 1

    return result

def popcnt3(n):
    c = (n & 0x5555555555555555) + ((n>>1) & 0x5555555555555555)
    c = (c & 0x3333333333333333) + ((c>>2) & 0x3333333333333333)
    c = (c & 0x0f0f0f0f0f0f0f0f) + ((c>>4) & 0x0f0f0f0f0f0f0f0f)
    c = (c & 0x00ff00ff00ff00ff) + ((c>>8) & 0x00ff00ff00ff00ff)
    c = (c & 0x0000ffff0000ffff) + ((c>>16) & 0x0000ffff0000ffff)
    c = (c & 0x00000000ffffffff) + ((c>>32) & 0x00000000ffffffff)
    return c

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

res = dict()
res[1] = 1
res[2] = 1
for i in range(3, 2 * 10**5 + 1):
    val = i % popcnt3(i)
    if val == 0:
        res[i] = 1
    else:
        res[i] = res[val] + 1

count = 0
for i in x:
    if i == "1":
        count += 1

x = x[::-1]
small = 0
big = 0
for i in range(len(x)):
    if x[i] == "1":
        if count - 1 != 0:
            small += fast_powmod(i, count - 1)
        big += fast_powmod(i, count + 1)

try:
    small %= count - 1
except:
    small = 0
big %= count + 1

anse = []
for i in range(len(x)):
    if x[i] == "1":
        done = False
        ans = 0
        if count - 1 == 0:
            anse.append(0)
        else:
            cur = small - fast_powmod(i, count - 1)
            cur %= count - 1
            if cur == 0:
                anse.append(1)
            else:
                anse.append(res[cur] + 1)
    else:
        done = False
        ans = 0
        cur = big + fast_powmod(i, count + 1)
        cur %= count + 1
        if cur == 0:
            anse.append(1)
        else:
            anse.append(res[cur] + 1)


for i in anse[::-1]:
    print(i)
                
        
        
# print(small, big)

Submission status: Accepted

Solution code:
n=int(input())
s=[int(c) for c in input()]

pc=sum(s)

resm=[0]*n
resp=[0]*n

jm=1
jp=1

totm=0
totp=0
for i in range(n):
    if pc-1>0:
        resm[n-i-1]=jm%(pc-1)
        jm=(2*jm)%(pc-1)
        totm+=resm[n-i-1]*s[n-i-1]
        totm%=pc-1
    
    resp[n-i-1]=jp%(pc+1)
    jp=(2*jp)%(pc+1)
    totp+=resp[n-i-1]*s[n-i-1]
    totp%=pc+1

def popc(x):
    return sum([int(c) for c in format(x,'b')])

for i in range(n):
    if s[i]==1:
        pcc=pc-1
        if pcc==0:
            print(0)
            continue
        cres=(totm+pc-1-resm[i])%(pc-1)
    else:
        pcc=pc+1
        cres=(totp+resp[i])%(pc+1)
    
    if cres==0:
        print(1)
        continue

    cnt=1
    while cres>0:
        cres%=popc(cres)
        cnt+=1
    
    print(cnt)

Submission status: Accepted

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

xre = x[::-1]

cou = x.count('1')

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

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

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

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


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

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


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

Submission status: Accepted

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

def pop(x): #10進数
    ret=0
    while x>0:
        ret+=x%2
        x//=2
    return ret

def solve(x): #10進数
    ret=0
    while x>0:
        pop_c=pop(x)
        x%=pop_c
        ret+=1
    return ret

mod=X.count("1") #>0
original_plus=0
original_minus=0
for i in range(N):
    if X[N-1-i]=="1":
        if mod>1:
            original_minus+=pow(2,i,mod-1)
        original_plus+=pow(2,i,mod+1)
for i in range(N):
    if X[i]=="0":
        tmp=original_plus+pow(2,N-1-i,mod+1)
        tmp%=mod+1
        print(solve(tmp)+1)
    else:
        if mod==1:
            print(0)
            continue
        tmp=original_minus-pow(2,N-1-i,mod-1)
        tmp%=mod-1
        print(solve(tmp)+1)

Submission status: Accepted

Solution code:
def main():
    N = int(input())
    S = input()
    X = int(S, 2)
    C = S.count('1')
    xc0 = X % (C + 1)
    xc1 = X % (C - 1) if C > 1 else 0
 
    def f(x):
        c = 0
        while x:
            c += 1
            x = x % bin(x).count('1')
        return c
 
    for i, s in enumerate(S):
        k = N - 1 - i
        if s == '0':
            print(f((xc0 + pow(2, k, C + 1)) % (C + 1)) + 1)
        else:
            if C > 1:
                print(f((xc1 - pow(2, k, C - 1)) % (C - 1)) + 1)
            else:
                print(0)
 
 
main()

Submission status: Accepted

Solution code:
import sys

input = sys.stdin.readline

n = int(input())
y = str(input())
# n = 10**5
# y  = '1' * n
ones = 0
for i in y:
    if i == '1': ones += 1
x = int(y, 2)

def get(z):
    ret = 0
    while z > 0:
        if z % 2 == 1:
            ret += 1
        z //= 2
    return ret

out = []
rem1 = -1
rem2 = -1
if ones > 1:
    rem1 = x % (ones - 1)
if ones < n:
    rem2 = x % (ones + 1)

def calc(p, m):
    if p <= 2:
        return (1 << p) % m
    a = p // 2
    ret = calc(a, m)
    ret = (ret * ret) % m
    if p % 2 == 1:
        ret = (ret * 2) % m
    return ret



for i in range(n):
    # tmp = (1 << i) * -1
    o = ones - 1
    if y[n - i - 1] == '0':
        # tmp = 1 << i
        o = ones + 1

    # tmp = tmp + x
    if o == 0:
        out.append(0)
        continue
    if o == 1:
        out.append(1)
        continue


    if o > ones:
        tmp = (rem2 % o + calc(i, o)) % o
    else:
        tmp = (rem1 % o - calc(i, o) + o) % o


    cnt = 1
    while tmp > 0:
        tmp %= get(tmp)
        cnt += 1

    out.append(cnt)

for i in range(n):
    print(out[n-i-1])

Submission status: Accepted

Solution code:
import sys, math
import io, os
#data = io.BytesIO(os.read(0,os.fstat(0).st_size)).readline
#from bisect import bisect_left as bl, bisect_right as br, insort
#from heapq import heapify, heappush, heappop
from collections import defaultdict as dd, deque, Counter
#from itertools import permutations,combinations
def data(): return sys.stdin.readline().strip()
def mdata(): return list(map(int, data().split()))
def outl(var) : sys.stdout.write('\n'.join(map(str, var))+'\n')
def out(var) : sys.stdout.write(str(var)+'\n')
#from decimal import Decimal
#from fractions import Fraction
#sys.setrecursionlimit(100000)
#INF = float('inf')
mod = int(1e9)+7

n=int(data())
x=data()
c=x.count('1')
t1,t2=1,1
k1=0
k2=0
for i in range(n-1,-1,-1):
    if x[i]=='1':
        k1=(k1+t1)%(c+1)
        if c==1:
            continue
        k2=(k2+t2)%(c-1)
    t1=(t1*2)%(c+1)
    if c != 1:
        t2=(t2*2)%(c-1)
ans=[]
t1,t2=1,1
for i in range(n-1,-1,-1):
    if x[i]=='1':
        if c==1:
            ans.append(0)
            continue
        k=(k2-t2+c-1)%(c-1)
    else:
        k=(k1+t1)%(c+1)
    cnt=1
    while k:
        k=k%(bin(k)[2:].count('1'))
        cnt+=1
    ans.append(cnt)
    t1 = (t1 * 2) % (c + 1)
    if c!=1:
        t2 = (t2 * 2) % (c - 1)
outl(ans[::-1])

Submission status: Accepted

Solution code:
'''Author- Akshit Monga'''
n=int(input())
x=input()
x=x[::-1]
ans1=0
ans2=0
c=x.count('1')
for i in range(0,n):
    if x[i]=='1':
        ans1=(ans1+pow(2,i,c+1))%(c+1)
        if c!=1:
            ans2=(ans2+pow(2,i,c-1))%(c-1)
to_print=[]
for i in range(0,n):
    if x[i]=='1':
        if c==1:
            to_print.append(0)
            continue
        var=(ans2%(c-1)-pow(2,i,c-1))%(c-1)
        a = 1
        while var:
            var = var % bin(var).count('1')
            a += 1
        to_print.append(a)
    else:
        # print(ans1)
        var = (ans1%(c+1) + pow(2, i, c +1))%(c+1)
        # print(c+1)
        # print(var)
        a = 1
        while var:
            var = var % bin(var).count('1')
            a += 1
        to_print.append(a)
for i in to_print[::-1]:
    print(i)

Submission status: Accepted

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

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

v=a.count('1')

ans=[0]*n
A=[0]*n
# n以下の残り回数を記録
for i in range(n):
    x=i
    cnt=0
    while x>0:
        cnt+=1
        r = 0
        for j in range(19):
            if (x>>j)&1:
                r+=1
            if x>>j==0:
                break
        x=x%r
    ans[i]=cnt

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

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

for i in A:
    print(i)

Submission status: Accepted

Solution code:
N = int(input())
X = input().strip()
C = X.count("1")
D = int(X, 2)
Mm, Mp = 0, D % (C+1)
if C > 1:
    Mm = D % (C-1)

p = [0]*(2*10**5+2)
for i in range(1, len(p)):
    n = i
    while True:
        b = bin(n).count("1")
        if b <= 0:
            break
        p[i] += 1
        n = n % b

for i in range(1, N+1):
    c = C
    if X[i-1] == "1":
        c -= 1
        if c == 0:
            print(0)
            continue
        m = Mm
        d = pow(2, N-i, c)
        d = (m-d+c) % c
    else:
        c += 1
        m = Mp
        d = pow(2, N-i, c)
        d = (m+d) % c

    print(p[d]+1)

Submission status: Accepted

Solution code:
n = int(input())
x = list(map(int, input()))

dp = [0] * n

for i in range(n):
    num = i
    while num:
        num2 = num
        cnt = 0
        while num2:
            if num2 & 1:
                cnt += 1
            num2 >>= 1

        num %= cnt
        dp[i] += 1

one_cnt = x.count(1)
mod1 = one_cnt - 1
mod2 = one_cnt + 1

sm1 = 0
sm2 = 0
for i, e in enumerate(x):
    if e == 0:
        continue

    if mod1 != 0:
        sm1 += pow(2, n - i - 1, mod1)
        sm1 %= mod1

    sm2 += pow(2, n - i - 1, mod2)
    sm2 %= mod2

for i, e in enumerate(x):
    if mod1 == 0 and e:
        print(0)
        continue

    if e:
        val = sm1 - pow(2, n - i - 1, mod1)
        val %= mod1

    else:
        val = sm2 + pow(2, n - i - 1, mod2)
        val %= mod2

    ans = dp[val] + 1
    print(ans)

Submission status: Accepted

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

memo = [0]*n
ans = [-1]*n
popcnt = 0

for i in range(n):
    if x[i] == "1":
        popcnt += 1

amariStaticA = 0
amariStaticB = 0
aaa = -1
if popcnt == 1:
    for i in range(n):
        if x[i] == "1":
            ans[i] = 0
            aaa = i
            amariStaticB += pow(2, n-i-1, popcnt+1)
    amariStaticB %= popcnt+1
else:
    for i in range(n):
        if x[i] == "1":
            amariStaticA += pow(2, n-i-1, max(1, popcnt-1))
            amariStaticB += pow(2, n-i-1, popcnt+1)
    amariStaticA %= max(1, popcnt-1)
    amariStaticB %= popcnt+1

for i in range(n):
    if popcnt == 1 and i == aaa:
        continue
    if x[i] == "0":
        amari = amariStaticB + pow(2, n-i-1, popcnt+1)
        amari %= popcnt+1
    else:
        amari = amariStaticA - pow(2, n-i-1, max(1, popcnt-1))
        amari %= max(1, popcnt-1)
    if amari == 0:
        ans[i] = 1
    else:
        memo[i] = amari

for i in range(len(memo)):
    cnt = 1
    firstMemo = copy.deepcopy(memo[i])
    while memo[i] != 0:
        popcnt = bin(memo[i]).count("1")
        memo[i] %= max(1, popcnt)
        cnt += 1
        if memo[i] == 0:
            ans[i] = cnt
            break


for anss in ans:
    print(anss)

Submission status: Accepted

Solution code:
import collections
N=int(input())
X=list(input())
X=list(map(int,X))
#print(X)
ans1=0
ans2=0
c=collections.Counter(X)
div=c[1]
for i in range(N):
    ans1=(ans1+X[i]*pow(2,N-i-1,div+1))%(div+1)
    if div-1!=0:
        ans2=(ans2+X[i]*pow(2,N-i-1,div-1))%(div-1)
    else:
        ans2=None
    #print(ans1)
#print(ans1,div+1)
#print(ans2,div-1)
#ここまででXについてのXのbit数、X%(Xのbit数)がわかる
for i in range(N):
    cnt = 1
    if (X[i]==0):
        num=(ans1+pow(2,N-i-1,div+1))%(div+1)
        #print(num)
    else:
        if (div-1)!=0:
            num=(ans2+div-1-pow(2,N-i-1,div-1))%(div-1)
        else:
            cnt=0
            num=0
        #print(num)
    while num != 0:
        di = 0
        for j in range(18):
            if (num >> j)&1 == 1:
                di = di + 1
        num = num % di
        cnt = cnt + 1
    print(cnt)

Submission status: Accepted

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

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


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

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

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

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

Submission status: Accepted

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

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n = I()
x = input()
b = []
c = [0, 1, 1]
for i in range(n+2):
    cnt = 0
    for j in range(101):
        if i >> j & 1:
            cnt += 1
    b.append(cnt)

for i in range(3, n+2):
    c.append(c[i % b[i]]+1)

ans = []
tmp1 = 0
tmp2 = 0
cnt = x.count("1")
if cnt != 1:
    for i in range(n):
        if x[i] == "1":
            tmp1 += pow(2, n-(i+1), cnt+1)
            tmp2 += pow(2, n-(i+1), cnt-1)
    for i in range(n):
        if x[i] == "1":
            ans.append(c[(tmp2 - pow(2, n-(i+1), cnt-1)) % (cnt-1)]+1)
        else:
            ans.append(c[(tmp1 + pow(2, n-(i+1), cnt+1)) % (cnt+1)]+1)

    for i in ans:
        print(i)
else:
    for i in range(n):
        if x[i] == "1":
            tmp1 += pow(2, n-(i+1), cnt+1)
    for i in range(n):
        if x[i] == "1":
            ans.append(0)
        else:
            ans.append(c[(tmp1 + pow(2, n-(i+1), cnt+1)) % (cnt+1)]+1)

    for i in ans:
        print(i)

Submission status: Accepted

Solution code:
N = int(input())
X = input()
times = {}
times[0] = 0

for i in range(1,200000):
  bi = format(i, 'b')
  arr = list(map(int, bi))
  sbi = sum(arr)
  if i%sbi == 0:
    times[i] = 1
  else:
    times[i] = 1+times[i%sbi]
    
arr = list(map(int, X))
sbX = sum(arr)
X10 = int(X,2)
mo = [1,-1]
if sbX-1 == 0:
  mo2 = [X10%(sbX+1),X10]
else:
  mo2 = [X10%(sbX+1),X10%(sbX-1)]

for i in range(N):
  waru = sbX+mo[int(X[i])]
  if waru == 0:
    print(0)
  else:
    print(times[(mo[int(X[i])]*pow(2,(N-i-1),waru)+mo2[int(X[i])])%waru]+1)

Submission status: Accepted

Solution code:
# input()
# int(input())
# map(int, input().split())
# list(map(int, input().split()))
# list(map(int, list(input()))) # スペースがない数字リストを読み込み
import math
import fractions
import sys
import bisect
import heapq  # 優先度付きキュー(最小値取り出し)
import collections
from collections import Counter
from collections import deque
import pprint
import itertools

sr = lambda: input()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

"""nを素因数分解"""
"""2以上の整数n => [[素因数, 指数], ...]の2次元リスト"""


def factorization(n):
    arr = []
    temp = n
    if n == 1:
        return arr

    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


# a^n
def power(a, n, mod):
    x = 1
    while n:
        if n & 1:
            x *= a % mod
        n >>= 1
        a *= a % mod
    return x % mod


# n*(n-1)*...*(l+1)*l
def kaijo(n, l, mod):
    if n == 0:
        return 1
    a = n
    tmp = n - 1
    while (tmp >= l):
        a = a * tmp % mod
        tmp -= 1
    return a

# Union Find
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

# 約数生成
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)

    divisors.sort()
    return divisors


inf = 10 ** 18
mod = 10 ** 9 + 7

n = ir()
x = list(sr())
sum1 = 0
for c in x:
    if c == '1':
        sum1+=1
tmpp = 0
tmpm = 0
for c in x:
    tmpp = tmpp*2
    tmpm = tmpm*2
    if c == '1':
        tmpp+=1
        tmpm+=1
    tmpp%=(sum1+1)
    if sum1 != 1:
        tmpm%=(sum1-1)
    else:
        tmpm = 0
dpp = [0 for i in range(n)]
dpm = [0 for i in range(n)]
mmp = 1
mmm = 0
if sum1 != 1:
    mmm = 1
for i in range(n):
    dpp[n-1-i] = mmp
    dpm[n-1-i] = mmm
    mmp = (mmp*2)%(sum1+1)
    if sum1 != 1:
        mmm = (mmm*2)%(sum1-1)
    else:
        mmm = 0
ansdp = [0 for i in range(n)]
ans = [0 for i in range(n)]
# 1回目の操作
for i,c in enumerate(x):
    if c == '1':
        if sum1 != 1:
            ansdp[i] = (tmpm-dpm[i])%(sum1-1)
            ans[i]+=1
    else:
        ansdp[i] = (tmpp+dpp[i])%(sum1+1)
        ans[i]+=1
while 1:
    end = True
    for c in ansdp:
        if c != 0:
            end = False
    if not end:
        for i in range(n):
            if ansdp[i] != 0:
                tmp = bin(ansdp[i])
                sum11 = 0
                for c in tmp:
                    if c == '1':
                        sum11+=1
                ansdp[i] = ansdp[i]%sum11
                ans[i]+=1
    else:
        for num in ans:
            print(num)
        sys.exit()