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: Time Limit Exceeded

Solution code:
N = int(input())
sX = input()
 
origin_count = sX.count('1')
one_r_count = origin_count -1
zero_r_count = origin_count +1
 
one_mod = 0
zero_mod =0
for b in sX:
    if one_r_count != 0:
        one_mod = (one_mod * 2) + int(b) % one_r_count
    zero_mod = (zero_mod * 2 ) + int(b) % zero_r_count
 
f = [0] * 220000
pop = [0]* 220000
 
for i in range(1,220000):
    pop[i] = pop[i//2] + i%2
    f[i] = f[i % pop[i]] + 1
    
onepow = [1] * 220000
zeropow = [1]* 220000
 
for i in range(1,220000):
    if one_r_count != 0:
        onepow[i] = onepow[i-1] * 2 % one_r_count
    zeropow[i] = zeropow[i-1] * 2 % zero_r_count
 
for i in range(1,N+1):
    if sX[i-1] == '1':
        if one_r_count != 0:
            Xi_n = one_mod - onepow[N-i]
            Xi_n %= one_r_count
            print(f[Xi_n]+1)
        else:
            print(0)
    else:
        Xi_n = zero_mod + zeropow[N-i]
        Xi_n %= zero_r_count
        print(f[Xi_n]+1)

Submission status: Time Limit Exceeded

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

X_1 = bin(int(X, 2)).count('1')


for i in range(N):
  
  X_list = list(X)
  if X_list[i] == '0':
    X_list[i] = '1'
    first = X_1 + 1
  else:
    X_list[i] = '0'
    first = X_1 - 1
  
  X_str = ''.join(X_list)
  n = int(X_str, 2)
  fn = 0
  if n != 0:
    n = n % first
    fn += 1
  while n != 0:
    n = n % bin(n).count('1')
    fn += 1
  
  print(fn)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
sX = input()
 
origin_count = sX.count('1')
one_r_count = origin_count -1
zero_r_count = origin_count +1
 
one_mod = 0
zero_mod =0
for b in sX:
    if one_r_count != 0:
        one_mod = (one_mod * 2) + int(b) % one_r_count
    zero_mod = (zero_mod * 2 ) + int(b) % zero_r_count
 
f = [0] * 220000
pop = [0]* 220000
 
for i in range(1,220000):
    pop[i] = pop[i//2] + i%2
    f[i] = f[i % pop[i]] + 1
 
onepow = [1] * 220000
zeropow = [1]* 220000
 
for i in range(1,220000):
    if one_r_count != 0:
        onepow[i] = onepow[i-1] * 2 % one_r_count
    zeropow[i] = zeropow[i-1] * 2 % zero_r_count
 
for i in range(1,N+1):
    if sX[i-1] == '1':
        if one_r_count != 0:
            Xi_n = one_mod - onepow[N-i]
            Xi_n %= one_r_count
            print(f[Xi_n]+1)
        else:
            print(0)
    else:
        Xi_n = zero_mod + zeropow[N-i]
        Xi_n %= zero_r_count
        print(f[Xi_n]+1)

Submission status: Time Limit Exceeded

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

def popcount(n):
    #ret = 0
    #while n >= 1:
    #    r = n // 2
    #    q = n % 2
    #    if q == 1:
    #        ret += 1
    #    n = r
    ret = bin(n).count("1")
    return ret

def ff(n):
    d = popcount(n)
    q = n % d
    return q

def f(n):
    count = 0
    while True:
        if n == 0:
            return count
        count += 1
        n = ff(n)

def power(n, r):
    #if r == 0: return 1
    #if r%2 == 0:
    #    ret = power(n*n, r//2)
    #if r%2 == 1:
    #    ret = n * power(n, r-1)
    ret = n ** r
    return ret

n = int(input())
x_str = input()
x = int(x_str, 2) 

xpop = x_str.count("1")
xpop_p1 = xpop + 1
x1_p1 = x % xpop_p1

if xpop >= 2:
    xpop_m1 = xpop - 1
    x1_m1 = x % xpop_m1
else:
    x1_m1 = None

#print("x", x)
#print("xpop", xpop)
#print(x1_p1, x1_m1)
#print(xpop_p1, xpop_m1)

for i, c in enumerate(x_str):
    shisuu = n - i -1

    #atai = 2 ** shisuu
    atai = power(2, shisuu)
    if c == "1":
        if xpop == 1:
            atai = 0
            xx = None
        else:
            atai = atai % xpop_m1
            xx = x1_m1
            xx = (x1_m1 - atai) % xpop_m1
    else:
        atai = atai % xpop_p1
        #print("atai", atai)
        xx = (x1_p1 + atai) % xpop_p1
    #print("xx", xx)
    if xx is not None:
        count = f(xx)
        out = 1 + count
    else:
        out = 0
    print(out)

Submission status: Time Limit Exceeded

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

def popcount(n):
    #ret = 0
    #while n >= 1:
    #    r = n // 2
    #    q = n % 2
    #    if q == 1:
    #        ret += 1
    #    n = r
    ret = bin(n).count("1")
    return ret

def ff(n):
    d = popcount(n)
    q = n % d
    return q

def f(n):
    count = 0
    while True:
        if n == 0:
            return count
        count += 1
        n = ff(n)

def power(n, r):
    if r == 0: return 1
    if r%2 == 0:
        ret = power(n*n, r//2)
    if r%2 == 1:
        ret = n * power(n, r-1)
    return ret

n = int(input())
x_str = input()
x = int(x_str, 2) 

xpop = x_str.count("1")
xpop_p1 = xpop + 1
x1_p1 = x % xpop_p1

if xpop >= 2:
    xpop_m1 = xpop - 1
    x1_m1 = x % xpop_m1
else:
    x1_m1 = None

#print("x", x)
#print("xpop", xpop)
#print(x1_p1, x1_m1)
#print(xpop_p1, xpop_m1)

for i, c in enumerate(x_str):
    shisuu = n - i -1

    #atai = 2 ** shisuu
    atai = power(2, shisuu)
    if c == "1":
        if xpop == 1:
            atai = 0
            xx = None
        else:
            atai = atai % xpop_m1
            xx = x1_m1
            xx = (x1_m1 - atai) % xpop_m1
    else:
        atai = atai % xpop_p1
        #print("atai", atai)
        xx = (x1_p1 + atai) % xpop_p1
    #print("xx", xx)
    if xx is not None:
        count = f(xx)
        out = 1 + count
    else:
        out = 0
    print(out)

Submission status: Time Limit Exceeded

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

origin_count = sX.count('1')
one_r_count = origin_count -1
zero_r_count = origin_count +1

one_mod = 0
zero_mod =0
for b in sX:
    if one_r_count != 0:
        one_mod = (one_mod * 2) + int(b) % one_r_count
    zero_mod = (zero_mod * 2 ) + int(b) % zero_r_count

f = [0] * 220000
pop = [0]* 220000

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

onepow = [1] * 220000
zeropow = [1]* 220000

for i in range(1,220000):
    if one_r_count != 0:
        onepow[i] = onepow[i-1] * 2 % one_r_count
    zeropow[i] = zeropow[i-1] * 2 % zero_r_count

for i in range(1,N+1):
    if sX[i-1] == '1':
        if one_r_count != 0:
            Xi_n = one_mod - onepow[N-i]
            Xi_n %= one_r_count
            print(f[Xi_n]+1)
        else:
            print(0)
    else:
        Xi_n = zero_mod + zeropow[N-i]
        Xi_n %= zero_r_count
        print(f[Xi_n]+1)

Submission status: Time Limit Exceeded

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

def popcount(n):
    ret = 0
    while n >= 1:
        r = n // 2
        q = n % 2
        if q == 1:
            ret += 1
        n = r
    #ret = bin(n).count("1")
    return ret

def ff(n):
    d = popcount(n)
    q = n % d
    return q

def f(n):
    count = 0
    while True:
        if n == 0:
            return count
        count += 1
        n = ff(n)

n = int(input())
x_str = input()
x = int(x_str, 2) 

xpop = x_str.count("1")
xpop_p1 = xpop + 1
x1_p1 = x % xpop_p1

if xpop >= 2:
    xpop_m1 = xpop - 1
    x1_m1 = x % xpop_m1
else:
    x1_m1 = None

#print("x", x)
#print("xpop", xpop)
#print(x1_p1, x1_m1)
#print(xpop_p1, xpop_m1)

for i, c in enumerate(x_str):
    shisuu = n - i -1

    atai = 2 ** shisuu
    if c == "1":
        if xpop == 1:
            atai = 0
            xx = None
        else:
            atai = atai % xpop_m1
            xx = x1_m1
            xx = (x1_m1 - atai) % xpop_m1
    else:
        atai = atai % xpop_p1
        #print("atai", atai)
        xx = (x1_p1 + atai) % xpop_p1
    #print("xx", xx)
    if xx is not None:
        count = f(xx)
        out = 1 + count
    else:
        out = 0
    print(out)

Submission status: Time Limit Exceeded

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

def popcount(n):
    ret = bin(n).count("1")
    return ret

def ff(n):
    d = popcount(n)
    q = n % d
    return q

def f(n):
    count = 0
    while True:
        if n == 0:
            return count
        count += 1
        n = ff(n)

n = int(input())
x_str = input()
x = int(x_str, 2) 

xpop = x_str.count("1")
xpop_p1 = xpop + 1
x1_p1 = x % xpop_p1

if xpop >= 2:
    xpop_m1 = xpop - 1
    x1_m1 = x % xpop_m1
else:
    x1_m1 = None

#print("x", x)
#print("xpop", xpop)
#print(x1_p1, x1_m1)
#print(xpop_p1, xpop_m1)

for i, c in enumerate(x_str):
    shisuu = n - i -1

    atai = 2 ** shisuu
    if c == "1":
        if xpop == 1:
            atai = 0
            xx = None
        else:
            atai = atai % xpop_m1
            xx = x1_m1
            xx = (x1_m1 - atai) % xpop_m1
    else:
        atai = atai % xpop_p1
        #print("atai", atai)
        xx = (x1_p1 + atai) % xpop_p1
    #print("xx", xx)
    if xx is not None:
        count = f(xx)
        out = 1 + count
    else:
        out = 0
    print(out)

Submission status: Time Limit Exceeded

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

origin_count = sX.count('1')
one_r_count = origin_count -1
zero_r_count = origin_count +1

one_mod = 0
zero_mod =0
for b in sX:
    if(one_r_count != 0):
        one_mod = (one_mod * 2) + int(b) % one_r_count
    zero_mod = (zero_mod * 2 ) + int(b) % zero_r_count

f = [0] * 220000
pop = [0]* 220000

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

onepow = [1] * 220000
zeropow = [1]* 220000

for i in range(1,220000):
    if(one_r_count != 0):
        onepow[i] = onepow[i-1] * 2 % one_r_count
    zeropow[i] = zeropow[i-1] * 2 % zero_r_count

for i in range(1,N+1):
    if(sX[i-1] == '1'):
        if(one_r_count != 0):
            Xi_n = one_mod - onepow[N-i]
            Xi_n %= one_r_count
            print(f[Xi_n]+1)
        else:
            print(0)
    else:
        Xi_n = zero_mod + zeropow[N-i]
        Xi_n %= zero_r_count
        print(f[Xi_n]+1)

Submission status: Time Limit Exceeded

Solution code:
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

for i in range(N):
  
  X_list = list(X)
  if X_list[i] == '0':
    X_list[i] = '1'
  else:
    X_list[i] = '0'
  
  X_str = ''.join(X_list)
  n = int(X_str, 2)
  fn = 0
  while n != 0:
    n = n % bin(n).count('1')
    fn += 1
  
  print(fn)

Submission status: Time Limit Exceeded

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

origin_count = sX.count('1')
one_r_count = origin_count -1
zero_r_count = origin_count +1

one_mod = 0
zero_mod =0
for i in range(N):
    if(one_r_count != 0):
        one_mod = (one_mod * 2) + int(sX[i]) % one_r_count
    zero_mod = (zero_mod * 2 ) + int(sX[i]) % zero_r_count

f = [0] * 220000
pop = [0]* 220000

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

onepow = [1] * 220000
zeropow = [1]* 220000

for i in range(1,220000):
    if(one_r_count != 0):
        onepow[i] = onepow[i-1] * 2 % one_r_count
    zeropow[i] = zeropow[i-1] * 2 % zero_r_count

for i in range(1,N+1):
    if(sX[i-1] == '1'):
        if(one_r_count != 0):
            Xi_n = one_mod - onepow[N-i]
            Xi_n %= one_r_count
            print(f[Xi_n]+1)
        else:
            print(0)
    else:
        Xi_n = zero_mod + zeropow[N-i]
        Xi_n %= zero_r_count
        print(f[Xi_n]+1)

Submission status: Time Limit Exceeded

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

def popcount(n):
    ret = bin(n)[2:].count("1")
    return ret

def ff(n):
    d = popcount(n)
    q = n % d
    return q

def f(n):
    count = 0
    while True:
        if n == 0:
            return count
        count += 1
        n = ff(n)

n = int(input())
x_str = input()
x = int(x_str, 2) 

xpop = x_str.count("1")
xpop_p1 = xpop + 1
x1_p1 = x % xpop_p1

if xpop >= 2:
    xpop_m1 = xpop - 1
    x1_m1 = x % xpop_m1
else:
    x1_m1 = None

#print("x", x)
#print("xpop", xpop)
#print(x1_p1, x1_m1)
#print(xpop_p1, xpop_m1)

for i, c in enumerate(x_str):
    shisuu = n - i -1

    atai = 2 ** shisuu
    if c == "1":
        if xpop == 1:
            atai = 0
            xx = None
        else:
            atai = atai % xpop_m1
            xx = x1_m1
            xx = (x1_m1 - atai) % xpop_m1
    else:
        atai = atai % xpop_p1
        #print("atai", atai)
        xx = (x1_p1 + atai) % xpop_p1
    #print("xx", xx)
    if xx is not None:
        count = f(xx)
        out = 1 + count
    else:
        out = 0
    print(out)

Submission status: Time Limit Exceeded

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

#N = 23
#X = '00110111001011011001110'

mem_func = [-1 for i in range(2**N)]
mem_popc = [-1 for i in range(2**N)]

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

def func(n, l):
    # mem_func定義済み
    if mem_func[n] != -1: return mem_func[n] + l
    # mem_func未定義
    if n == 0: return l
    #print('mem_func not defined,', n)
    #print(n, popcount(n))
    if mem_popc[n] != -1:
        k = n % mem_popc[n]
    else:
        k = n % popcount(n)
    mem_func[n] = func(k, 1)
    return func(k, l+1)


list_X = list(X)
standard = popcount(int(X, 2))

for i in range(N):
    x = copy.copy(list_X)
    if x[i] == '0':
        x[i] = '1'
        z = int(''.join(x), 2)
        mem_func[z] = func(z%(standard+1), 1)
        print(mem_func[z])
    else:
        x[i] = '0'
        z = int(''.join(x), 2)
        if standard == 1:
            print(0)
            continue
        mem_func[z] = func(z%(standard-1), 1)
        print(mem_func[z])

Submission status: Time Limit Exceeded

Solution code:
def popcount(number, bit_counter):
    num = number
    counter = 0
    while num != 0: # 5,6回程度
        bit_con = 0
        if counter == 0:
            bit_con = bit_counter  
        else:
            bit_con = bin(num).count('1')
        num = num % bit_con
        counter += 1

    return counter

if __name__ == "__main__":
    import sys 

    readline = sys.stdin.readline 

    N = int(input())
    X_str= readline()
    X = list(X_str)
    bit_count = X_str.count('1')

    for i in range(N):
        # ビットの反転
        x_copy = X.copy()
        bit_count_n = bit_count
        if x_copy[i] == '0':
            x_copy[i] = '1'
            bit_count_n += 1
        else:
            x_copy[i] = '0'
            bit_count_n -= 1

        bit_int = int("".join(x_copy), 2)

        print(popcount(bit_int, bit_count_n))

Submission status: Time Limit Exceeded

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

#N = 23
#X = '00110111001011011001110'

mem_func = [-1 for i in range(2**N)]
mem_popc = [-1 for i in range(2**N)]

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

def func(n, l):
    # mem_func定義済み
    if mem_func[n] != -1: return mem_func[n] + l
    # mem_func未定義
    if n == 0: return l
    #print('mem_func not defined,', n)
    #print(n, popcount(n))
    if mem_popc[n] != -1:
        k = n % mem_popc[n]
    else:
        k = n % popcount(n)
    return func(k, l+1)


list_X = list(X)
standard = popcount(int(X, 2))

for i in range(N):
    x = copy.copy(list_X)
    if x[i] == '0':
        x[i] = '1'
        z = int(''.join(x), 2)
        mem_func[z] = func(z%(standard+1), 1)
        print(mem_func[z])
    else:
        x[i] = '0'
        z = int(''.join(x), 2)
        if standard == 1:
            print(0)
            continue
        mem_func[z] = func(z%(standard-1), 1)
        print(mem_func[z])

Submission status: Time Limit Exceeded

Solution code:
def popcount(number, bit_counter):
    num = number
    counter = 0
    while num != 0: # 5,6回程度
        bit_con = 0
        if counter == 0:
            bit_con = bit_counter  
        else:
            bit_con = bin(num)[2:].count('1')
        num = num % bit_con
        counter += 1

    return counter

if __name__ == "__main__":
    import sys 

    readline = sys.stdin.readline 

    N = int(input())
    X_str= readline()
    X = list(X_str)
    bit_count = X_str.count('1')

    for i in range(N):
        # ビットの反転
        x_copy = X.copy()
        bit_count_n = bit_count
        if x_copy[i] == '0':
            x_copy[i] = '1'
            bit_count_n += 1
        else:
            x_copy[i] = '0'
            bit_count_n -= 1

        bit_int = int("".join(x_copy), 2)

        print(popcount(bit_int, bit_count_n))

Submission status: Time Limit Exceeded

Solution code:
def popcount(number, bit_counter):
    num = number
    counter = 0
    while num != 0: # 5,6回程度
        bit_con = 0
        if counter == 0:
            bit_con = bit_counter  
        else:
            bit_con = bin(num)[2:].count('1')
        num = num % bit_con
        counter += 1

    return counter

if __name__ == "__main__":
    import sys 

    readline = sys.stdin.readline 

    N = int(input())
    X_str= input()
    X = list(X_str)
    bit_count = X_str.count('1')

    for i in range(N):
        # ビットの反転
        x_copy = X.copy()
        bit_count_n = bit_count
        if x_copy[i] == '0':
            x_copy[i] = '1'
            bit_count_n += 1
        else:
            x_copy[i] = '0'
            bit_count_n -= 1

        bit_int = int("".join(x_copy), 2)

        print(popcount(bit_int, bit_count_n))

Submission status: Time Limit Exceeded

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

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

max_n = int(("1" * N), 2)
dp = {}

def re(n):
  if n == 0:
    return 0
  elif n in dp:
    return dp[n]
  else:
    a = re(n % popcount(n)) + 1
    dp[n] = a
  return a
for i in range(1, N+1):
  print(re(X ^ 2**(N-i)))

Submission status: Time Limit Exceeded

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

def input(): return sys.stdin.readline().strip()

n=int(input())
xs=input()
xk=list(map(int,list(xs)))
xj=xk.count(1)

x=int(xs,2)

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

for i in range(n-1,-1,-1):
    xi=x^(1<<i)
    pxi=xj
    if xk[n-1-i]==0:
        pxi=pxi+1
    else:
        pxi=pxi-1
    if xi==0:
        print(0)
    else:
        xi=xi%pxi
        if xi==0:
            print(1)
        else:
            icnt=1
            while xi>0:
                icnt+=1
                xi=xi%popcount(xi)
            print(icnt)

Submission status: Time Limit Exceeded

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

n=int(input())
xs=input()
xk=list(map(int,list(xs)))
xj=xk.count(1)

x=int(xs,2)

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

for i in range(n-1,-1,-1):
    xi=x^(1<<i)
    pxi=xj
    if xk[n-1-i]==0:
        pxi=pxi+1
    else:
        pxi=pxi-1
    if xi==0:
        print(0)
    else:
        xi=xi%pxi
        if xi==0:
            print(1)
        else:
            icnt=1
            while xi>0:
                icnt+=1
                xi=xi%popcount(xi)
            print(icnt)

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
X=input()
popcount=X.count('1')
Xnum1 = 0
Xnum0 = 0
if popcount != 1:
    for i in range(N):
        Xnum1 = (Xnum1 + int(X[i])*(2**(N-i-1)%(popcount-1)))%(popcount-1)
for i in range(N):
    Xnum0 = (Xnum0 + int(X[i])*(2**(N-i-1)%(popcount+1)))%(popcount+1)
for i in range(N):
    if popcount==1 and X[i]=='1':
        print(0)
        continue
    if X[i]=='1':
        Xi = (Xnum1 - (2**(N-i-1)%(popcount-1)))%(popcount-1)
    else:
        Xi = (Xnum0 + (2**(N-i-1)%(popcount+1)))%(popcount+1)
    ans = 1
    while Xi!=0:
        Xi = Xi % bin(Xi).count('1')
        ans += 1
    print(ans)

Submission status: Time Limit Exceeded

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

#N = 23
#X = '00110111001011011001110'

mem_func = [-1 for i in range(2**N)]

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

def func(n, l):
    # mem_func定義済み
    if mem_func[n] != -1: return mem_func[n] + l
    # mem_func未定義
    if n == 0: return l
    n = n % popcount(n)
    return func(n, l+1)

list_X = list(X)
standard = popcount(int(X, 2))

for i in range(N):
    x = copy.copy(list_X)
    if x[i] == '0':
        x[i] = '1'
        z = int(''.join(x), 2)
        mem_func[z] = func(z%(standard+1), 1)
        print(mem_func[z])
    else:
        x[i] = '0'
        z = int(''.join(x), 2)
        if standard == 1:
            print(0)
            continue
        mem_func[z] = func(z%(standard-1), 1)
        print(mem_func[z])

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
xs=input()
xk=list(map(int,list(xs)))
xj=xk.count(1)

x=int(xs,2)

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

for i in range(n-1,-1,-1):
    xi=x^(1<<i)
    pxi=xj
    if xk[n-1-i]==0:
        pxi=pxi+1
    else:
        pxi=pxi-1
#    print(i,xi,"pxi",pxi)
    if xi==0:
        print(0)
    else:
#        print("i",i,"xi",xi,"pxi",pxi)
        xi=xi%pxi
#        print("--i",i,"xi",xi,"pxi",pxi)
        if xi==0:
            print(1)
        else:
#            print("i",i,"xi",xi,"pxi",pxi)
#            print(i,pxi,xi,popcount(xi),xi%popcount(xi))
            icnt=1
            while xi>0:
                icnt+=1
#                print(i,pxi,xi,popcount(xi),xi%popcount(xi))
                xi=xi%popcount(xi)
            print(icnt)

Submission status: Time Limit Exceeded

Solution code:
import sys
n = int(input())
x = int(input(),2)
bitx = bin(x).count('1')

ans = [0]*(bitx+1)
for i in range(1,len(ans)):
    ans[i] = 1 + ans[i%bin(i).count('1')]
#print(ans)
l = []
for i in range(n):
    y = x^(1<<(n-i-1))
    if y>>(n-i-1)&1:
        bity = bitx+1
    else:
        bity = bitx-1
    if bity != 0:
        t = y % bity
        l.append(str(1+ans[t]))
    else:
        l.append(str(0))
    #print(1+ans[t])
print('\n'.join(l))

Submission status: Time Limit Exceeded

Solution code:
input = raw_input

def popcount(n):
    ret = bin(n)[2:].count("1")
    return ret

def ff(n):
    d = popcount(n)
    q = n % d
    return q

def f(n):
    count = 0
    while True:
        if n == 0:
            return count
        count += 1
        n = ff(n)

n = int(input())
x_str = input()
x = int(x_str, 2) 

xpop = x_str.count("1")
xpop_p1 = xpop + 1
x1_p1 = x % xpop_p1

if xpop >= 2:
    xpop_m1 = xpop - 1
    x1_m1 = x % xpop_m1
else:
    x1_m1 = None

#print("x", x)
#print("xpop", xpop)
#print(x1_p1, x1_m1)
#print(xpop_p1, xpop_m1)

for i, c in enumerate(x_str):
    shisuu = n - i -1

    atai = 2 ** shisuu
    if c == "1":
        if xpop == 1:
            atai = 0
            xx = None
        else:
            atai = atai % xpop_m1
            xx = x1_m1
            xx = (x1_m1 - atai) % xpop_m1
    else:
        atai = atai % xpop_p1
        #print("atai", atai)
        xx = (x1_p1 + atai) % xpop_p1
    #print("xx", xx)
    if xx is not None:
        count = f(xx)
        out = 1 + count
    else:
        out = 0
    print(out)

Submission status: Time Limit Exceeded

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

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

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

num = int(s, 2)
# print(num)
# print(num%(popcnt-1))
# print(num%(popcnt+1))

zero = False
if popcnt==1:
    zero = True
else:
    p_l = num%(popcnt-1)
p_h = num%(popcnt+1)

next = [-1]*n
for i in range(n):
    # print(s[i])
    if s[i]=='0':
        next[i] = (p_h + 2**(n-i-1)%(popcnt+1))%(popcnt+1)
    else:
        if zero:
            next[i] = -1
        else:
            next[i] = (p_l - 2**(n-i-1)%(popcnt-1))%(popcnt-1)

# print(next)

d = {0:0, -1:-1}
for number in next:
    if number in d.keys():
        continue
    m = number
    tmp = 0
    while not m in d.keys():
        m = m%bin(m).count("1")
        tmp += 1
    d[number] = d[m]+tmp

for number in next:
    print(d[number]+1)

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
X=input()
Xnum=int(X,2)
popcount=X.count('1')
if popcount != 1:
    Xnum1=Xnum%(popcount-1)
Xnum0=Xnum%(popcount+1)
for i in range(N):
    if popcount==1 and X[i]=='1':
        print(0)
        continue
    if X[i]=='1':
        Xi = (Xnum1 - (2**(N-i-1)%(popcount-1)))%(popcount-1)
    else:
        Xi = (Xnum0 + (2**(N-i-1)%(popcount+1)))%(popcount+1)
    ans = 1
    while Xi!=0:
        Xi = Xi % bin(Xi).count('1')
        ans += 1
    print(ans)

Submission status: Time Limit Exceeded

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

dp=[-1]*(200001)

dp[0]=0
dp[1]=1

def fun(num,step):
    num2=num%sum(list(map(int,bin(num)[2:])))
    if dp[num2]!=-1:
        dp[num]=dp[num2]+step
    else:
        fun(num2,step+1)

for i in range(2,200001):
    fun(i,1)

num1=''.join(x)
num2=int(num1,2)
su = sum(list(map(int,x)))

for i in range(n):
    num4=num2
    su2=su
    if x[i]=='1':
        num4-=pow(2,(n-1-i))
        su2-=1
    else:
        num4+=pow(2,(n-1-i))
        su2+=1
    if su2 == 0:
        print('0')
    elif num4<=20000:
        print(dp[num4])
    else:
        num3=num4%su2
        print(dp[num3]+1)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
X = int(input(), 2)
def popcount(n):
  return bin(n).count("1")

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

for i in range(1, N+1):
  print(re(X ^ 2**(N-i)))

Submission status: Time Limit Exceeded

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


mem_func = [-1 for i in range(2**N)]
mem_popcount = [-1 for i in range(2**N)]

def popcount(n):
    if mem_popcount[n] != -1:
        return mem_popcount[n]
    else:
        mem_popcount[n] = str(bin(n)).count('1')
    return mem_popcount[n]

def func(n, l):
    # mem_func定義済み
    if mem_func[n] != -1: return mem_func[n] + l
    # mem_func未定義
    if n == 0: return l
    n = n % popcount(n)
    return func(n, l+1)


list_X = list(X)
for i in range(N):
    x = copy.copy(list_X)
    if x[i] == '0':
        x[i] = '1'
    else:
        x[i] = '0'
    z = int(''.join(x), 2)
    mem_func[z] = func(z, 0)
    print(mem_func[z])

Submission status: Time Limit Exceeded

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

dp=[-1]*(200001)

dp[0]=0
dp[1]=1

def fun(num,step):
    num2=num%sum(list(map(int,bin(num)[2:])))
    if dp[num2]!=-1:
        dp[num]=dp[num2]+step
    else:
        fun(num2,step+1)

for i in range(2,200001):
    fun(i,1)

num1=''.join(x)
num2=int(num1,2)
su = sum(list(map(int,x)))

for i in range(n):
    num4=num2
    su2=su
    if x[i]=='1':
        num4-=pow(2,(n-1-i))
        su2-=1
    else:
        num4+=pow(2,(n-1-i))
        su2+=1
    if su2 == 0:
        print('0')
    elif num4<=n:
        print(dp[num4])
    else:
        num3=num4%su2
        print(dp[num3]+1)

Submission status: Time Limit Exceeded

Solution code:
import sys
import itertools
# import numpy as np
import time
import math
import heapq
from collections import defaultdict
sys.setrecursionlimit(10 ** 7)
 
INF = 10 ** 9 + 7
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

# map(int, input().split())

def my_pow(base, n, mod):
    if n == 0:
        return 1
    x = base
    y = 1
    while n > 1:
        if n % 2 == 0:
            x *= x
            n //= 2
        else:
            y *= x
            n -= 1
        x %= mod
        y %= mod
    return x * y % mod
MOD = 10 ** 9 + 7

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

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

ones = X.count('1')
A_1 = 0
A_2 = 0
d = 1
for a in X[::-1]:
    if ones == 1:
        A_2 += (int(a) * d) % (ones + 1)
    else:
        A_1 += (int(a) * d) % (ones - 1)
        A_2 += (int(a) * d) % (ones + 1)
    d *= 2

for i in range(N):
    ans = 1
    total = ones
    sumA = 0
    if X[i] == '0':
        total += 1
        sumA = A_2 + my_pow(2, N - i - 1, total)
    else:
        total -= 1
        if total != 0:
            sumA = A_1 - my_pow(2, N - i - 1, total)
    if total == 0:
        print(0)
        continue
    n = sumA % total
    while n != 0:
        n = n % popcount(n)
        ans += 1
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
B = input()
B_1 = B.count("1")
mod_p1 = int(B,2) % (B_1+1)
if B_1 != 1:
    mod_m1 = int(B,2) % (B_1-1)

def calc_small(n, iter):
    iter += 1
    mod = n % bin(n).count("1")

    if mod == 0:
        return iter
    else:
        return calc_small(mod, iter)


for i in range(N):
    if B_1 == 1 and int(B[i]) == 1:
        print(0)
        continue
    mod = (mod_m1 - (2**(N-i-1))) % (B_1-1) if int(B[i]) == 1 else (mod_p1 + (2**(N-i-1))) % (B_1+1)
    iter = 1
    if mod == 0:
        print(iter)
    else:
        print(calc_small(mod, iter))