UVA 11361

题目链接：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 #include 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  100) printf("0\n");else printf("%d\n", solve(b) - solve(a - 1));}return 0;}

登录后复制