UVA 11361

Question link: 11361 - Investigating Div-Sum Property

There is an example question in the white book, but there is no code. I just wrote a digital DP question a few days ago, so this question is relatively Relaxed.

dp[i][x][y] means adding to the i-th digit, the number % k, the number of combinations of digits and % k, then now we need to add a number from 0 to 9 and the state transition is

dp[i 1][(x * 10 num) % k][(y num) % k]. After calculating the sum, since the number itself cannot exceed the maximum value, the exact preceding number must be added at the end. The situation where several of them are the maximum value. Then finally judge whether the number itself meets the conditions. Note that the answer is 1 when the boundary is 0.

Code:

#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;}