ABC470-F Googol Swaps

問題へのリンク

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 3");
            WillReturn.Add("miria");
            WillReturn.Add("1 3");
            WillReturn.Add("2 5");
            WillReturn.Add("4 5");
            //6
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("6 6");
            WillReturn.Add("yiwayi");
            WillReturn.Add("1 2");
            WillReturn.Add("1 3");
            WillReturn.Add("2 3");
            WillReturn.Add("4 5");
            WillReturn.Add("4 6");
            WillReturn.Add("5 6");
            //18
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("29 25");
            WillReturn.Add("hexakosioihexekontahexaphobia");
            WillReturn.Add("1 2");
            WillReturn.Add("1 4");
            WillReturn.Add("1 6");
            WillReturn.Add("1 8");
            WillReturn.Add("1 15");
            WillReturn.Add("1 16");
            WillReturn.Add("2 3");
            WillReturn.Add("3 4");
            WillReturn.Add("4 20");
            WillReturn.Add("5 6");
            WillReturn.Add("5 8");
            WillReturn.Add("8 22");
            WillReturn.Add("8 23");
            WillReturn.Add("9 15");
            WillReturn.Add("9 17");
            WillReturn.Add("11 21");
            WillReturn.Add("12 20");
            WillReturn.Add("13 19");
            WillReturn.Add("14 29");
            WillReturn.Add("15 28");
            WillReturn.Add("16 17");
            WillReturn.Add("18 19");
            WillReturn.Add("18 21");
            WillReturn.Add("19 20");
            WillReturn.Add("20 21");
            //346192062
        }
        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();

        char[] CharArr = InputList[1].ToCharArray();

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

        SplitAct(InputList[0]);
        long N = wkArr[0];

        var InsUnionFind = new UnionFind();
        for (long I = 1; I <= CharArr.GetUpperBound(0) + 1; I++) {
            InsUnionFind.MakeSet(I);
        }

        foreach (string EachStr in InputList.Skip(2)) {
            SplitAct(EachStr);
            long From = wkArr[0];
            long To = wkArr[1];
            InsUnionFind.Unite(From, To);
        }

        // 文字のList[ルート]なDict
        var CharListDict = new Dictionary<long, List<char>>();

        for (long I = 1; I <= CharArr.GetUpperBound(0) + 1; I++) {
            long Root = InsUnionFind.FindSet(I);
            if (CharListDict.ContainsKey(Root) == false) {
                CharListDict[Root] = new List<char>();
            }
            CharListDict[Root].Add(CharArr[I - 1]);
        }

        // 重複文字があるかを調べる
        bool HasDuplicate = false;
        foreach (var EachList in CharListDict.Values) {
            if (EachList.Count() != EachList.Distinct().Count()) {
                HasDuplicate = true;
            }
        }

        long Answer = 1;

        var InsChooseMod = new ChooseMod(N, Hou);

        foreach (var EachPair in CharListDict) {
            var CntDict = new Dictionary<char, long>();
            foreach (char EachChar in EachPair.Value) {
                if (CntDict.ContainsKey(EachChar) == false) {
                    CntDict[EachChar] = 0;
                }
                CntDict[EachChar]++;
            }
            long TotalCnt = CntDict.Values.Sum();

            long CurrAnswer = 1;
            foreach (long EachCnt in CntDict.Values) {
                CurrAnswer *= InsChooseMod.DeriveChoose(TotalCnt, EachCnt);
                TotalCnt -= EachCnt;
                CurrAnswer %= Hou;
            }
            Answer *= CurrAnswer;
            Answer %= Hou;
        }
        if (HasDuplicate == false) {
            Answer *= DeriveGyakugen(2);
            Answer %= Hou;
        }

        Console.WriteLine(Answer);
    }

    // 引数の逆元を求める
    static Dictionary<long, long> mMemoGyakugen = new Dictionary<long, long>();
    static long DeriveGyakugen(long pLong)
    {
        if (mMemoGyakugen.ContainsKey(pLong)) {
            return mMemoGyakugen[pLong];
        }
        return mMemoGyakugen[pLong] = 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 UnionFind
// UnionFindクラス
internal class UnionFind
{
    private class NodeInfoDef
    {
        internal long ParentNode;
        internal long Rank;
    }
    private Dictionary<long, NodeInfoDef> mNodeInfoDict =
        new Dictionary<long, NodeInfoDef>();

    // 要素が1つである木を森に追加
    internal void MakeSet(long pNode)
    {
        NodeInfoDef WillAdd = new NodeInfoDef();
        WillAdd.ParentNode = pNode;
        WillAdd.Rank = 0;
        mNodeInfoDict[pNode] = WillAdd;
    }

    // 合併処理
    internal void Unite(long pX, long pY)
    {
        long XNode = FindSet(pX);
        long YNode = FindSet(pY);
        long XRank = mNodeInfoDict[XNode].Rank;
        long YRank = mNodeInfoDict[YNode].Rank;

        if (XRank > YRank) {
            mNodeInfoDict[YNode].ParentNode = XNode;
        }
        else {
            mNodeInfoDict[XNode].ParentNode = YNode;
            if (XRank == YRank) {
                mNodeInfoDict[YNode].Rank++;
            }
        }
    }

    // ノードを引数として、木の根を取得
    internal long FindSet(long pTargetNode)
    {
        // 根までの経路上のノードのList
        var PathNodeList = new List<long>();

        long CurrNode = pTargetNode;
        while (CurrNode != mNodeInfoDict[CurrNode].ParentNode) {
            PathNodeList.Add(CurrNode);
            CurrNode = mNodeInfoDict[CurrNode].ParentNode;
        }

        // 経路圧縮 (親ポインタの付け替え)
        foreach (long EachPathNode in PathNodeList) {
            mNodeInfoDict[EachPathNode].ParentNode = CurrNode;
        }
        return CurrNode;
    }

    internal void DebugPrint()
    {
        foreach (var EachPair in mNodeInfoDict.OrderBy(pX => pX.Key)) {
            Console.WriteLine("mNodeInfoDict[{0}].ParentNode={1}",
                EachPair.Key, EachPair.Value.ParentNode);
        }
    }
}
#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

解説

入れ替え可能なノード同士を辺でつなぎ
無向グラフとして、考えます。

実装としては、
UnionFindで辺ごとに連結し、
ルートノードごとに
文字のList[ルート]を求め、
chooseを使って、文字を配置し、何通りの配置ができるかを求めます。

10の100乗は、偶数で、
偶数回の置換を行うので、
偶置換と奇置換をふまえ、

どれかの連結成分に、重複文字があるかを調べ
重複文字が無ければ、解を2で割ってます。