ARC107-C Shuffle Permutation

問題へのリンク

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 13");
            WillReturn.Add("3 2 7");
            WillReturn.Add("4 8 9");
            WillReturn.Add("1 6 5");
            //12
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("10 165");
            WillReturn.Add("82 94 21 65 28 22 61 80 81 79");
            WillReturn.Add("93 35 59 85 96 1 78 72 43 5");
            WillReturn.Add("12 15 97 49 69 53 18 73 6 58");
            WillReturn.Add("60 14 23 19 44 99 64 17 29 67");
            WillReturn.Add("24 39 56 92 88 7 48 75 36 91");
            WillReturn.Add("74 16 26 10 40 63 45 76 86 3");
            WillReturn.Add("9 66 42 84 38 51 25 2 33 41");
            WillReturn.Add("87 54 57 62 47 31 68 11 83 8");
            WillReturn.Add("46 27 55 70 52 98 20 77 89 34");
            WillReturn.Add("32 71 30 50 90 4 37 95 13 100");
            //348179577
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    const long Hou = 998244353;

    static int mK;
    static int[,] mBanArr;
    static int UB;

    // 隣接リスト
    static Dictionary<int, List<int>> mToNodeListDict = new Dictionary<int, List<int>>();

    static void Main()
    {
        List<string> InputList = GetInputList();
        int[] wkArr = InputList[0].Split(' ').Select(pX => int.Parse(pX)).ToArray();
        mK = wkArr[1];
        mBanArr = CreateBanArr(InputList.Skip(1));
        UB = mBanArr.GetUpperBound(0);

        long Cnt1 = ExecCC();

        mBanArr = Kaiten90do(mBanArr);
        long Cnt2 = ExecCC();

        long Answer = Cnt1 * Cnt2;
        Answer %= Hou;
        Console.WriteLine(Answer);
    }

    // 連結成分分解を行い、要素数の階乗の、総積を返す
    static long ExecCC()
    {
        mToNodeListDict.Clear();

        Action<int, int> ConnAct = (pNode1, pNode2) =>
        {
            if (mToNodeListDict.ContainsKey(pNode1) == false) {
                mToNodeListDict[pNode1] = new List<int>();
            }
            mToNodeListDict[pNode1].Add(pNode2);
        };

        for (int Y1 = 0; Y1 <= UB; Y1++) {
            for (int Y2 = Y1 + 1; Y2 <= UB; Y2++) {
                bool IsOK = true;
                for (int X = 0; X <= UB; X++) {
                    int SumVal = mBanArr[X, Y1] + mBanArr[X, Y2];
                    if (SumVal > mK) {
                        IsOK = false;
                        break;
                    }
                }
                if (IsOK == false) continue;
                ConnAct(Y1, Y2);
                ConnAct(Y2, Y1);
            }
        }

        Dictionary<int, List<int>> CCListDict = DeriveCCListDict(0, UB);

        long Answer = 1;
        foreach (List<int> EachList in CCListDict.Values) {
            for (long I = 2; I <= EachList.Count(); I++) {
                Answer *= I;
                Answer %= Hou;
            }
        }
        return Answer;
    }

    struct JyoutaiDef1
    {
        internal int CurrNode; // 現在ノード
    }

    // 連結成分分解を行い、ノードList[代表ノード]なDictを返す
    static Dictionary<int, List<int>> DeriveCCListDict(int pMinNode, int pMaxNode)
    {
        var CCListDict = new Dictionary<int, List<int>>();

        var VisitedSet = new HashSet<int>();
        for (int I = pMinNode; I <= pMaxNode; I++) {
            if (VisitedSet.Contains(I)) continue;
            CCListDict[I] = new List<int>();
            CCListDict[I].Add(I);

            var Stk = new Stack<JyoutaiDef1>();
            JyoutaiDef1 WillPush;
            WillPush.CurrNode = I;
            Stk.Push(WillPush);
            VisitedSet.Add(I);

            while (Stk.Count > 0) {
                JyoutaiDef1 Popped = Stk.Pop();

                // 子ノード無しの場合
                if (mToNodeListDict.ContainsKey(Popped.CurrNode) == false)
                    continue;

                foreach (int EachToNode in mToNodeListDict[Popped.CurrNode]) {
                    if (VisitedSet.Add(EachToNode) == false) continue;
                    CCListDict[I].Add(EachToNode);

                    WillPush.CurrNode = EachToNode;
                    Stk.Push(WillPush);
                }
            }
        }
        return CCListDict;
    }

    // 右に90度回転させた盤面を返す
    static Type[,] Kaiten90do<Type>(Type[,] pBanArr)
    {
        Type[,] WillReturn = new Type[pBanArr.GetUpperBound(1) + 1,
                                      pBanArr.GetUpperBound(0) + 1];

        for (int X = 0; X <= WillReturn.GetUpperBound(0); X++) {
            for (int Y = 0; Y <= WillReturn.GetUpperBound(1); Y++) {
                WillReturn[X, Y] = pBanArr[Y, WillReturn.GetUpperBound(0) - X];
            }
        }
        return WillReturn;
    }

    ////////////////////////////////////////////////////////////////
    // IEnumerable<string>をintの2次元配列に設定する
    ////////////////////////////////////////////////////////////////
    static int[,] CreateBanArr(IEnumerable<string> pStrEnum)
    {
        var StrList = pStrEnum.ToList();
        if (StrList.Count == 0) {
            return new int[0, 0];
        }

        int[] IntArr = { };
        Action<string> SplitAct = pStr =>
            IntArr = pStr.Split(' ').Select(pX => int.Parse(pX)).ToArray();

        SplitAct(StrList[0]);

        int UB_X = IntArr.GetUpperBound(0);
        int UB_Y = StrList.Count - 1;

        int[,] WillReturn = new int[UB_X + 1, UB_Y + 1];

        for (int Y = 0; Y <= UB_Y; Y++) {
            SplitAct(StrList[Y]);
            for (int X = 0; X <= UB_X; X++) {
                WillReturn[X, Y] = IntArr[X];
            }
        }
        return WillReturn;
    }
}

解説

考察すると
行の入れ替えを行ってから
列の入れ替えを行うと考えても解は変わないと分かります。

なので、行ごとに入れ替え可能なグループごとの
要素数を無向グラフを作ってから、連結成分分解を行います。

そして、
連結成分ごとの要素数の階乗の、総積から、解を求めることができます。

2次元配列を90度回転するメソッドを使い、
実装量を減らす工夫もしてます。