ABC465-E Digit Circus

問題へのリンク

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("45");
            //19
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("1013");
            //424
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("2");
            //0
        }
        else if (InputPattern == "Input4") {
            WillReturn.Add("314159265358979323846264338327950");
            //658111391
        }
        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();
        string StrN = InputList[0].ToString();

        // 対応する2べき数[0から9]
        var Beki2Dict = new Dictionary<long, long>();
        long CurrBeki2 = 1;
        for (long I = 0; I <= 9; I++) {
            Beki2Dict[I] = CurrBeki2;
            CurrBeki2 *= 2;
        }

        long AllBitOn = (1 << 10) - 1;

        // 場合の数[数字自由フラグ , 0以外登場有無 , mod 3 ,  登場数字のBitSet]なDP表
        long[, , ,] PrevDP = new long[2, 2, 3, AllBitOn + 1];
        PrevDP[0, 0, 0, 0] = 1;

        for (int I = 0; I <= StrN.Length - 1; I++) {
            long[, , ,] CurrDP = new long[2, 2, 3, AllBitOn + 1];
            for (long J = 0; J <= PrevDP.GetUpperBound(0); J++) {
                for (long K = 0; K <= PrevDP.GetUpperBound(1); K++) {
                    for (long L = 0; L <= PrevDP.GetUpperBound(2); L++) {
                        for (long M = 0; M <= PrevDP.GetUpperBound(3); M++) {
                            if (PrevDP[J, K, L, M] == 0) continue;

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

                                long NewJ = J;
                                if (StrN[I] > NewChar) NewJ = 1;

                                long NewK = K;
                                if (NewChar != '0' && K == 0) {
                                    NewK = 1;
                                }

                                long NewL = L;
                                NewL += NewChar - '0';
                                NewL %= 3;

                                long NewM = M;
                                if (NewChar != '0' || K == 1) {
                                    long BitOR = Beki2Dict[NewChar - '0'];
                                    NewM |= BitOR;
                                }

                                CurrDP[NewJ, NewK, NewL, NewM] += PrevDP[J, K, L, M];
                                CurrDP[NewJ, NewK, NewL, NewM] %= Hou;
                            }
                        }
                    }
                }
            }
            PrevDP = CurrDP;
        }

        long Answer = 0;
        for (long J = 0; J <= PrevDP.GetUpperBound(0); J++) {
            for (long K = 0; K <= PrevDP.GetUpperBound(1); K++) {
                for (long L = 0; L <= PrevDP.GetUpperBound(2); L++) {
                    for (long M = 0; M <= PrevDP.GetUpperBound(3); M++) {
                        bool OK1 = L == 0;

                        long Bit3 = Beki2Dict[3];
                        bool OK2 = (M & Bit3) > 0;

                        bool OK3 = PopCount(M) == 3;

                        if (OK1 && OK2 == false && OK3 == false) {
                            Answer += PrevDP[J, K, L, M]; Answer %= Hou;
                        }
                        if (OK1 == false && OK2 && OK3 == false) {
                            Answer += PrevDP[J, K, L, M]; Answer %= Hou;
                        }
                        if (OK1 == false && OK2 == false && OK3) {
                            Answer += PrevDP[J, K, L, M]; Answer %= Hou;
                        }
                    }
                }
            }
        }
        // 0の分を引く
        Console.WriteLine(Answer - 1);
    }

    ////////////////////////////////////////////////////////////////
    // C++のPopCount
    ////////////////////////////////////////////////////////////////
    static long PopCount(long pVal)
    {
        long WillReturn = 0;
        while (pVal > 0) {
            if (pVal % 2 == 1) WillReturn++;
            pVal /= 2;
        }
        return WillReturn;
    }
}

解説

桁DPで解いてます。