ARC189-A Reversi 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("6");
            WillReturn.Add("1 1 1 1 1 0");
            //3
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("10");
            WillReturn.Add("1 1 1 1 1 0 1 1 1 0");
            //9
        }
        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();
    }

    const long Hou = 998244353;

    static void Main()
    {
        List<string> InputList = GetInputList();
        long[] GoalArr = GetSplitArr(InputList[1]);
        long UB = GoalArr.GetUpperBound(0);

        long[] FirstArr = new long[GoalArr.Length];
        for (long I = 0; I <= UB; I++) {
            if (I % 2 == 0) FirstArr[I] = 1;
            if (I % 2 == 1) FirstArr[I] = 0;
        }

        // 必要条件1 左端が一致
        if (GoalArr[0] != FirstArr[0]) {
            Console.WriteLine(0);
            return;
        }

        // 必要条件2 右端が一致
        if (GoalArr[UB] != FirstArr[UB]) {
            Console.WriteLine(0);
            return;
        }

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

        // 必要条件3 全て奇数長であること
        foreach (RunLenLongArr.RunLenLongArrInfo EachRunLenLongArrInfo in RunLenLongArrInfoList) {
            if (EachRunLenLongArrInfo.RunLen % 2 == 0) {
                Console.WriteLine(0);
                return;
            }
        }

        // 変換回数を求める
        long ChangeCntSum = 0;
        foreach (RunLenLongArr.RunLenLongArrInfo EachRunLenLongArrInfo in RunLenLongArrInfoList) {
            ChangeCntSum += (EachRunLenLongArrInfo.RunLen - 1) / 2;
        }

        // 場合の数[ゴール配列の連長圧縮での長さ]なDict
        var PatternDict = new Dictionary<long, long>();
        long MaxRunLen = RunLenLongArrInfoList.Max(pX => pX.RunLen);

        PatternDict[1] = 1;
        PatternDict[3] = 1;

        for (long I = 5; I <= MaxRunLen; I += 2) {
            PatternDict[I] = PatternDict[I - 2] * (I - 2);
            PatternDict[I] %= Hou;
        }

        long RestSpace = ChangeCntSum;

        var InsChooseMod = new ChooseMod(RestSpace, Hou);

        long Answer = 1;
        foreach (RunLenLongArr.RunLenLongArrInfo EachRunLenLongArrInfo in RunLenLongArrInfoList) {
            if (EachRunLenLongArrInfo.RunLen == 1) continue;
            long CurrChangeCnt = (EachRunLenLongArrInfo.RunLen - 1) / 2;
            Answer *= InsChooseMod.DeriveChoose(RestSpace, CurrChangeCnt);
            Answer %= Hou;
            Answer *= PatternDict[EachRunLenLongArrInfo.RunLen];
            Answer %= Hou;

            RestSpace -= CurrChangeCnt;
        }
        Console.WriteLine(Answer);
    }
}

#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>();

        // 空配列の対応
        if (pArr.Length == 0) {
            return WillReturn;
        }

        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

#region ChooseMod
// 二項係数クラス (nCr を nの最大値指定で事前準備し、高速に求める)
internal class ChooseMod
{
    private long mHou;

    private long[] mFacArr;
    private long[] mFacInvArr;
    private long[] mInvArr;

    // コンストラクタ
    internal ChooseMod(long pCnt, long pHou)
    {
        mHou = pHou;
        mFacArr = new long[pCnt + 1];
        mFacInvArr = new long[pCnt + 1];
        mInvArr = new long[pCnt + 1];

        mFacArr[0] = mFacArr[1] = 1;
        mFacInvArr[0] = mFacInvArr[1] = 1;
        mInvArr[1] = 1;
        for (int I = 2; I <= pCnt; I++) {
            mFacArr[I] = mFacArr[I - 1] * I % mHou;
            mInvArr[I] = mHou - mInvArr[mHou % I] * (mHou / I) % mHou;
            mFacInvArr[I] = mFacInvArr[I - 1] * mInvArr[I] % mHou;
        }
    }

    // nCrを返す
    internal long DeriveChoose(long pN, long pR)
    {
        if (pN < pR) return 0;
        if (pN < 0 || pR < 0) return 0;
        return mFacArr[pN] * (mFacInvArr[pR] * mFacInvArr[pN - pR] % mHou) % mHou;
    }
}
#endregion

解説

ダイソーのオセロセットで考察します。

すると以下の3つの必要条件が分かります。
必要条件1 左端の白黒が一致
必要条件2 右端の白黒が一致
必要条件3 ゴール配列をRLEした時に全て奇数長
さらに考察すると、これは十分条件だと分かります。

後は、RLEでの奇数長ごとに、何回でゴール配列に変更できるかを求めます。
この手数合計が10の場合
□□□□□□□□□□
という空欄をイメージし、各RLEごとの操作の配置を choose で求め、
積の法則で解を求めることができます。

また
RLEごとの変換の場合の数は、以下の考え方で求めることができます。

ケース1 これは1通り
元配列 ○●○
ゴール ○○○

ケース2 これは3通り
元配列 ○●○●○
ゴール ○○○○○

ケース3 これは3*5通り(なぜなら、ケース2に遷移する場合が5通りあるから)
元配列 ○●○●○●○
ゴール ○○○○○○○

ケース4 これは3*5*7通り(なぜなら、ケース3に遷移する場合が7通りあるから)
元配列 ○●○●○●○●○
ゴール ○○○○○○○○○