Introduction

Participated in Acing Programming Contest 2020 *. Thanks to AtCoder and AtCoder Problems.

This theme

AtCoder Acing Programming Contest 2020 D --Anything Goes to Zero * Difficulty: 1294

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():
    input = stdin.readline
    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()