Submission #3622376

---

Source Code Expand

using System;
using System.Linq;//リストの使用
using System.Collections.Generic;
using System.Text;//テキストの高速出力に必要
class Program
{
	static void Main()
	{
		long d = long.Parse(Console.ReadLine());
    string n = Console.ReadLine();
    long digit = n.Length;
    long mod = 1000000007;
    long answer = 0;
    long[,,] dp = new long[digit+1,d,2];//dp[見た桁数、余り、最上位未満で1]=何通りか
    dp[0,0,0] = 1;


    for(int i = 1; i <= digit; i++)
    {
      for(int j = 0; j < d; j++)//余り
      {
        for(int k = 0; k <= 9; k++)
        {
          dp[i,j,0] = dp[i-1,(j-(n[i-1]-'0')+d*100)%d,0];
          dp[i,j,1] += dp[i-1,(j-k+d*100)%d,1];
          if(n[i-1]-'0' > k) dp[i,j,1] += dp[i-1,(j-k+d*100)%d,0];
          dp[i,j,1] %= mod;
        }
      }
    } 

		Console.WriteLine(dp[digit,0,1]+dp[digit,0,0]-1);//WriteLineをWriteとすると、改行なしで出力。
	}
}

Submission Info

Judge Result