177AC - ABC050C: Lining Up

競プロ 10^9+7
ABC050-C (300 points)
問題

以下の条件を満たす N 人の並び方の総数を 10^9 + 7 で割った余りを出力する.

  • 人 i の右側に並んでいる人数と左側に並んでいる人数の差の絶対値は A_i.
  • 1 \leq N \leq 10^5
  • 0 \leq A_i \leq N - 1
方針
  • 人 i の左に並んでいる人数を k とすると, 右に並んでいる人数は k \pm A_i となり, 全員で N 人であることから

\ \ \ \ k = \frac{N \pm A_i - 1}{2}

  • 条件を満たす並び方がゼロになる場合：
  • N と偶奇が同じ A_i が存在（このとき k が整数にならない）.
  • A_1, A_2, \ldots, A_N に 同じ数が 3 つ以上含まれる（ k は 2 通り）.
  • N が奇数のとき, A_1, A_2, \ldots, A_N に 0 が 2 つ以上含まれる.
  • これら以外の場合, A_i = A_j となる 2 人 i, j は左右を入れ替えることが可能なので, 並び方の総数は 2 ^ {\lfloor N / 2 \rfloor} 通り. 
# input
N = int(input())
A = list(map(int, input().split()))

cnt = [0 for i in range(N)]
ans = 1

if N % 2 == 0:
    for i in range(N):
        if A[i] % 2 == 0:
            print(0)
            exit()
        cnt[A[i]] += 1
        if cnt[A[i]] > 2:
            print(0)
            exit()
        if cnt[A[i]] == 1:
            ans = (ans * 2) % (10 ** 9 + 7)
    print(ans)
else:
    for i in range(N):
        if A[i] % 2 == 1:
            print(0)
            exit()
        if A[i] > 0:
            cnt[A[i]] += 1
            if cnt[A[i]] > 2:
                print(0)
                exit()
            if cnt[A[i]] == 1:
                ans = (ans * 2) % (10 ** 9 + 7)
        if A[i] == 0:
            cnt[0] += 1
            if cnt[0] > 1:
                print(0)
                exit()
    print(ans)