ABC425-E Count Sequences 2

問題へのリンク

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 1000000000");
            WillReturn.Add("2");
            WillReturn.Add("2 2");
            WillReturn.Add("5");
            WillReturn.Add("1 1 1 1 1");
            WillReturn.Add("6");
            WillReturn.Add("1 2 3 4 5 6");
            //6
            //120
            //230379200
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("3 998244353");
            WillReturn.Add("1");
            WillReturn.Add("1");
            WillReturn.Add("3");
            WillReturn.Add("4 2 5");
            WillReturn.Add("10");
            WillReturn.Add("500 500 500 500 500 500 500 500 500 500");
            //1
            //6930
            //261233246
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static long[] GetSplitArr(string pStr)
    {
        return (pStr == "" ? new string[0] : pStr.Split(' ')).Select(pX => long.Parse(pX)).ToArray();
    }

    static long Hou;

    static long[][] mPascalSankakukeiJagArr;
    static void Main()
    {
        List<string> InputList = GetInputList();

        long[] wkArr = { };
        Action<string> SplitAct = (pStr) => wkArr = GetSplitArr(pStr);

        SplitAct(InputList[0]);
        Hou = wkArr[1];

        mPascalSankakukeiJagArr = CreatePascalSankakukeiJagArr(5000, Hou);

        for (int I = 2; I <= InputList.Count - 1; I += 2) {
            long[] CArr = GetSplitArr(InputList[I]);
            long Result = Solve(CArr);
            Console.WriteLine(Result);
        }
    }

    static long Solve(long[] pCArr)
    {
        long SumCnt = pCArr.Sum();

        long Answer = 1;
        foreach (long EachC in pCArr) {
            Answer *= mPascalSankakukeiJagArr[SumCnt][EachC];
            SumCnt -= EachC;
            Answer %= Hou;
        }
        return Answer;
    }

    // パスカルの三角形のジャグ配列を返す
    // 引数1 (0始まりの)木の高さ上限
    // 引数2 法
    // 戻り値 ジャグ配列
    // [0][0]          1   
    // [1][0から1]    1 1
    // [2][0から2]   1 2 1
    // [3][0から3]  1 3 3 1
    // [4][0から4] 1 4 6 4 1
    static long[][] CreatePascalSankakukeiJagArr(long pDepth, long pHou)
    {
        long[][] JagArr = new long[pDepth + 1][];

        for (long I = 0; I <= pDepth; I++) {
            JagArr[I] = new long[I + 1];
            long CurrUB = JagArr[I].GetUpperBound(0);

            JagArr[I][0] = 1;
            JagArr[I][CurrUB] = 1;

            if (I > 0) {
                for (long J = 1; J < CurrUB; J++) {
                    long AddVal1 = JagArr[I - 1][J - 1];
                    long AddVal2 = JagArr[I - 1][J];
                    JagArr[I][J] = AddVal1 + AddVal2;
                    JagArr[I][J] %= pHou;
                }
            }
        }
        return JagArr;
    }
}

解説

1が1個
2が2個
3が3個

□□□□□□
に順番に埋めていくと考えれば
1C6 * 2C5 * 3C3
で通り数を求めることができます。

chooseを高速で求めるために、
パスカルの三角形を最初に作成してます。