ABC248-F Keep Connect

問題へのリンク

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 998244353");
            //7 15
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("16 999999937");
            //46 1016 14288 143044 1079816 6349672 29622112 110569766 330377828 784245480 453609503 38603306 44981526 314279703 408855776
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static long mN;
    static long mP;

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

        Solve(mN - 1);
    }

    static void Solve(long pCutLimit)
    {
        long UB = pCutLimit;

        // 場合の数[切断した辺の数 , 上下の接続] なDP表
        long[,] PrevDP = new long[UB + 1, 2];
        PrevDP[0, 1] = 1;
        PrevDP[1, 0] = 1;

        for (long I = 2; I <= mN; I++) {
            long[,] CurrDP = new long[UB + 1, 2];
            for (long J = 0; J <= UB; J++) {
                for (long K = 0; K <= 1; K++) {
                    if (PrevDP[J, K] == 0) continue;

                    Action<long, long, long> AddVal = (pNewJ, pNewK, pAddVal) =>
                    {
                        if (pNewJ > UB) return;
                        CurrDP[pNewJ, pNewK] += pAddVal;
                        CurrDP[pNewJ, pNewK] %= mP;
                    };

                    // 上下が接続している場合
                    if (K == 1) {
                        // 0個切断が1通り
                        AddVal(J, 1, PrevDP[J, K]);

                        // 1個切断が3通り
                        AddVal(J + 1, 1, PrevDP[J, K] * 3);

                        // 2個切断が2通り
                        AddVal(J + 2, 0, PrevDP[J, K] * 2);
                    }

                    // 上下が接続してない場合
                    if (K == 0) {
                        // 0個切断が1通り
                        AddVal(J, 1, PrevDP[J, K]);

                        // 1個切断が1通り
                        AddVal(J + 1, 0, PrevDP[J, K]);
                    }
                }
            }
            PrevDP = CurrDP;
        }

        var AnswerList = new List<long>();
        for (long I = 1; I <= pCutLimit; I++) {
            AnswerList.Add(PrevDP[I, 1]);
        }

        // セパレータとLong型の列挙を引数として、結合したstringを返す
        Func<string, IEnumerable<long>, string> LongEnumJoin = (pSeparater, pEnum) =>
        {
            string[] StrArr = Array.ConvertAll(pEnum.ToArray(), pX => pX.ToString());
            return string.Join(pSeparater, StrArr);
        };

        Console.WriteLine(LongEnumJoin(" ", AnswerList));
    }
}

解説

正方形が横に連続した状態で
最初は一番左の|の切断有無を決定し、
次からは、コの箇所の3辺の切断有無を決定するDPで
場合の数[切断した辺の数 , 上下の接続]
を更新してます。

遷移は、図を書いた上で、オセロの石で考察すると分かります。