ABC336-E Digit Sum Divisible

問題へのリンク

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("20");
            //13
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("2024");
            //409
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("9876543210");
            //547452239
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static string mStrN;

    static void Main()
    {
        List<string> InputList = GetInputList();
        mStrN = InputList[0];

        long Answer = 0;
        long KetawaMax = mStrN.Length * 9;
        for (long I = 1; I <= KetawaMax; I++) {
            long Result = ExecDP(I);
            Answer += Result;
        }
        Console.WriteLine(Answer);
    }

    // 桁和を引数として、DP結果を返す
    static long ExecDP(long pKetawa)
    {
        long[] Base10Arr = new long[mStrN.Length];
        long Base10 = 1;
        for (long I = mStrN.Length - 1; 0 <= I; I--) {
            Base10Arr[I] = Base10;
            Base10 *= 10;
            Base10 %= pKetawa;
        }

        // 場合の数[桁和,桁和を法とした余り,数字自由フラグ]なDP表
        long[, ,] PrevDP = new long[pKetawa + 1, pKetawa, 2];
        PrevDP[0, 0, 0] = 1;

        for (int I = 0; I <= mStrN.Length - 1; I++) {
            long[, ,] CurrDP = new long[pKetawa + 1, pKetawa, 2];

            for (long J = 0; J <= PrevDP.GetUpperBound(0); J++) {
                for (long K = 0; K <= PrevDP.GetUpperBound(1); K++) {
                    for (long L = 0; L <= 1; L++) {
                        if (PrevDP[J, K, L] == 0) continue;

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

                            long NewJ = (J + NewChar - '0');
                            if (NewJ > pKetawa) break;

                            long Base10Val = Base10Arr[I];
                            long NewK = (K + (NewChar - '0') * Base10Val) % pKetawa;

                            long NewL = L;
                            if (mStrN[I] > NewChar) NewL = 1;

                            CurrDP[NewJ, NewK, NewL] += PrevDP[J, K, L];
                        }
                    }
                }
            }
            PrevDP = CurrDP;
        }
        long PatternCnt = 0;
        PatternCnt += PrevDP[pKetawa, 0, 0];
        PatternCnt += PrevDP[pKetawa, 0, 1];

        return PatternCnt;
    }
}

解説

桁和を全探索しつつ、桁DPしてます。