ABC179-D Leaping Tak

問題へのリンク

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

    const long Hou = 998244353;

    struct LRInfoDef
    {
        internal long L;
        internal long R;
    }

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

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

        SplitAct(InputList[0]);
        long N = wkArr[0];

        var LRInfoList = new List<LRInfoDef>();
        foreach (string EachStr in InputList.Skip(1)) {
            SplitAct(EachStr);
            LRInfoDef WillAdd;
            WillAdd.L = wkArr[0];
            WillAdd.R = wkArr[1];
            LRInfoList.Add(WillAdd);
        }

        // 場合の数[現在位置]
        long UB = N;
        long[] DPArr = new long[UB + 1];
        DPArr[1] = 1;

        // 配るDPで、いもす法で配る用の配列
        long[] RunSumArr = new long[UB + 1];

        for (int I = 1; I <= UB; I++) {
            // 累積和を求める
            RunSumArr[I] += RunSumArr[I - 1];
            RunSumArr[I] = DeriveMod(RunSumArr[I]);

            DPArr[I] += RunSumArr[I];
            DPArr[I] = DeriveMod(DPArr[I]);

            // 配るDPで、いもす法で配る
            foreach (LRInfoDef EachLRInfo in LRInfoList) {
                long RangeSta = I + EachLRInfo.L;
                long RangeEnd = I + EachLRInfo.R + 1;

                if (RangeSta <= UB) {
                    RunSumArr[RangeSta] += DPArr[I];
                    RunSumArr[RangeSta] = DeriveMod(RunSumArr[RangeSta]);
                }
                if (RangeEnd <= UB) {
                    RunSumArr[RangeEnd] += DPArr[I] * (-1);
                    RunSumArr[RangeEnd] = DeriveMod(RunSumArr[RangeEnd]);
                }
            }
        }
        Console.WriteLine(DPArr[UB]);
    }

    static long DeriveMod(long pTarget)
    {
        pTarget %= Hou;
        if (pTarget < 0) pTarget += Hou;
        return pTarget;
    }
}

解説

配るDPで、いもす法で配ってます。