ABC367-E Permute K times

問題へのリンク

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("7 3");
            WillReturn.Add("5 2 6 3 1 4 6");
            WillReturn.Add("1 2 3 5 7 9 11");
            //7 2 3 5 1 9 3
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("4 0");
            WillReturn.Add("3 4 1 2");
            WillReturn.Add("4 3 2 1");
            //4 3 2 1
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("9 1000000000000000000");
            WillReturn.Add("3 7 8 5 9 3 7 4 2");
            WillReturn.Add("9 9 8 2 4 4 3 5 3");
            //3 3 3 3 3 3 3 3 3
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static long mNodeCnt;

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

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

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

        // ファンクショナルグラフを隣接リストで作成
        for (long I = 1; I <= mNodeCnt; I++) {
            mToNodeListDict[I] = new List<long>();
        }
        for (long I = 0; I <= XArr.GetUpperBound(0); I++) {
            long FromNode = I + 1;
            long ToNode = XArr[I];
            mToNodeListDict[FromNode].Add(ToNode);
        }

        var AnswerList = new List<long>();
        var InsFunctionalGraphDoubling = new FunctionalGraphDoubling(1, mNodeCnt, mToNodeListDict, K);
        for (long I = 0; I <= XArr.GetUpperBound(0); I++) {
            long StaNode = I + 1;
            long GoalNode = InsFunctionalGraphDoubling.DeriveGoalNode(StaNode, K);
            AnswerList.Add(AArr[GoalNode - 1]);
        }
        Console.WriteLine(LongEnumJoin(" ", AnswerList.ToArray()));
    }

    // セパレータとLong型の列挙を引数として、結合したstringを返す
    static string LongEnumJoin(string pSeparater, IEnumerable<long> pEnum)
    {
        string[] StrArr = Array.ConvertAll(pEnum.ToArray(), pX => pX.ToString());
        return string.Join(pSeparater, StrArr);
    }
}

// ファンクショナルグラフでのダブリングのクラス
#region FunctionalGraphDoubling
internal class FunctionalGraphDoubling
{
    // 移動後のノード[ノード,2の指数]な2次元配列
    private long[,] mDoublingArr;

    // コンストラクタ
    internal FunctionalGraphDoubling(long pMinNode, long pMaxNode,
        Dictionary<long, List<long>> pToNodeListDict, long pMoveCntLimit)
    {
        long Shisuu2 = 0;
        long Beki2 = 1;
        while (Beki2 <= pMoveCntLimit) {
            Shisuu2++;
            Beki2 *= 2;
        }

        mDoublingArr = new long[pMaxNode + 1, Shisuu2 + 1];

        // 1回だけ移動後のノードを設定
        for (long I = pMinNode; I <= pMaxNode; I++) {
            mDoublingArr[I, 0] = pToNodeListDict[I][0];
        }

        // 2べき回移動後のノードを設定
        for (long J = 1; J <= mDoublingArr.GetUpperBound(1); J++) {
            for (long I = pMinNode; I <= pMaxNode; I++) {
                long Div2Pos = mDoublingArr[I, J - 1];
                long GoalPos = mDoublingArr[Div2Pos, J - 1];
                mDoublingArr[I, J] = GoalPos;
            }
        }
    }

    // 開始ノードと移動回数を引数として、移動後のノードを返す
    internal long DeriveGoalNode(long pStaNode, long pMoveCnt)
    {
        long CurrNode = pStaNode;
        long RestMoveCnt = pMoveCnt;

        long CurrShisuu2 = 0;
        long CurrBeki2 = 1;
        while (RestMoveCnt > 0) {
            if ((RestMoveCnt & CurrBeki2) > 0) {
                CurrNode = mDoublingArr[CurrNode, CurrShisuu2];
                RestMoveCnt -= CurrBeki2;
            }
            CurrShisuu2++;
            CurrBeki2 *= 2;
        }
        return CurrNode;
    }
}
#endregion

解説

ファンクショナルグラフなので、後退解析で
K回の移動を、逆にたどるようにしてます。