ABC-050-C Lining Up

■■■問題■■■

1〜N までの番号がついた、N人の人がいます。
彼らは昨日、ある順番で左右一列に並んでいましたが、
今日になってその並び方が分からなくなってしまいました。

しかし、彼らは全員、「自分の左に並んでいた人数と自分の右に並んでいた人数の差の絶対値」を覚えています。
彼らの報告によると、人iの、「自分の左に並んでいた人数と自分の右に並んでいた人数の差の絶対値」はAiです。

彼らの報告を元に、元の並び方が何通りあり得るかを求めてください。
ただし、答えは非常に大きくなることがあるので、1000000007で割った余りを出力してください。
また、彼らの報告が間違っており、ありうる並び方がないこともありえます。 その際は0を出力してください。

■■■入力■■■

N
A1 A2 ・・・ AN

●1 <= N  <= 10万
●0 <= Ai <= N-1

■■■出力■■■

元の並び順としてありうるものが何通りあるか求め、1000000007で割った余りを出力せよ。

C#のソース

using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    static string InputPattern = "Input1";

    static List<string> GetInputList()
    {
        var WillReturn = new List<string>();

        if (InputPattern == "Input1") {
            WillReturn.Add("5");
            WillReturn.Add("2 4 4 0 2");
            //4
            //ありうる並び方は、人の番号で書くと、
            //●2,1,4,5,3
            //●2,5,4,1,3
            //●3,1,4,5,2
            //●3,5,4,1,2
            //の4通りです。
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("7");
            WillReturn.Add("6 4 0 2 4 0 2");
            //0
            //どのような並び方でも、報告と矛盾するので、0が答えになります
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("8");
            WillReturn.Add("7 5 1 1 7 3 5 3");
            //16
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static void Main()
    {
        List<string> InputList = GetInputList();

        int N = int.Parse(InputList[0]);
        int[] AArr = InputList[1].Split(' ').Select(X => int.Parse(X)).ToArray();
        Array.Sort(AArr);

        bool IsCorrect = true;

        for (int I = 1; I <= N; I++) {
            int wkNum;

            //Nが偶数の場合
            if (N % 2 == 0) {
                wkNum = (I % 2 == 0 ? I - 1 : I);
            }
            else { //Nが奇数の場合
                wkNum = (I % 2 == 1 ? I - 1 : I);
            }
            if (AArr[I - 1] != wkNum)
                IsCorrect = false;
        }

        if (IsCorrect) {
            Console.WriteLine(DeriveBekijyou(2, N / 2, 1000000007));
        }
        else Console.WriteLine(0);
    }

    //繰り返し2乗法で、(NのP乗) Mod Mを求める
    static long DeriveBekijyou(long pN, long pP, long pM)
    {
        long CurrJyousuu = pN % pM;
        long CurrShisuu = 1;
        long WillReturn = 1;

        while (true) {
            //対象ビットが立っている場合
            if ((pP & CurrShisuu) > 0) {
                WillReturn = (WillReturn * CurrJyousuu) % pM;
            }

            CurrShisuu *= 2;
            if (CurrShisuu > pP) return WillReturn;
            CurrJyousuu = (CurrJyousuu * CurrJyousuu) % pM;
        }
    }
}

解説

偶数と奇数で場合分けしてから、正しい配列かをチェックし、
場合の数の積の法則で、繰り返し2乗法を使ってます。