Submission #5402395

---

Source Code Expand

using System;
using System.Collections.Generic;
using System.Linq;
using BitArray = System.Collections.BitArray;
using BigInteger = System.Numerics.BigInteger;

namespace AtCoderProject
{
    public class Program
    {
        public object Calc()
        {
            var D = consoleReader.Int();
            var N = consoleReader.String();
            var bara = N.Reverse().Select(c => c - '0').ToArray();

            var dp = new long[bara.Length + 1, D, 2]; // 最後のはそこまでで出た数を超えてるかどうかを表す
            dp[0, 0, 0] = 1;

            for (int i = 0; i < bara.Length; i++)
            {
                var num = bara[i];
                for (int j = 0; j < D; j++)
                {
                    for (int k = 0; k < 10; k++)
                    {
                        var next = (j + k) % D;
                        if (k < num)
                        {
                            dp[i + 1, next, 0] += dp[i, j, 0] + dp[i, j, 1];
                        }
                        else if (num == k)
                        {
                            dp[i + 1, next, 0] += dp[i, j, 0];
                            dp[i + 1, next, 1] += dp[i, j, 1];
                        }
                        else
                        {
                            dp[i + 1, next, 1] += dp[i, j, 0] + dp[i, j, 1];
                        }


                        dp[i + 1, next, 0] %= mod;
                        dp[i + 1, next, 1] %= mod;
                    }
                }
            }

            return dp[N.Length, 0, 0] - 1;
        }

        public const int mod = 1000000007;
        #region いつもの
        private readonly ConsoleReader consoleReader;
        public Program() : this(new ConsoleReader()) { }
        public Program(ConsoleReader consoleReader) { this.consoleReader = consoleReader; }
        static void Main() => Console.WriteLine(new Program().Calc());
        public static string MultiLine<T>(IEnumerable<T> source) => string.Join("\n", source);
        #endregion
    }

    #region Console
    public class ConsoleReader { public virtual string String() => Console.ReadLine(); public int Int() => int.Parse(String()); public long Long() => long.Parse(String()); public ulong ULong() => ulong.Parse(String()); public double Double() => double.Parse(String()); public string[] Split() => String().Split().ToArray(); public int[] SplitInt() => String().Split().Select(int.Parse).ToArray(); public long[] SplitLong() => String().Split().Select(long.Parse).ToArray(); public ulong[] SplitULong() => String().Split().Select(ulong.Parse).ToArray(); public double[] SplitDouble() => String().Split().Select(double.Parse).ToArray(); public IEnumerable<string> Repeat(int count) { for (int i = 0; i < count; i++) yield return String(); } public IEnumerable<int> RepeatInt(int count) { for (int i = 0; i < count; i++) yield return Int(); } public IEnumerable<long> RepeatLong(int count) { for (int i = 0; i < count; i++) yield return Long(); } public IEnumerable<string[]> RepeatSplit(int count) { for (int i = 0; i < count; i++) yield return Split(); } public IEnumerable<int[]> RepeatSplitInt(int count) { for (int i = 0; i < count; i++) yield return SplitInt(); } }
    #endregion
}

Submission Info

Judge Result