ABC-030-D へんてこ辞書

■■■問題■■■

ミカミくんは怪しい英単語帳を使っています。
その単語帳にはN個の単語の意味が載っており、
単語iの説明には「単語 bi と同じ意味である」とだけ書いてあります。

ここで、i番目の単語を単語iと呼ぶことにします。
ミカミくんはまだ一つの英単語も知らないので、
単語iの意味を調べようとしたとき、単語biの意味を調べようとします。

ミカミくんは真面目なので、今までにすでに調べようとしたことのある単語でも同じように単語帳をひき続けます。
しかし、残念ながらこの単語帳では英単語の意味自体はどこにも書いていないため、意味を知ることはできません。
ある単語iを調べようとして、単語帳を参照し、単語biを調べようとするまでを1ステップとします。

ミカミくんが単語iを調べようとして、kステップ経ったとき、
ミカミくんはどの単語を調べようとしているでしょうか？

■■■入力■■■

N a
k
b1 b2 ・・・ bN

●1行目には、単語の数 N(2 <= N <= 10万) とミカミくんが調べようとしている
              単語の番号 a(1 <= a <= N) がスペース区切りで与えられる。
●2行目には、ミカミくんが単語を調べるステップ数 k(1 <= k <= 10の10万乗) が与えられる。
●3行目には、各単語の説明を表すN個の整数 b1,・・・,bN が空白区切りで与えられる。
●1 <= bi <= Nかつbi != i(1 <= i <= N) であることが保証される。

■■■出力■■■

ミカミくんが単語aを調べようとしてからkステップ経ったとき、
調べようとしている単語の番号を1行に出力せよ。出力の末尾にも改行をいれること。

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("6 4");
            WillReturn.Add("5");
            WillReturn.Add("2 3 1 2 6 5");
            //3
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("4 1");
            WillReturn.Add("100000000000000000000");
            WillReturn.Add("2 3 4 1");
            //1
            //kはたいへん大きくなることがあります
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("8 1");
            WillReturn.Add("1");
            WillReturn.Add("2 3 4 5 3 2 4 5");
            //2
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static long a;
    static string StrK;
    static long[] BArr;

    static void Main()
    {
        List<string> InputList = GetInputList();
        a = InputList[0].Split(' ').Select(X => long.Parse(X)).Last();
        StrK = InputList[1];
        BArr = InputList[2].Split(' ').Select(X => long.Parse(X)).ToArray();

        Console.WriteLine(SolveQuick());
    }

    static long[] SuuretuArr;
    static long StartInd;

    //クイックに解く
    static long SolveQuick()
    {
        CreateSuuretu();

        //非循環部の項数
        long NonCycleCnt = StartInd;

        //循環部の項数
        long CycleCnt = SuuretuArr.Length - NonCycleCnt;

        //String型のkを解析する
        bool IsOverNonCycleCnt = false; //kが非循環部の項数超えか？

        //合同式の考え方を使うと、
        //(k-NonCycleCnt) mod CycleCnt
        //((k mod CycleCnt) - (NonCycleCnt mod CycleCnt)) mod CycleCnt

        //kの値。ただし、kが非循環部の項数超えなら、(k mod CycleCnt)
        long LongK = 0;

        foreach (char EachChar in StrK) {
            int wkInt = EachChar - '0';
            LongK *= 10;
            LongK += wkInt;
            if (IsOverNonCycleCnt == false) {
                if (LongK > NonCycleCnt) IsOverNonCycleCnt = true;
            }
            if (IsOverNonCycleCnt) LongK %= CycleCnt;
        }

        //場合1 kが非循環部の項数以下の場合
        if (IsOverNonCycleCnt == false)
            return SuuretuArr[LongK - 1];

        //場合2 kが非循環部の項数超えの場合
        LongK = (LongK - NonCycleCnt % CycleCnt) % CycleCnt;
        ModTyousei(ref LongK, CycleCnt);

        //123456789で3を法とすると
        //123123123としたいので
        //3を法としてのModが0なら、法を足す
        if (LongK == 0) LongK = CycleCnt;
        return SuuretuArr[NonCycleCnt + LongK - 1];
    }

    //Modが負なら法を加算する
    static void ModTyousei(ref long pMod, long pHou)
    {
        if (pMod < 0) pMod += pHou;
    }

    //1単語目からの数列と、循環開始の項番号を求める
    static void CreateSuuretu()
    {
        var SuuretuList = new List<long>();
        long CurrNo = BArr[a - 1];

        while (true) {
            long wkInd = SuuretuList.IndexOf(CurrNo);
            if (wkInd >= 0) {
                StartInd = wkInd;
                SuuretuArr = SuuretuList.ToArray();
                break;
            }

            SuuretuList.Add(CurrNo);
            CurrNo = BArr[CurrNo - 1];
        }
    }
}

解説

合同式の変形を行って、10の10万乗に対応してます。