Educational DP Contest Y Grid 2

問題へのリンク

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 4 2");
            WillReturn.Add("2 2");
            WillReturn.Add("1 4");
            //3
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("5 2 2");
            WillReturn.Add("2 1");
            WillReturn.Add("4 2");
            //0
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("5 5 4");
            WillReturn.Add("3 1");
            WillReturn.Add("3 5");
            WillReturn.Add("1 3");
            WillReturn.Add("5 3");
            //24
        }
        else if (InputPattern == "Input4") {
            WillReturn.Add("100000 100000 1");
            WillReturn.Add("50000 50000");
            //123445622
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    struct RCInfoDef
    {
        internal long R;
        internal long C;
    }
    static List<RCInfoDef> mRCInfoList = new List<RCInfoDef>();

    static long mH;
    static long mW;

    const long Hou = 1000000007;

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

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

        SplitAct(InputList[0]);
        mH = wkArr[0];
        mW = wkArr[1];

        foreach (string EachStr in InputList.Skip(1)) {
            SplitAct(EachStr);
            RCInfoDef WillAdd;
            WillAdd.R = wkArr[0];
            WillAdd.C = wkArr[1];
            mRCInfoList.Add(WillAdd);
        }
        Solve();
    }

    static void Solve()
    {
        // 壁はX座標とY座標でソートしておく
        mRCInfoList = mRCInfoList.OrderBy(pX => pX.C).ThenBy(pX => pX.R).ToList();

        var InsChooseMod = new ChooseMod(mH + mW, Hou);

        long UB = mRCInfoList.Count - 1;

        // 場合の数[壁のInd , 壁の個数 % 2] なインラインDP表
        long[,] DPArr = new long[UB + 1, 2];

        // 移動元と移動先のペアで2重ループ
        for (int I = -1; I <= UB; I++) {
            long FromX = 1;
            long FromY = 1;
            if (I >= 0) {
                FromX = mRCInfoList[I].C;
                FromY = mRCInfoList[I].R;
            }
            // 移動先のループ
            for (int J = I + 1; J <= UB; J++) {
                if ((FromX <= mRCInfoList[J].C && FromY <= mRCInfoList[J].R) == false) {
                    continue;
                }

                long ToX = mRCInfoList[J].C;
                long ToY = mRCInfoList[J].R;

                Action<int, int, long> UpdateAct = (pNewWallInd, pNewMod2, pAddCnt) =>
                {
                    pAddCnt %= Hou;
                    DPArr[pNewWallInd, pNewMod2] += pAddCnt;
                    DPArr[pNewWallInd, pNewMod2] %= Hou;
                };

                long PatternCnt = InsChooseMod.DeriveChoose(ToX - FromX + ToY - FromY, ToX - FromX);
                if (I == -1) {
                    UpdateAct(J, 1, PatternCnt);
                }
                else {
                    UpdateAct(J, 0, DPArr[I, 1] * PatternCnt);
                    UpdateAct(J, 1, DPArr[I, 0] * PatternCnt);
                }
            }
        }

        long Answer = InsChooseMod.DeriveChoose(mH - 1 + mW - 1, mH - 1);

        for (int I = 0; I <= UB; I++) {
            for (int J = 0; J <= 1; J++) {
                long CurrX = mRCInfoList[I].C;
                long CurrY = mRCInfoList[I].R;
                long GoalPathCnt = InsChooseMod.DeriveChoose(mW - CurrX + mH - CurrY, mW - CurrX);

                long PatternCnt = DPArr[I, J] * GoalPathCnt;
                PatternCnt %= Hou;
                if (J == 0) Answer += PatternCnt;
                if (J == 1) Answer -= PatternCnt;

                if (Answer < 0) Answer += Hou;
                Answer %= Hou;
            }
        }
        Console.WriteLine(Answer);
    }
}

#region ChooseMod
// 二項係数クラス
internal class ChooseMod
{
    private long mHou;

    private long[] mFacArr;
    private long[] mFacInvArr;
    private long[] mInvArr;

    // コンストラクタ
    internal ChooseMod(long pCnt, long pHou)
    {
        mHou = pHou;
        mFacArr = new long[pCnt + 1];
        mFacInvArr = new long[pCnt + 1];
        mInvArr = new long[pCnt + 1];

        mFacArr[0] = mFacArr[1] = 1;
        mFacInvArr[0] = mFacInvArr[1] = 1;
        mInvArr[1] = 1;
        for (int I = 2; I <= pCnt; I++) {
            mFacArr[I] = mFacArr[I - 1] * I % mHou;
            mInvArr[I] = mHou - mInvArr[mHou % I] * (mHou / I) % mHou;
            mFacInvArr[I] = mFacInvArr[I - 1] * mInvArr[I] % mHou;
        }
    }

    // nCrを返す
    internal long DeriveChoose(long pN, long pR)
    {
        if (pN < pR) return 0;
        if (pN < 0 || pR < 0) return 0;
        return mFacArr[pN] * (mFacInvArr[pR] * mFacInvArr[pN - pR] % mHou) % mHou;
    }
}
#endregion

解説

壁Aまたは壁Bまたは壁Cまたは壁Dを通らない経路は、
全体集合 - (壁Aまたは壁Bまたは壁Cまたは壁Dを通る経路)
になるので
包除原理が使えます。

なので、壁をX座標の昇順、Y座標の昇順にソートしてから
壁と壁の組み合わせを全て試しつつ
インラインDPで
場合の数[壁のInd , 壁の個数 % 2]
を更新してます。

包除原理は、偶奇によって足すか引くかが決まるので
偶奇のみ持つようにして、状態数を減らしてます。