ABC249-E RLE

問題へのリンク

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");
            //26
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("2 998244353");
            //0
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("5 998244353");
            //2626
        }
        else if (InputPattern == "Input4") {
            WillReturn.Add("3000 924844033");
            //607425699
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

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

        long UB = N;

        // 場合の数[RLEでの文字数 , 文字数]なインラインDP表
        long[,] DPArr = new long[UB + 1, UB + 1];
        DPArr[0, 0] = 1;
        DPArr[0, 1] = -1;

        for (long LoopY = 0; LoopY <= UB; LoopY++) {
            for (long LoopX = 0; LoopX <= UB; LoopX++) {
                if (LoopY > 0) {
                    // 縦軸は累積和
                    DPArr[LoopX, LoopY] += DPArr[LoopX, LoopY - 1];
                    DPArr[LoopX, LoopY] %= P;
                }

                Action<long, long, long> SendAct = (pNewX, pRangeYSta, pRangeYEnd) =>
                {
                    if (pNewX > UB) return;
                    if (pRangeYSta > UB) return;

                    long SendVal = DPArr[LoopX, LoopY];
                    if (LoopX == 0) {
                        SendVal *= 26;
                    }
                    else {
                        SendVal *= 25;
                    }
                    SendVal %= P;

                    DPArr[pNewX, pRangeYSta] += SendVal;
                    DPArr[pNewX, pRangeYSta] %= P;

                    long ImosRangeYEnd = pRangeYEnd + 1;
                    if (ImosRangeYEnd <= UB) {
                        DPArr[pNewX, ImosRangeYEnd] -= SendVal;
                        if (DPArr[pNewX, ImosRangeYEnd] < 0) {
                            DPArr[pNewX, ImosRangeYEnd] += P;
                        }
                        else {
                            DPArr[pNewX, ImosRangeYEnd] %= P;
                        }
                    }
                };

                // 1文字から9文字
                SendAct(LoopX + 2, LoopY + 1, LoopY + 9);
                // 10文字から99文字
                SendAct(LoopX + 3, LoopY + 10, LoopY + 99);
                // 100文字から999文字
                SendAct(LoopX + 4, LoopY + 100, LoopY + 999);
                // 1000文字から9999文字
                SendAct(LoopX + 5, LoopY + 1000, LoopY + 9999);
            }
        }

        long Answer = 0;
        for (long LoopX = 0; LoopX <= UB - 1; LoopX++) {
            Answer += DPArr[LoopX, UB];
            Answer %= P;
        }
        Console.WriteLine(Answer);
    }
}

解説

場合の数[RLEでの文字数 , 文字数]でDPすることを考えると、
配列の添字が2つなので、二次元表を書いて考察することができます。

横軸が、RLEでの文字数
縦軸が、文字数
で下記の二次元表になります

   0 1 2 3 4 5 6 7 8 9 10 11 12 ・・・
 0
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

遷移が必ず、右下の連続した区間になるので
いもす法で配れば、TLEせずに解くことができます。