UVA11361

質問リンク: 11361 - Investigating Div-Sum Property

ホワイトブックには質問例がありますが、コードはありません。数日前にデジタル DP の質問を書いたばかりなので、この質問は比較的簡単です。

dp[i][x][y] は、i 番目の桁、数値 % k、桁の組み合わせの数、% k を加算することを意味します。次に、0 から 9 までの数値を加算する必要があります。状態遷移は

dp[i + 1][(x * 10 + num) % k][(y + num) % k] となります。和を計算した後、数値自体は最大値を超えることができないため、最初の数桁はすべて最大値であることを付け加えます。そして最後に数字自体が条件を満たしているかどうかを判断します。 境界が 0 の場合、答えは 1 になることに注意してください。

コード:

#include <stdio.h>#include <string.h>int t, a, b, k, f[15][105][105], n, d[15];void tra(int num) {	n = 0;	while (num) {		d[++n] = num % 10;		num /= 10;	}	for (int i = 1; i <= n / 2; i++) {		int t = d[i];		d[i] = d[n + 1 - i];		d[n + 1 - i] = t;	}}int solve(int num) {	if (num == 0) return 1;	tra(num);	memset(f, 0, sizeof(f));	int x1 = 0, x2 = 0;	for (int i = 1; i <= n; i++) {		for (int x = 0; x < k; x++) {			for (int y = 0; y < k; y++) {				for (int j = 0; j <= 9; j++) {					f[i][(x * 10 + j) % k][(y + j) % k] += f[i - 1][x][y];				}			}		}		for (int j = 0; j < d[i]; j++)			f[i][(x1 * 10 + j) % k][(x2 + j) % k]++;		x1 = (x1 * 10 + d[i]) % k;		x2 = (x2 + d[i]) % k;	}	if (x1 == 0 && x2 == 0)		f[n][0][0]++;	return f[n][0][0];}int main() {	scanf("%d", &t);	while (t--) {		scanf("%d%d%d", &a, &b, &k);		if (k > 100) printf("0\n");		else printf("%d\n", solve(b) - solve(a - 1));	}	return 0;}