首页 > 代码库 > uva 11361 - Investigating Div-Sum Property(数位dp)
uva 11361 - Investigating Div-Sum Property(数位dp)
题目链接:uva 11361 - Investigating Div-Sum Property
题目大意:给出a,b,k,问说在[a,b]这个区间有多少n,满足n整除k,以及n的各个为上的数字之和也整除k。
解题思路:数位dp,dp[i][j][x]表示第i为的时候,n整除k余j,n(以及考虑到的位数)的各个位置上的数字之和整除k余x的情况总数,并且每次要计算上限的临界值。
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 15;
const int M = 105;
int a, b, k, n, d[N];
int dp[N][M][M];
void cat(int u) {
n = 1;
memset(d, 0, sizeof(d));
while (u) {
d[n++] = u%10;
u /= 10;
}
for (int i = 1; i <= n/2; i++)
swap(d[i], d[n-i+1]);
}
int solve (int u) {
if (u == 0)
return 1;
cat(u);
memset(dp, 0, sizeof(dp));
int p = 0, q = 0;
for (int i = 1; i <= n; i++) {
for (int j = 0; j <= k; j++) {
for (int t = 0; t <= k; t++) {
for (int x = 0; x < 10; x++)
dp[i][(j*10+x)%k][(t+x)%k] += dp[i-1][j][t];
}
}
for (int j = 0; j < d[i]; j++)
dp[i][(p*10+j)%k][(q + j)%k]++;
p = (p*10+d[i])%k;
q = (q+d[i])%k;
}
if (p == 0 && q == 0)
dp[n][0][0]++;
return dp[n][0][0];
}
int main () {
int cas;
scanf("%d", &cas);
while (cas--) {
scanf("%d%d%d", &a, &b, &k);
if (k > 100)
printf("0\n");
else
printf("%d\n", solve(b) - solve(a-1));
}
return 0;
}
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。