Typical DP Contest E: 数 (動的計画法)

問題

E: 数 - Typical DP Contest | AtCoder

解法

下からi桁目まで見た時にj余る整数の数を記録しておく。この時、i桁目がNのi桁目以下になる数も記録しておく。

コード

import java.util.Scanner;

public class Main {
	private static final long MOD = 1000000007;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int D = sc.nextInt();
		char[] input = sc.next().toCharArray();
		sc.close();

		int N = input.length;// 桁数
		int[] nums = new int[N];
		for (int i = 0; i < nums.length; i++) {
			nums[i] = Character.getNumericValue(input[i]);
		}

		// dp[i][j]:= i+1桁目まで見てj余る整数の数
		long[][] dp = new long[N + 1][D];
		long[][] dpLarger = new long[N + 1][D];// N桁の99999...の中のDの倍数を記録する
		dp[N][0] = 1;
		dpLarger[N][0] = 1;
		for (int n = N - 1; n >= 0; n--) {
			for (int d = 0; d < D; d++) {
				for (int j = 0; j <= 9; j++) {
					int rest = d - j;
					rest = (rest + 10 * D) % D;
					dpLarger[n][d] += dpLarger[n + 1][rest];
					dpLarger[n][d] %= MOD;
				}

				for (int j = 0; j < nums[n]; j++) {
					int rest = d - j;
					rest = (rest + 10 * D) % D;
					dp[n][d] += dpLarger[n + 1][rest];
					dp[n][d] %= MOD;
				}

				int rest = d - nums[n];
				rest = (rest + 10 * D) % D;
				dp[n][d] += dp[n + 1][rest];
				dp[n][d] %= MOD;
			}
		}
		// 000...を含まないようにする
		System.out.println(dp[0][0] - 1);
	}
}