ABC201-E Xor Distances

問題へのリンク

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 1");
            WillReturn.Add("1 3 3");
            //6
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("5");
            WillReturn.Add("3 5 2");
            WillReturn.Add("2 3 2");
            WillReturn.Add("1 5 1");
            WillReturn.Add("4 5 13");
            //62
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("10");
            WillReturn.Add("5 7 459221860242673109");
            WillReturn.Add("6 8 248001948488076933");
            WillReturn.Add("3 5 371922579800289138");
            WillReturn.Add("2 5 773108338386747788");
            WillReturn.Add("6 10 181747352791505823");
            WillReturn.Add("1 3 803225386673329326");
            WillReturn.Add("7 8 139939802736535485");
            WillReturn.Add("9 10 657980865814127926");
            WillReturn.Add("2 4 146378247587539124");
            //241240228
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    const long Hou = 1000000007;

    struct EdgeInfoDef
    {
        internal long ToNode;
        internal long Cost;
    }

    // 隣接リスト
    static Dictionary<long, List<EdgeInfoDef>> mEdgeListDict = new Dictionary<long, List<EdgeInfoDef>>();

    static long mRootNode;

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

        long[] wkArr = { };
        Action<string> SplitAct = pStr =>
            wkArr = pStr.Split(' ').Select(pX => long.Parse(pX)).ToArray();

        foreach (string EachStr in InputList.Skip(1)) {
            SplitAct(EachStr);
            long FromNode = wkArr[0];
            long ToNode = wkArr[1];
            long Cost = wkArr[2];

            if (mEdgeListDict.ContainsKey(FromNode) == false) {
                mEdgeListDict[FromNode] = new List<EdgeInfoDef>();
            }
            EdgeInfoDef WillAdd1;
            WillAdd1.ToNode = ToNode;
            WillAdd1.Cost = Cost;
            mEdgeListDict[FromNode].Add(WillAdd1);

            if (mEdgeListDict.ContainsKey(ToNode) == false) {
                mEdgeListDict[ToNode] = new List<EdgeInfoDef>();
            }
            EdgeInfoDef WillAdd2;
            WillAdd2.ToNode = FromNode;
            WillAdd2.Cost = Cost;
            mEdgeListDict[ToNode].Add(WillAdd2);
        }
        mRootNode = mEdgeListDict.Keys.Min();

        List<JyoutaiDef> BFSResultList = ExecBFS();
        long[] CostSumArr = BFSResultList.Select(pX => pX.CostSum).ToArray();
        long Answer = DeriveAnswer(CostSumArr);
        Console.WriteLine(Answer);
    }

    struct JyoutaiDef
    {
        internal long NodeID;
        internal long CostSum;
    }

    // BFSを行い、各ノードの根からの最短距離を求める
    static List<JyoutaiDef> ExecBFS()
    {
        var WillReturn = new List<JyoutaiDef>();

        var Que = new Queue<JyoutaiDef>();
        JyoutaiDef WillEnque;
        WillEnque.NodeID = mRootNode;
        WillEnque.CostSum = 0;
        Que.Enqueue(WillEnque);

        var VisitedSet = new HashSet<long>();
        VisitedSet.Add(mRootNode);

        while (Que.Count > 0) {
            JyoutaiDef Dequeued = Que.Dequeue();
            WillReturn.Add(Dequeued);

            if (mEdgeListDict.ContainsKey(Dequeued.NodeID)) {
                foreach (EdgeInfoDef EachEdge in mEdgeListDict[Dequeued.NodeID]) {
                    // 再訪防止
                    if (VisitedSet.Add(EachEdge.ToNode) == false) {
                        continue;
                    }

                    WillEnque.NodeID = EachEdge.ToNode;

                    // 加算ではなく排他的論理和を求める
                    WillEnque.CostSum = Dequeued.CostSum ^ EachEdge.Cost;

                    Que.Enqueue(WillEnque);
                }
            }
        }
        return WillReturn;
    }

    // 各ノードまでの最短距離のArrから、解を計算する
    static long DeriveAnswer(long[] pCostSumArr)
    {
        long MaxBit = long.MinValue;
        foreach (long EachCostSum in pCostSumArr) {
            string BinStr = Convert.ToString(EachCostSum, 2);
            MaxBit = Math.Max(MaxBit, BinStr.Length);
        }

        long Answer = 0;

        for (long I = 1; I <= MaxBit; I++) {
            long CurrBit = (1L << (int)(I - 1));
            long CntOne = pCostSumArr.Count(pX => (pX & CurrBit) == 0);
            long CntZero = pCostSumArr.Count(pX => (pX & CurrBit) > 0);

            // 場合の数の積の法則
            long CurrSum = CurrBit;
            CurrSum %= Hou;
            CurrSum *= CntOne;
            CurrSum %= Hou;
            CurrSum *= CntZero;
            CurrSum %= Hou;

            Answer += CurrSum;
            Answer %= Hou;
        }
        return Answer;
    }
}

解説

考察として、
根付き木として考えると、
ノード間の距離は、根からの経路同士の排他的論理和になります。
2を法としてのビット単位の足し算なので、
根からの共通箇所は、ダブルカウントされて0になるからです。

全てのノード対の総和を知りたいので、
ビットごとに、根から各ノードまでの経路の排他的論理和
が0になるノード個数と、1になるノード個数で
積の法則を使えば、解を求めることができます。