ABC113-D Number of Amidakuji

問題へのリンク

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("1 3 2");
            //1
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("1 3 1");
            //2
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("2 3 3");
            //1
        }
        else if (InputPattern == "Input4") {
            WillReturn.Add("2 3 1");
            //5
        }
        else if (InputPattern == "Input5") {
            WillReturn.Add("7 1 1");
            //1
        }
        else if (InputPattern == "Input6") {
            WillReturn.Add("15 8 5");
            //437760187
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    const long Hou = 1000000007;

    static long mH;
    static long mW;
    static long mK;

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

        mH = wkArr[0];
        mW = wkArr[1];
        mK = wkArr[2];

        long UB = mW - 1;
        long GoalInd = mK - 1;

        List<HashSet<long>> RangeSetList = DeriveRangeSetListt();

        // 場合の数[現在位置]なDP表
        long[] PrevDP = new long[UB + 1];
        PrevDP[0] = 1;

        for (long I = 1; I <= mH; I++) {
            long[] CurrDP = new long[UB + 1];

            for (long J = 0; J <= UB; J++) {
                if (PrevDP[J] == 0) continue;

                long SearchLeft = J - 1;
                long SearchRight = J;

                // 左に移動する経路
                long MoveLeftCnt = RangeSetList.Count(pX => pX.Contains(SearchLeft));
                MoveLeftCnt %= Hou;

                // 右に移動する経路
                long MoveRightCnt = RangeSetList.Count(pX => pX.Contains(SearchRight));
                MoveRightCnt %= Hou;

                // 移動しない経路
                long MoveNotCnt = RangeSetList.Count - MoveLeftCnt - MoveRightCnt;
                MoveNotCnt %= Hou;

                // 配るDP
                if (MoveLeftCnt > 0) {
                    CurrDP[J - 1] += PrevDP[J] * MoveLeftCnt;
                    CurrDP[J - 1] %= Hou;
                }
                if (MoveRightCnt > 0) {
                    CurrDP[J + 1] += PrevDP[J] * MoveRightCnt;
                    CurrDP[J + 1] %= Hou;
                }
                if (MoveNotCnt > 0) {
                    CurrDP[J] += PrevDP[J] * MoveNotCnt;
                    CurrDP[J] %= Hou;
                }
            }
            PrevDP = CurrDP;
        }
        Console.WriteLine(PrevDP[GoalInd]);
    }

    struct JyoutaiDef
    {
        internal long CurrRangeID;
        internal HashSet<long> RangeSet;
    }

    // DFSで、行ごとの線の組み合わせを列挙する
    static List<HashSet<long>> DeriveRangeSetListt()
    {
        var WillReturn = new List<HashSet<long>>();

        var Stk = new Stack<JyoutaiDef>();
        JyoutaiDef WillPush;
        WillPush.CurrRangeID = 0;
        WillPush.RangeSet = new HashSet<long>();
        Stk.Push(WillPush);

        long MaxRangeID = mW - 2;

        while (Stk.Count > 0) {
            JyoutaiDef Popped = Stk.Pop();

            WillReturn.Add(Popped.RangeSet);

            for (long I = Popped.CurrRangeID; I <= MaxRangeID; I++) {
                WillPush.CurrRangeID = I + 2;
                WillPush.RangeSet = new HashSet<long>(Popped.RangeSet);
                WillPush.RangeSet.Add(I);
                Stk.Push(WillPush);
            }
        }
        return WillReturn;
    }
}

解説

行ごとの、線の組み合わせを事前にDFSで列挙しておいて、
DPで解いてます。