Ruby と Perl と Java と Python で解く AtCoder ARC 066 C 繰返し二乗法 ハッシュ

# はじめに
*[AtCoder Problems](https://kenkoooo.com/atcoder/#/)* の Recommendation を利用して、過去の問題を解いています。
AtCoder さん、AtCoder Problems さん、ありがとうございます。

# 今回のお題
*[AtCoder Regular Contest 066 C - Lining Up](https://atcoder.jp/contests/arc066/tasks/arc066_a)*
<font color="green">Difficulty: 927</font>

今回のテーマ、繰返し二乗法　と　ハッシュ
# Ruby
これは左右対称な問題ですので、仮にハッシュに代入した場合、奇数名では`2221222`、偶数名では`22222222`の様なvalues配列になると想定されます。
それ以外の場合は、並び方がないと判断できます。

また、以前投稿しました *[Ruby と Perl と Java と Python で解く AtCoder ATC 002 B](https://qiita.com/superrino130/items/adbb485637e45a024fa1)* が役立つ時が来ました。
2の掛け算の組合せ数ですので、上記投稿で作成した繰返し二乗法(関数|メソッド)がそのまま使用できます。

```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
```
そのまま使用しています。
# 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
```
ハッシュを使用する場合`from collections import Counter`を宣言します。

```mod.py
MOD = 1000000007
MOD = 1_000_000_007
```
俺環`Python 3.8.2 (default, Apr 16 2020, 16:12:56)`では、`1_000_000_007`と書いても通りますが、AtCoder環境では `WA` になるようです。
# 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";
```
そのまま...
# 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));
    }
}
```

||Ruby|Python|Perl|Java|
|:--:|:--:|:--:|:--:|:--:|
|コード長|438 Byte|535 Byte|504 Byte|1100 Byte|
|実行時間|75 ms|125 ms|76 ms|435 ms|
|メモリ|12172 KB|16096 KB|20556 KB|49896 KB|
# まとめ
+ ARC 066 C を解いた
+ Ruby に詳しくなった
+ Python に詳しくなった
+ Perl に詳しくなった
+ Java に詳しくなった

参照したサイト
*[【Python】辞書（ハッシュ）](https://qiita.com/kenta1984/items/5b61ecc4b96a30a32601)*
*[Python の or と and 演算子の罠](https://qiita.com/keisuke-nakata/items/e0598b2c13807f102469)*