Lösen mit Ruby, Perl, Java und Python AtCoder ARC 066 C Iterativer Square Hash

Einführung

• AtCoder-Probleme * Verwenden Sie Empfehlungen, um frühere Probleme zu lösen. Dank AtCoder und AtCoder Probleme.

Dieses Thema

AtCoder Regular Contest 066 C - Lining Up Difficulty: 927

Dieses Thema, iterative Quadratmethode und Hash Ruby Dies ist ein symmetrisches Problem. Wenn Sie es also einem Hash zuweisen, wird erwartet, dass es sich um ein Wertearray handelt, z. B. "2221222" für ungerade Namen und "22222222" für gerade Namen. In anderen Fällen kann festgestellt werden, dass keine Vereinbarung vorliegt.

Es ist auch an der Zeit, dass das zuvor veröffentlichte * Lösen mit Ruby, Perl, Java und Python AtCoder ATC 002 B * nützlich ist. Da es sich um die Anzahl der Multiplikationskombinationen von 2 handelt, kann die im obigen Beitrag erstellte iterative Quadratmethode (Funktion | Methode) unverändert verwendet werden.

ruby.rb

n = gets.to_i
a = gets.split.map(&:to_i)
h = Hash.new(0)
a.each do |x|
  h[x] += 1
end
f = true
h.each do |k, v|
  if n.odd? && k == 0
    if v != 1
      f = false
      break
    end
  elsif v != 2
    f = false
    break
  end
end
MOD = 1_000_000_007
def mpow(n, p, mod)
  r = 1
  while p > 0
    r = r * n % mod if p & 1 == 1
    n = n * n % mod
    p >>= 1
  end
  r
end
puts (f ? mpow(2, n / 2, MOD) : 0)

mpow.rb

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

Ich benutze es so wie es ist. Python

python.py

from collections import Counter

n = int(input())
a = list(map(int, input().split()))
h = Counter()
for x in a:
    h[x] += 1
f = True
for k, v in h.most_common():
    if n % 2 == 1 and k == 0:
        if v != 1:
            f = False
            break
    elif v != 2:
        f = False
        break
MOD = 1000000007
def mpow(n, p, mod):
    r = 1
    while p > 0:
        if p & 1 == 1:
            r = r * n % mod
        n = n * n % mod
        p >>= 1
    return r
print(mpow(2, n // 2, MOD) if f else 0)

hash.py

from collections import Counter

Deklarieren Sie "aus Sammlungen Importzähler", wenn Sie Hashes verwenden.

mod.py

MOD = 1000000007
MOD = 1_000_000_007

In meinem Ring "Python 3.8.2 (Standard, 16. April 2020, 16:12:56)" können Sie "1_000_000_007" schreiben, aber in der AtCoder-Umgebung scheint es "WA" zu sein. Perl

perl.pl

chomp (my $n = <STDIN>);
chomp (my @a = split / /, <STDIN>);
my %h;
$h{$_}++ for @a;
my $f = 1;
for my $k (keys %h) {
  if ($n % 2 == 1 && $k == 0) {
    if ($h{$k} != 1) {
      $f = 0;
      last;
    }
  } elsif ($h{$k} != 2) {
    $f = 0;
    last;
  }
}
my $MOD = 1_000_000_007;
sub mpow {
  my ($n, $p) = @_;
  my $r = 1;
  while ($p > 0) {
    $r = $r * $n % $MOD if $p & 1;
    $n = $n * $n % $MOD;
    $p >>= 1;
  }
  $r;
}
print ($f ? mpow(2, int($n / 2)) : 0), "\n";

Wie es ist ... Java

java.java

import java.math.BigInteger;
import java.util.*;

class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = Integer.parseInt(sc.next());
        HashMap<Integer, Integer> h = new HashMap<>();
        for (int i = 0; i < n; i++) {
            int a = Integer.parseInt(sc.next());
            if (h.containsKey(a)) {
                h.put(a, h.get(a) + 1);
            } else {
                h.put(a, 1);
            }
        }
        sc.close();
        boolean f = true;
        for (int k : h.keySet()) {
            if (n % 2 == 1 && k == 0) {
                if (h.get(k) != 1) {
                    f = false;
                    break;
                }
            } else if (h.get(k) != 2) {
                f = false;
                break;
            }
        }
        BigInteger bn = new BigInteger("2");
        BigInteger bm = new BigInteger("1000000007");
        BigInteger bp = new BigInteger(Integer.toString(n / 2));
        System.out.println((f ? bn.modPow(bp, bm) : 0));
    }
}

Zusammenfassung

• Gelöster ARC 066 C.
• Machen Sie sich mit Ruby vertraut
• Machen Sie sich mit Python vertraut
• Machen Sie sich mit Perl vertraut
• Machen Sie sich mit Java vertraut

Referenzierte Site

• [Python] Dictionary (Hash) *
• Python oder und und Operatorfalle *