ABC135-D Digits Parade

問題へのリンク

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??5");
            //768
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("?44");
            //1
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("7?4");
            //0
        }
        else if (InputPattern == "Input4") {
            WillReturn.Add("?6?42???8??2??06243????9??3???7258??5??7???????774????4?1??17???9?5?70???76???");
            //153716888
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    const long Hou = 1000000007;

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

        // 場合の数 [ mod 13 ] なDP表
        long[] PrevDP = new long[13];
        PrevDP[0] = 1;

        long Base = 1;
        for (int I = S.Length - 1; 0 <= I; I--) {
            long[] CurrDP = new long[13];

            for (long J = 0; J <= 12; J++) {
                if (PrevDP[J] == 0) continue;
                for (long K = 0; K <= 9; K++) {
                    if (S[I] != '?') {
                        if (S[I] - '0' != K) continue;
                    }
                    long NewInd = J + Base * K;
                    NewInd %= 13;

                    CurrDP[NewInd] += PrevDP[J];
                    CurrDP[NewInd] %= Hou;
                }
            }
            Base *= 10;
            Base %= 13;

            PrevDP = CurrDP;
        }
        Console.WriteLine(PrevDP[5]);
    }
}

解説

動的計画法で解いてます。