ARC023-C タコヤ木

問題へのリンク

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

    const long Hou = 1000000007;

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

        List<RunLenLongArr.RunLenLongArrInfo> RunLenLongArrInfoList =
            RunLenLongArr.DeriveRunLenLongArrInfoList(AArr);

        long Answer = 1;
        for (int I = 0; I <= RunLenLongArrInfoList.Count - 1; I++) {
            if (RunLenLongArrInfoList[I].AppearNum == -1) {
                //Console.WriteLine("AppearNum={0},RunLen={1}",
                //    RunLenIntArrInfoList[I].AppearNum,
                //    RunLenIntArrInfoList[I].RunLen);

                long PrevNum = RunLenLongArrInfoList[I - 1].AppearNum;
                long NextNum = RunLenLongArrInfoList[I + 1].AppearNum;

                long Result = DerivePatternCnt(RunLenLongArrInfoList[I].RunLen, NextNum - PrevNum);
                Answer *= Result;
                Answer %= Hou;
            }
        }
        Console.WriteLine(Answer);
    }

    static long DerivePatternCnt(long pTakeCnt, long pAddCnt)
    {
        return DeriveChoose(pTakeCnt + pAddCnt, pTakeCnt);
    }

    // nCr (mod Hou)を求める
    static long DeriveChoose(long pN, long pR)
    {
        if (pN < pR) return 0;

        pR = Math.Min(pR, pN - pR);

        long WillReturn = 1;
        for (long I = pN - pR + 1; I <= pN; I++) {
            WillReturn *= I;
            WillReturn %= Hou;
        }
        for (long I = 2; I <= pR; I++) {
            WillReturn *= DeriveGyakugen(I);
            WillReturn %= Hou;
        }
        return WillReturn;
    }

    // 引数の逆元を求める
    static long DeriveGyakugen(long pLong)
    {
        return DeriveBekijyou(pLong, Hou - 2, Hou);
    }

    // 繰り返し2乗法で、(NのP乗) Mod Mを求める
    static long DeriveBekijyou(long pN, long pP, long pM)
    {
        long CurrJyousuu = pN % pM;
        long CurrShisuu = 1;
        long WillReturn = 1;

        while (true) {
            // 対象ビットが立っている場合
            if ((pP & CurrShisuu) > 0) {
                WillReturn = (WillReturn * CurrJyousuu) % pM;
            }

            CurrShisuu *= 2;
            if (CurrShisuu > pP) return WillReturn;
            CurrJyousuu = (CurrJyousuu * CurrJyousuu) % pM;
        }
    }
}

#region RunLen
// ランレングス圧縮(longの配列)
internal class RunLenLongArr
{
    // ランレングス圧縮情報
    internal struct RunLenLongArrInfo
    {
        internal long AppearNum;
        internal long RunLen;
    }

    // ランレングス圧縮結果を返す
    internal static List<RunLenLongArrInfo> DeriveRunLenLongArrInfoList(long[] pArr)
    {
        var WillReturn = new List<RunLenLongArrInfo>();

        long PrevNum = pArr[0];
        long SeqLen = 0;
        for (int I = 0; I <= pArr.GetUpperBound(0); I++) {
            if (pArr[I] != PrevNum) {
                RunLenLongArrInfo WillAdd;
                WillAdd.AppearNum = PrevNum;
                WillAdd.RunLen = SeqLen;
                WillReturn.Add(WillAdd);
                SeqLen = 0;
                PrevNum = pArr[I];
            }
            SeqLen++;

            if (I == pArr.GetUpperBound(0)) {
                RunLenLongArrInfo WillAdd;
                WillAdd.AppearNum = pArr[I];
                WillAdd.RunLen = SeqLen;
                WillReturn.Add(WillAdd);
            }
        }
        return WillReturn;
    }
}
#endregion

解説

10 -1 -1 -1 15
について考察すると、

10から15の区間から
●取る
●1増やす
の2つの行動の組合せと場合の数が対応すると分かります。

取るが3個で、1増やすが、15-10で5個です。
取 取 取 増 増 増 増 増
でこれは、Chooseで求めることができます。

別の考え方として、
10 11 12 13 14 15 から、重複を許して、3個取ると考えて
重複組合せの公式を使うこともできます。