ABC217-F Make Pair

問題へのリンク

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

    const long Hou = 998244353;

    static long mN;
    static HashSet<long> mPairSet = new HashSet<long>();

    static ChooseMod mInsChooseMod;

    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]);
        mN = wkArr[0];
        mInsChooseMod = new ChooseMod(mN * 2, Hou);

        foreach (string EachStr in InputList.Skip(1)) {
            SplitAct(EachStr);
            long Hash = GetHash(wkArr[0], wkArr[1]);
            mPairSet.Add(Hash);
        }
        long Result = dfs(1, 2 * mN);
        Console.WriteLine(Result);
    }

    static long GetHash(long pSta, long pEnd)
    {
        long Min = Math.Min(pSta, pEnd);
        long Max = Math.Max(pSta, pEnd);
        return Min * 1000 + Max;
    }

    // メモ化再帰
    static Dictionary<long, long> mMemo = new Dictionary<long, long>();
    static long dfs(long pSta, long pEnd)
    {
        long Hash = GetHash(pSta, pEnd);
        if (mMemo.ContainsKey(Hash)) {
            return mMemo[Hash];
        }

        // 区間長さが2の場合
        if (pSta + 1 == pEnd) {
            if (mPairSet.Contains(Hash)) {
                return 1;
            }
            else {
                return 0;
            }
        }

        // 左端との組み合わせを全探索
        long ResultSum = 0;
        for (long LoopMid = pSta + 1; LoopMid <= pEnd; LoopMid += 2) {
            if (LoopMid == pEnd) {
                if (mPairSet.Contains(GetHash(pSta, pEnd))) {
                    ResultSum += dfs(pSta + 1, pEnd - 1);
                    ResultSum %= Hou;
                }
                continue;
            }

            if (mPairSet.Contains(GetHash(pSta, LoopMid)) == false) {
                continue;
            }

            long PatternCnt1 = dfs(pSta, LoopMid);
            if (pSta + 1 < LoopMid) {
                PatternCnt1 = dfs(pSta + 1, LoopMid - 1);
            }
            long PatternCnt2 = dfs(LoopMid + 1, pEnd);

            long TakeCnt1 = (LoopMid - pSta + 1) / 2;
            long TakeCnt2 = (pEnd - (LoopMid + 1) + 1) / 2;

            long CurrPattern = mInsChooseMod.DeriveChoose(TakeCnt1 + TakeCnt2, TakeCnt1);
            CurrPattern *= PatternCnt1;
            CurrPattern %= Hou;
            CurrPattern *= PatternCnt2;
            CurrPattern %= Hou;

            ResultSum += CurrPattern;
            ResultSum %= Hou;
        }
        return mMemo[Hash] = ResultSum;
    }
}

#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

解説

1 2 3 4 5 6 7 8
の人がいるとして、
左端の人とペアになれるのは、
2,4,6,8
のいずれかですので
左端とペアになる人を全部試すのを、
メモ化再帰で行ってます。