AGC-017-A Biscuits

■■■問題■■■

いくつかのビスケットの入った袋がN個あります。
i番目の袋にはAi個のビスケットが入っています。

高木君は、このうちいくつかの袋を選んで、
選んだ袋に入っているビスケットをすべて食べるということを行います。
このとき、袋を一つも選ばなかったり、すべての袋を選んだりしてもかまいません。

高木君は、食べるビスケットの枚数を2で割ると余りがPに等しくなるようにしたいです。
このような袋の選び方は何通りあるか求めてください。

■■■入力■■■

N P
A1 A2 ・・・ AN

●1 <= N <= 50
●P=0,1
●1 <= Ai <= 100

■■■出力■■■

高木君が食べるビスケットの枚数を2で割るとPに等しくなるような、
袋の選び方は何通りあるかを出力せよ。

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("2 0");
            WillReturn.Add("1 3");
            //2
            //食べるビスケットの枚数が2で割って0に等しくなるような選び方は2通りです：
            //●どちらの袋も選ばない。食べるビスケットの枚数は0である
            //●どちらの袋も選ぶ。食べるビスケットの枚数は4である
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("1 1");
            WillReturn.Add("50");
            //0
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("3 0");
            WillReturn.Add("1 1 1");
            //4
            //同じ枚数のビスケットが入っている場合でも、異なる袋は区別します
        }
        else if (InputPattern == "Input4") {
            WillReturn.Add("45 1");
            WillReturn.Add("17 55 85 55 74 20 90 67 40 70 39 89 91 50 16 24 14 43 24 66 25 9 89 71 41 16 53 13 61 15 85 72 62 67 42 26 36 66 4 87 59 91 4 25 26");
            //17592186044416
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static void Main()
    {
        List<string> InputList = GetInputList();
        int[] wkArr = InputList[0].Split(' ').Select(X => int.Parse(X)).ToArray();
        int P = wkArr[1];

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

        //場合の数[2を法とした余り]のDP表
        long[] PrevDP = new long[2];
        PrevDP[0] = 1;

        foreach (int EachInt in AArr) {
            long[] CurrDP = (long[])PrevDP.Clone();
            for (int I = 0; I <= 1; I++) {
                if (PrevDP[I] == 0) continue;

                long NewI = (I + EachInt) % 2;
                CurrDP[NewI] += PrevDP[I];
            }
            PrevDP = CurrDP;
        }
        Console.WriteLine(PrevDP[P]);
    }
}

解説

動的計画法で解いてます。