square869120コンテスト2 C問題 何通りの分割方法がある？

問題へのリンク

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("1355");
            WillReturn.Add("50");
            //3
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("2439");
            WillReturn.Add("100");
            //5
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("1225");
            WillReturn.Add("20");
            //2
        }
        else if (InputPattern == "Input4") {
            WillReturn.Add("123456");
            WillReturn.Add("10000");
            //29
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    const int Hou = 1000000007;
    static int mD;

    static void Main()
    {
        List<string> InputList = GetInputList();
        string StrN = InputList[0];
        mD = int.Parse(InputList[1]);

        int LastNum = StrN.ToCharArray().Last() - '0';
        if (LastNum > mD) {
            Console.WriteLine(0);
            return;
        }

        // 場合の数[和 , 10の指数] なDP表
        int[,] PrevDP = new int[mD + 1, StrN.Length + 1];
        PrevDP[LastNum, 0] = 1;

        for (int I = StrN.Length - 2; 0 <= I; I--) {
            int[,] CurrDP = new int[mD + 1, StrN.Length + 1];
            for (int J = 0; J <= mD; J++) {
                for (int K = 0; K <= StrN.Length; K++) {
                    if (PrevDP[J, K] == 0) continue;

                    int CurrVal = StrN[I] - '0';

                    // 貰うDP
                    Action<int, int> UpdateAct = (pNewJ, pNewK) =>
                    {
                        if (pNewJ > mD) return;
                        CurrDP[pNewJ, pNewK] += PrevDP[J, K];
                        CurrDP[pNewJ, pNewK] %= Hou;
                    };

                    // 分割する場合
                    UpdateAct(J + CurrVal, 0);

                    // 分割しない場合
                    bool IsOver;
                    int Beki10;
                    Derive10Beki(K + 1, out IsOver, out Beki10);
                    if (IsOver == false || IsOver && CurrVal == 0) {
                        UpdateAct(J + CurrVal * Beki10, K + 1);
                    }
                }
            }
            PrevDP = CurrDP;
            System.GC.Collect(); // MLE対策
        }

        int Answer = 0;
        for (int J = 0; J <= mD; J++) {
            for (int K = 0; K <= StrN.Length; K++) {
                Answer += PrevDP[J, K];
                Answer %= Hou;
            }
        }
        Console.WriteLine(Answer);
    }

    // 10の指数と、Dを超えたかのbool値を設定
    static void Derive10Beki(int pP, out bool pIsOver, out  int pBeki10)
    {
        pIsOver = false;
        pBeki10 = 1;
        for (int I = 1; I <= pP; I++) {
            pBeki10 *= 10;
            if (mD < pBeki10) {
                pIsOver = true;
                return;
            }
        }
    }
}

解説

場合の数[和 , 10の指数] なDP表を貰うDPで更新してます。
MLE対策でSystem.GC.Collectも使ってます。