Lining Up [AtCoder Beginner Contest 050 C]

atcoder.jp

「自分の左に並んでいた人数と自分の右に並んでいた人数の差の絶対値」の配列は、並んでいる人数が決まれば一意に定まります。例えば、人数が10人なら、

・9,7,5,3,1,1,3,5,7,9

となります。1番目の人の左には0人、右には9人いますから、差の絶対値は9です。同様に、2番目の人の左には1人、右には8人で、差の絶対値は7です。

この配列を「元の配列」と表現すると、まず「入力で与えられた配列」が元の配列と一致するかどうかを判定する必要があります。これについては、人数を受け取った時点で「元の配列（ソート済み）」を作ってしまい、それと「入力で与えられた配列」をソートしたものが一致するかどうかを調べることで判定できます。

「元の配列」と「入力で与えられた配列」が一致するなら、次に元の並び方が何通りあるかを考えます。これは、上記の [9,7,5,3,1,1,3,5,7,9] を見てわかる通り、差の絶対値が1である人は左右に2つある1のどちらか、差の絶対値が3の人は……となっていくので、2^n/2 通りです。人数が奇数の場合は真ん中に「差の絶対値が0である人」が存在しますが、その人の並び方は1通りなので考慮する必要はなく、元の並び方は人数が奇数でも偶数でも共に 2^n/2 通りということになります。

import java.util.*;

class Main {
	static Scanner sc = new Scanner(System.in);
	public static void main(String[] args) {
		
		int n = sc.nextInt();
		int[] ar = new int[n];
		for (int i=0; i<n; i++) ar[i] = sc.nextInt();
		Arrays.sort(ar);
		
		if (n%2 == 0) {
			int[] even = new int[n];
			for (int i=0; i<=n-1; i++) {
				if (i%2 == 0) even[i] = i+1;
				else even[i] = i;
			}
			
			for (int i=0; i<n; i++) {
				if (ar[i] != even[i]) {
					System.out.println(0); return;
				}
			}
			
		}
		else {
			int[] odd = new int[n];
			odd[0] = 0;
			for (int i=1; i<=n-1; i++) {
				if (i%2 != 0) odd[i] = i+1;
				else odd[i] = i;
			}
			
			for (int i=0; i<n; i++) {
				if (ar[i] != odd[i]) {
					System.out.println(0); return;
				}
			}
			
		}
		
		long ans = 1;
		for (int i=0; i<n/2; i++) ans = 2*ans%1000000007;
		System.out.println(ans);
		
	}
}

最後、2を n/2 乗する部分ですが、Math.pow でやったらオーバーフローしました。考えてみれば当然ですね。10^9+7 で割った余りを求める系の問題では、Math.pow 関数は使わないほうがよさそうです。