ABC147-D Xor Sum 4

問題へのリンク

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 2 3");
            //6
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("10");
            WillReturn.Add("3 1 4 1 5 9 2 6 5 3");
            //237
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("10");
            WillReturn.Add("3 14 159 2653 58979 323846 2643383 27950288 419716939 9375105820");
            //103715602
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    const long Hou = 1000000007;

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

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

        // 0の個数[2のべき乗]なDict
        var Cnt0Dict = new Dictionary<long, long>();

        // 1の個数[2のべき乗]
        var Cnt1Dict = new Dictionary<long, long>();

        foreach (long EachLong in AArr) {
            long CurrVal = EachLong;
            long Bekijyou = 1;

            while (true) {
                if (Cnt0Dict.ContainsKey(Bekijyou) == false) Cnt0Dict[Bekijyou] = 0;
                if (Cnt1Dict.ContainsKey(Bekijyou) == false) Cnt1Dict[Bekijyou] = 0;

                long Mod2 = CurrVal % 2;
                if (Mod2 == 0) Cnt0Dict[Bekijyou]++;
                if (Mod2 == 1) Cnt1Dict[Bekijyou]++;

                if (CurrVal == 0) break;

                CurrVal /= 2;
                Bekijyou *= 2;
            }
        }

        // 前ゼロの分を補完
        foreach (long EachKey in Cnt1Dict.Keys) {
            long CntSum = Cnt1Dict[EachKey] + Cnt0Dict[EachKey];
            if (CntSum < AArr.Length) {
                long Rest = AArr.Length - CntSum;
                Cnt0Dict[EachKey] += Rest;
            }
        }

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

        long Answer = 0;
        foreach (var EachPair in Cnt0Dict) {
            long CurrVal0 = EachPair.Value;
            long CurrVal1 = Cnt1Dict[EachPair.Key];

            long CurrKetaSum = EachPair.Key % Hou;
            CurrKetaSum *= (CurrVal0 * CurrVal1) % Hou;
            CurrKetaSum %= Hou;

            Answer += CurrKetaSum;
            Answer %= Hou;
        }
        Console.WriteLine(Answer);
    }
}

解説

排他的論理和なのでビットごとに考えることができます。

1 2 3 4 5 6 7
というサンプルで考え、2進数で表すと
001
010
011
100
101
110
111
となります。

1ビット目に注目すると
全部で 7*6/2 = 210 通りの 0と1の組み合わせの中で
排他的論理和の結果が1になるのは、片方が0で片方が1になるペアなので
0の数が3で、1の数が4なので
3*4 = 12 通りの 排他的論理和が1になる組み合わせがあります。

他のビットも同様にして、
全ての組み合わせの排他的論理和の総和を求めることができます。