ABC362-E Count Arithmetic Subsequences

問題へのリンク

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

    const long Hou = 998244353;

    struct JyoutaiDef
    {
        internal long Cnt;
        internal long Kou1;
        internal long Kou2;
    }

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

        long N = long.Parse(InputList[0]);

        // 場合の数[ハッシュ値]なDP表
        var PrevDP = new Dictionary<decimal, long>();
        PrevDP[0] = 1;

        var AnswerDict = new Dictionary<long, long>();

        foreach (long EachA in AArr) {
            var CurrDP = new Dictionary<decimal, long>(PrevDP);
            foreach (var EachPair in PrevDP) {
                JyoutaiDef CurrJyoutai = GetJyoutai(EachPair.Key);

                Action<decimal, long> AddAct = (pNewHash, Cnt) =>
                {
                    if (CurrDP.ContainsKey(pNewHash) == false) {
                        CurrDP[pNewHash] = 0;
                    }
                    CurrDP[pNewHash] += EachPair.Value;
                    CurrDP[pNewHash] %= Hou;

                    if (AnswerDict.ContainsKey(Cnt) == false) {
                        AnswerDict[Cnt] = 0;
                    }
                    AnswerDict[Cnt] += EachPair.Value;
                    AnswerDict[Cnt] %= Hou;
                };

                if (CurrJyoutai.Cnt == 0) {
                    JyoutaiDef NewJyoutai;
                    NewJyoutai.Cnt = 1;
                    NewJyoutai.Kou1 = 0;
                    NewJyoutai.Kou2 = EachA;
                    AddAct(GetHash(NewJyoutai), 1);
                }
                if (CurrJyoutai.Cnt == 1) {
                    JyoutaiDef NewJyoutai;
                    NewJyoutai.Cnt = 2;
                    NewJyoutai.Kou1 = CurrJyoutai.Kou2;
                    NewJyoutai.Kou2 = EachA;
                    AddAct(GetHash(NewJyoutai), 2);
                }
                if (CurrJyoutai.Cnt >= 2) {
                    long Kousa = CurrJyoutai.Kou2 - CurrJyoutai.Kou1;

                    if (CurrJyoutai.Kou2 + Kousa == EachA) {
                        JyoutaiDef NewJyoutai;
                        NewJyoutai.Cnt = CurrJyoutai.Cnt + 1;
                        NewJyoutai.Kou1 = CurrJyoutai.Kou2;
                        NewJyoutai.Kou2 = EachA;
                        AddAct(GetHash(NewJyoutai), NewJyoutai.Cnt);
                    }
                }
            }
            PrevDP = CurrDP;
        }

        var AnswerList = new List<long>();
        for (long I = 1; I <= N; I++) {
            if (AnswerDict.ContainsKey(I)) {
                AnswerList.Add(AnswerDict[I]);
            }
            else {
                AnswerList.Add(0);
            }
        }
        Console.WriteLine(LongEnumJoin(" ", AnswerList));
    }


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

    static decimal GetHash(JyoutaiDef pJyoutai)
    {
        decimal Hash = 0;
        Hash += pJyoutai.Kou1;
        Hash *= 10000000000;

        Hash += pJyoutai.Kou2;
        Hash *= 100;

        Hash += pJyoutai.Cnt;

        return Hash;
    }

    static JyoutaiDef GetJyoutai(decimal pHash)
    {
        JyoutaiDef WillReturn;
        WillReturn.Cnt = (long)(pHash % 100);

        pHash /= 100;
        pHash = Math.Truncate(pHash);

        WillReturn.Kou2 = (long)(pHash % 10000000000);

        pHash /= 10000000000;
        pHash = Math.Truncate(pHash);
        WillReturn.Kou1 = (long)pHash;

        return WillReturn;
    }
}

解説

{末項の1つ前 , 末項 , 数列の項数} をハッシュ値とし
場合の数[ハッシュ値]でDPしてます。
項数が3以上なら、等差数列の判定もしてます。