Educational DP Contest R Walk

問題へのリンク

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("4 2");
            WillReturn.Add("0 1 0 0");
            WillReturn.Add("0 0 1 1");
            WillReturn.Add("0 0 0 1");
            WillReturn.Add("1 0 0 0");
            //6
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("3 3");
            WillReturn.Add("0 1 0");
            WillReturn.Add("1 0 1");
            WillReturn.Add("0 0 0");
            //3
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("6 2");
            WillReturn.Add("0 0 0 0 0 0");
            WillReturn.Add("0 0 1 0 0 0");
            WillReturn.Add("0 0 0 0 0 0");
            WillReturn.Add("0 0 0 0 1 0");
            WillReturn.Add("0 0 0 0 0 1");
            WillReturn.Add("0 0 0 0 0 0");
            //1
        }
        else if (InputPattern == "Input4") {
            WillReturn.Add("1 1");
            WillReturn.Add("0");
            //0
        }
        else if (InputPattern == "Input5") {
            WillReturn.Add("10 1000000000000000000");
            WillReturn.Add("0 0 1 1 0 0 0 1 1 0");
            WillReturn.Add("0 0 0 0 0 1 1 1 0 0");
            WillReturn.Add("0 1 0 0 0 1 0 1 0 1");
            WillReturn.Add("1 1 1 0 1 1 0 1 1 0");
            WillReturn.Add("0 1 1 1 0 1 0 1 1 1");
            WillReturn.Add("0 0 0 1 0 0 1 0 1 0");
            WillReturn.Add("0 0 0 1 1 0 0 1 0 1");
            WillReturn.Add("1 0 0 0 1 0 1 0 0 0");
            WillReturn.Add("0 0 0 0 0 1 0 0 0 0");
            WillReturn.Add("1 0 1 1 1 0 1 1 1 0");
            //957538352
        }
        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[] wkArr = InputList[0].Split(' ').Select(pX => long.Parse(pX)).ToArray();
        long K = wkArr[1];

        long[,] FirstMatrixArr = CreateBanArr(InputList.Skip(1));
        long UB = FirstMatrixArr.GetUpperBound(0);

        long[,] Result = DeriveBekijyouMatrix(FirstMatrixArr, K);

        long Answer = 0;
        for (long LoopY = 0; LoopY <= UB; LoopY++) {
            for (long LoopX = 0; LoopX <= UB; LoopX++) {
                Answer += Result[LoopY, LoopX];
                Answer %= Hou;
            }
        }
        Console.WriteLine(Answer);
    }

    // 正方行列2つの積を返す
    static long[,] DeriveMatrixProd(long[,] pMatrix1, long[,] pMatrix2)
    {
        long UB = pMatrix1.GetUpperBound(0);

        // 横の値の配列[行]
        var YokoArrDict = new Dictionary<long, long[]>();
        for (long LoopY = 0; LoopY <= UB; LoopY++) {
            var YokoList = new List<long>();
            for (long LoopX = 0; LoopX <= UB; LoopX++) {
                YokoList.Add(pMatrix1[LoopY, LoopX] % Hou);
            }
            YokoArrDict[LoopY] = YokoList.ToArray();
        }

        // 縦の値の配列[列]
        var TateArrDict = new Dictionary<long, long[]>();
        for (long LoopX = 0; LoopX <= UB; LoopX++) {
            var TateList = new List<long>();
            for (long LoopY = 0; LoopY <= UB; LoopY++) {
                TateList.Add(pMatrix2[LoopY, LoopX] % Hou);
            }
            TateArrDict[LoopX] = TateList.ToArray();
        }

        long[,] MatrixProd = new long[UB + 1, UB + 1];
        for (long LoopY = 0; LoopY <= UB; LoopY++) {
            for (long LoopX = 0; LoopX <= UB; LoopX++) {
                long SumVal = 0;
                for (long K = 0; K <= UB; K++) {
                    SumVal += (YokoArrDict[LoopY][K] * TateArrDict[LoopX][K] % Hou) % Hou;
                    SumVal %= Hou;
                }
                MatrixProd[LoopY, LoopX] = SumVal;
            }
        }
        return MatrixProd;
    }

    // 正方行列のP乗を、繰り返し2乗法で求める
    static long[,] DeriveBekijyouMatrix(long[,] pBaseMatrix, long pP)
    {
        long[,] CurrJyousuu = (long[,])pBaseMatrix.Clone();
        long CurrShisuu = 1;
        long[,] WillReturn = DeriveUnitMatrix(pBaseMatrix.GetUpperBound(0));

        while (true) {
            // 対象ビットが立っている場合
            if ((pP & CurrShisuu) > 0) {
                WillReturn = DeriveMatrixProd(WillReturn, CurrJyousuu);
            }

            CurrShisuu *= 2;
            if (CurrShisuu > pP) return WillReturn;
            CurrJyousuu = DeriveMatrixProd(CurrJyousuu, CurrJyousuu);
        }
    }

    // 単位行列を返す
    static long[,] DeriveUnitMatrix(long UB)
    {
        long[,] WillReturn = new long[UB + 1, UB + 1];
        for (long LoopY = 0; LoopY <= UB; LoopY++) {
            for (long LoopX = 0; LoopX <= UB; LoopX++) {
                if (LoopY == LoopX) {
                    WillReturn[LoopY, LoopX] = 1;
                }
            }
        }
        return WillReturn;
    }

    ////////////////////////////////////////////////////////////////
    // IEnumerable<string>をintの2次元配列に設定する
    ////////////////////////////////////////////////////////////////
    static long[,] CreateBanArr(IEnumerable<string> pStrEnum)
    {
        var StrList = pStrEnum.ToList();
        if (StrList.Count == 0) {
            return new long[0, 0];
        }

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

        SplitAct(StrList[0]);

        long UB_X = IntArr.GetUpperBound(0);
        long UB_Y = StrList.Count - 1;

        long[,] WillReturn = new long[UB_X + 1, UB_Y + 1];

        for (long Y = 0; Y <= UB_Y; Y++) {
            SplitAct(StrList[(int)Y]);
            for (long X = 0; X <= UB_X; X++) {
                WillReturn[X, Y] = IntArr[X];
            }
        }
        return WillReturn;
    }
}

解説

考察すれば、行列累乗だと分かるので、
行列での繰り返し二乗法を使ってます。

類題

TDP M 家