ABC365-E Xor Sigma Problem

問題へのリンク

C#のソース

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

class Program
{
    static string InputPattern = "InputX";

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

        if (InputPattern == "Input1") {
            WillReturn.Add("3");
            WillReturn.Add("1 3 2");
            //3
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("7");
            WillReturn.Add("2 5 6 5 2 1 7");
            //83
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static void Main()
    {
        List<string> InputList = GetInputList();
        long[] AArr = InputList[1].Split(' ').Select(pX => long.Parse(pX)).ToArray();
        long UB = AArr.GetUpperBound(0);

        long MaxVal = AArr.Max();

        var BitValDict = new Dictionary<long, long>();
        long CurrBit = 1;
        long BitVal = 1;
        while (true) {
            BitValDict[CurrBit] = BitVal;
            CurrBit++;
            BitVal *= 2;
            if (BitVal > MaxVal) {
                break;
            }
        }

        //foreach (var EachPair in BitValDict) {
        //    Console.WriteLine("BitValDict[{0}]={1}", EachPair.Key, EachPair.Value);
        //}

        long Answer = 0;
        foreach (var EachPair in BitValDict) {
            var BitList = new List<long>();
            foreach (long EachA in AArr) {
                if ((EachA & EachPair.Value) > 0) {
                    BitList.Add(1);
                }
                else {
                    BitList.Add(0);
                }
            }
            long Result = ExecDP(BitList);
            Answer += Result * EachPair.Value;
        }
        Console.WriteLine(Answer);
    }

    // ビットのListを引数として、1の個数を偶数にできる区間の数を返す
    static long ExecDP(List<long> pList)
    {
        checked {
            long Answer = 0;

            // 場合の数[1の個数 mod 2][区間長さ(2まで)] なDP表
            long[,] PrevDP = new long[2, 3];
            PrevDP[0, 0] = 1;

            foreach (long EachBit in pList) {
                long[,] CurrDP = new long[2, 3];

                for (long I = 0; I <= 1; I++) {
                    for (long J = 0; J <= 2; J++) {
                        if (PrevDP[I, J] == 0) continue;

                        long NewI = I + EachBit;
                        NewI %= 2;

                        long NewJ = J + 1;
                        NewJ = Math.Min(2, NewJ);

                        CurrDP[NewI, NewJ] += PrevDP[I, J];

                        // 解に計上
                        if (NewI == 1 && NewJ == 2) {
                            Answer += PrevDP[I, J];
                        }
                    }
                }
                PrevDP = CurrDP;
                PrevDP[0, 0] = 1;
            }

            return Answer;
        }
    }
}

解説

XORなので、ビットごとに
場合の数[1の個数 mod 2][区間長さ(2まで)]
でDPしてます。