# This theme

This theme, iterative squares

0 1 1 0 1 Decimal notation
Original number $0*2^4$ $1*2^3$ $1*2^2$ $0*2^1$ $1*2^0$ 13
0th digit bit inversion $1*2^4$ 13+16=29
1st digit bit inversion $0*2^3$ 13- 8= 5
2nd digit bit inversion $0*2^2$ 13- 4= 9
3rd digit bit inversion $1*2^1$ 13+ 2=15
4th digit bit inversion $0*2^0$ 13- 1=12

If the given value is 01101, it can be decomposed as shown in the table above. In addition, the following holds as a distributive law, so $(a+b)\%m=(a\%m+b\%m)\%m$ The entire value can be obtained at high speed by inserting and removing the value of the bit-inverted digit. Ruby

#### ruby.rb


n = gets.to_i
x = gets.chomp
xs = x.to_i(2)
xc = x.count('1')
def mpow(n, p, mod)
return 0 if mod.zero?
r = 1
while p > 0
r = r * n % mod if p & 1 == 1
n = n * n % mod
p >>= 1
end
r
end
def popcount(u)
return 0 if u.zero?
a = u % u.to_s(2).count('1')
1 + popcount(a)
end
xsp = mpow(xs, 1, xc + 1)
xsm = mpow(xs, 1, xc - 1)
n.times do |i|
if x[i] == '0'
y = xsp + mpow(2, n - i - 1, xc + 1)
y = mpow(y, 1, xc + 1)
elsif xc == 1
puts '0'
next
else
y = xsm - mpow(2, n - i - 1, xc - 1)
y = mpow(y, 1, xc - 1)
end
puts popcount(y) + 1
end


Use the mpow method of the previously posted * Solve with Ruby, Perl, Java and Python AtCoder ATC 002 B * ~~ copy and paste ~~ ..

#### mpow.rb


def mpow(n, p, mod)
return 0 if mod.zero?
r = 1
while p > 0
r = r * n % mod if p & 1 == 1
n = n * n % mod
p >>= 1
end
r
end


However, this time the divisor may be 0, so it corresponds to that.

#### inout.rb


n.times do |i|
if x[i] == '0'
y = xsp + mpow(2, n - i - 1, xc + 1)
y = mpow(y, 1, xc + 1)
elsif xc == 1
puts '0'
next
else
y = xsm - mpow(2, n - i - 1, xc - 1)
y = mpow(y, 1, xc - 1)
end
puts popcount(y) + 1
end


Here, the numerical value of the bit-inverted digit is put in and out. Again, we need to do something when the divisor is 0.

#### popcount.rb


def popcount(u)
return 0 if u.zero?
a = u % u.to_s(2).count('1')
1 + popcount(a)
end


The second and subsequent pop counts are recursively calculated. If you make a note of this, it will be a little faster. Python

#### python.py


from sys import stdin

def mpow(n, p, mod):
if mod == 0:
return 0
r = 1
while p > 0:
if p & 1 == 1:
r = r * n % mod
n = n * n % mod
p >>= 1
return r
def popcount(u):
if u == 0:
return 0
a = u % bin(u).count('1')
return 1 + popcount(a)
def main():
n = int(input())
x = '0b' + input()
xs = int(x, 0)
xc = x.count('1')
xsp = mpow(xs, 1, xc + 1)
xsm = mpow(xs, 1, xc - 1)
for i in range(2, n + 2):
if x[i] == '0':
y = xsp + mpow(2, n - i + 1, xc + 1)
y = mpow(y, 1, xc + 1)
elif xc == 1:
print(0)
continue
else:
y = xsm - mpow(2, n - i + 1, xc - 1)
y = mpow(y, 1, xc - 1)
print(popcount(y) + 1)
main()

Ruby Python
Code length(Byte) 629 872
Execution time(ms) 625 1048
memory(KB) 15392 9636

# Summary

• Solved AISING2020 D
• Become familiar with Ruby
• Become familiar with Python

Referenced site