Lösen mit Ruby und Python AtCoder AISING2020 D Iterative Square-Methode

Einführung

• Teilnahme am Acing Programming Contest 2020 *. Dank AtCoder und AtCoder Probleme.

Dieses Thema

• AtCoder Acing Programming Contest 2020 D - Alles geht auf Null * Difficulty: 1294

Dieses Thema wiederholte quadratische Methode

Wenn der angegebene Wert "01101" ist, kann er wie in der obigen Tabelle gezeigt zerlegt werden. Darüber hinaus gilt das Folgende als Verteilungsregel $(a+b)\%m=(a\%m+b\%m)\%m$ Der gesamte numerische Wert kann mit hoher Geschwindigkeit erhalten werden, indem der numerische Wert der bitinvertierten Ziffer ein- und ausgefahren wird. 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

Verwenden Sie die "mpow-Methode" der zuvor veröffentlichten * Mit Ruby, Perl, Java und Python AtCoder ATC 002 B lösen * ~~ copy ~~ ..

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

Diesmal kann der Divisor jedoch "0" sein, also entspricht er dem.

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

Hier wird der numerische Wert der bitinvertierten Ziffer ein- und ausgegeben. Auch hier ist eine Verarbeitung erforderlich, wenn der Divisor "0" ist.

popcount.rb

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

Die zweite und die nachfolgenden "Pop Count" werden rekursiv berechnet. Wenn Sie hier eine Notiz machen, wird es etwas schneller. 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()

Zusammenfassung

• Gelöst AISING2020 D.
• Machen Sie sich mit Ruby vertraut
• Machen Sie sich mit Python vertraut

Referenzierte Site

• Darstellung von Binärzahlen in Python *