ABC246-F typewriter

問題へのリンク

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("2 2");
            WillReturn.Add("ab");
            WillReturn.Add("ac");
            //7
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("4 3");
            WillReturn.Add("abcdefg");
            WillReturn.Add("hijklmnop");
            WillReturn.Add("qrstuv");
            WillReturn.Add("wxyz");
            //1352
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("5 1000000000");
            WillReturn.Add("abc");
            WillReturn.Add("acde");
            WillReturn.Add("cefg");
            WillReturn.Add("abcfh");
            WillReturn.Add("dghi");
            //346462871
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    const long Hou = 998244353;

    static List<char[]> mSList = new List<char[]>();

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

        foreach (string EachStr in InputList.Skip(1)) {
            mSList.Add(EachStr.ToCharArray());
        }

        long Answer = 0;
        foreach (JyoutaiDef EachResut in ExecDFS()) {
            long CurrPatternCnt = DeriveBekijyou(EachResut.AppearCharSet.Count, L, Hou);
            if (EachResut.SelectedCnt % 2 == 1) {
                Answer += CurrPatternCnt;
                Answer %= Hou;
            }
            else {
                Answer -= CurrPatternCnt;
                if (Answer < 0) {
                    Answer += Hou;
                }
            }
        }
        Console.WriteLine(Answer);
    }

    struct JyoutaiDef
    {
        internal int CurrInd;
        internal int SelectedCnt;
        internal HashSet<char> AppearCharSet;
    }

    static IEnumerable<JyoutaiDef> ExecDFS()
    {
        var Stk = new Stack<JyoutaiDef>();
        JyoutaiDef WillPush;
        WillPush.CurrInd = 0;
        WillPush.SelectedCnt = 0;
        WillPush.AppearCharSet = new HashSet<char>();
        mSList.ForEach(pX => WillPush.AppearCharSet.UnionWith(pX));
        Stk.Push(WillPush);

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

            if (Popped.SelectedCnt > 0) {
                yield return Popped;
            }

            for (int I = Popped.CurrInd; I <= mSList.Count - 1; I++) {
                WillPush.CurrInd = I + 1;
                WillPush.SelectedCnt = Popped.SelectedCnt + 1;
                WillPush.AppearCharSet = new HashSet<char>(Popped.AppearCharSet);
                WillPush.AppearCharSet.IntersectWith(mSList[I]);
                Stk.Push(WillPush);
            }
        }
    }

    // 繰り返し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;
        }
    }
}

解説

3段で考えると

1段目の文字列で作成できる文字列 と
2段目の文字列で作成できる文字列 と
3段目の文字列で作成できる文字列 の和集合の個数が解になります。

これは、包除原理を使って、
1段目の文字列で作成できる文字列 + 2段目の文字列で作成できる文字列 + 3段目の文字列で作成できる文字列 
- (1段目かつ2段目の文字列で作成できる文字列)
- (2段目かつ3段目の文字列で作成できる文字列)
- (3段目かつ1段目の文字列で作成できる文字列)
+ (1段目かつ2段目かつ3段目の文字列で作成できる文字列)

で求まります。