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

- 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 | 13 | |||||

0th digit bit inversion | 13+16=29 | |||||

1st digit bit inversion | 13- 8= 5 | |||||

2nd digit bit inversion | 13- 4= 9 | |||||

3rd digit bit inversion | 13+ 2=15 | |||||

4th digit bit inversion | 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

`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 count`

s 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()
```

Ruby | Python | |
---|---|---|

Code length(Byte) | 629 | 872 |

Execution time(ms) | 625 | 1048 |

memory(KB) | 15392 | 9636 |

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

Referenced site

Recommended Posts