Résolution avec Ruby et Python AtCoder AISING2020 D Méthode carrée itérative

introduction

• Participation au Acing Programming Contest 2020 *. Merci à AtCoder et AtCoder Problems.

Ce thème

• Concours de programmation AtCoder Acing 2020 D - Tout va à zéro * Difficulty: 1294

Ce thème, méthode carrée répétée

Si la valeur donnée est «01101», elle peut être décomposée comme indiqué dans le tableau ci-dessus. En outre, ce qui suit vaut comme règle de distribution, $(a+b)\%m=(a\%m+b\%m)\%m$ La valeur entière peut être obtenue à grande vitesse en insérant et en supprimant la valeur de chiffre à bits inversés. 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

Utilisez la mpow method de la précédente * Résoudre avec Ruby, Perl, Java et Python AtCoder ATC 002 B * ~~ copier ~~ ..

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

Cependant, cette fois, le diviseur peut être «0», donc cela correspond à cela.

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

Ici, la valeur du chiffre à bits inversés est entrée et sortie. Là encore, un traitement est nécessaire lorsque le diviseur est «0».

popcount.rb

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

Le deuxième «pop count» et les suivants sont calculés récursivement. Si vous faites une note ici, ce sera un peu plus rapide. 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()

Résumé

• Résolu AISING2020 D
• Familiarisez-vous avec Ruby
• Familiarisez-vous avec Python

Site référencé

• Représentant des nombres binaires en python *