ABC235-F Variety of Digits

問題へのリンク

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("104");
            WillReturn.Add("2");
            WillReturn.Add("0 1");
            //520
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("999");
            WillReturn.Add("4");
            WillReturn.Add("1 2 3 4");
            //0
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("1234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890");
            WillReturn.Add("5");
            WillReturn.Add("0 2 4 6 8");
            //397365274
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    const int Hou = 998244353;

    static string mStrN;
    static int[] mCArr;

    static int AllBitOn;

    static void Main()
    {
        List<string> InputList = GetInputList();
        mStrN = InputList[0];
        mCArr = InputList[2].Split(' ').Select(pX => int.Parse(pX)).ToArray();

        int Result = Solve();
        Console.WriteLine(Result);
    }

    static int Solve()
    {
        AllBitOn = (1 << 10) - 1;

        long[] Base10Arr = new long[mStrN.Length];
        long Base10 = 1;
        for (int I = mStrN.Length - 1; 0 <= I; I--) {
            Base10Arr[I] = Base10;
            Base10 *= 10;
            Base10 %= Hou;
        }

        //int UB = 2 * (AllBitOn + 1);
        int UB = AllBitOn * 2 + 1;

        // 場合の数[数字自由フラグ , 使用した数字のBitSet] なDP表
        int[] PrevDP1 = new int[UB + 1];
        PrevDP1[0] = 1;

        // 合計[数字自由フラグ , 使用した数字のBitSet] なDP表
        int[] PrevDP2 = new int[UB + 1];
        PrevDP2[0] = 0;

        for (int I = 0; I <= mStrN.Length - 1; I++) {
            int[] CurrDP1 = new int[UB + 1];
            int[] CurrDP2 = new int[UB + 1];
            for (int L = 0; L <= UB; L++) {
                if (PrevDP1[L] == 0) continue;

                int J, K;
                GetVal(L, out J, out K);

                for (char NewChar = '0'; NewChar <= '9'; NewChar++) {
                    if (J == 0 && mStrN[I] < NewChar) break;

                    int NewJ = J;
                    if (mStrN[I] > NewChar) NewJ = 1;

                    int CurrNum = NewChar - '0';
                    int CurrBit = (1 << CurrNum);

                    int NewK = K | CurrBit;
                    if (K <= 1) { // 0以外の数字を使用してない場合
                        if (NewK % 2 == 1) NewK--;
                    }

                    int Hash = GetHash(NewJ, NewK);

                    CurrDP1[Hash] += PrevDP1[L];
                    CurrDP1[Hash] %= Hou;

                    long AddVal = Base10Arr[I] * CurrNum * PrevDP1[L];
                    AddVal %= Hou;
                    AddVal += PrevDP2[L];
                    AddVal %= Hou;

                    CurrDP2[Hash] += (int)AddVal;
                    CurrDP2[Hash] %= Hou;
                }
            }
            PrevDP1 = CurrDP1;
            PrevDP2 = CurrDP2;
        }

        int NeedBitSet = 0;
        foreach (int EachInt in mCArr) {
            int NeedBit = (1 << (EachInt));
            NeedBitSet |= NeedBit;
        }

        int Answer = 0;
        for (int L = 0; L <= UB; L++) {
            int J, K;
            GetVal(L, out J, out K);

            if ((NeedBitSet & K) == NeedBitSet) {
                Answer += PrevDP2[L];
                Answer %= Hou;
            }
        }
        return Answer;
    }

    static int GetHash(int pJ, int pK)
    {
        return pK * 2 + pJ;
    }

    static void GetVal(int pHash, out int pJ, out int pK)
    {
        pJ = pHash % 2;
        pK = pHash / 2;
    }
}

解説

桁DPで解いてます。

多次元配列をハッシュ値を使って、1次元配列にする。
Dictではなく、配列を使う。
という定数倍高速化も行ってます。