本文主要是介绍UVa 11361 Investigating Div-Sum Property / 数位DP，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
先上代码 以后再说
#include <cstdio>
#include <cstring>
const int maxn = 110;
int dp[maxn][maxn][maxn];
int ok(int x, int k)
{if(x < 10)return x / k;int a = x;int b = 1;int l = 0;while(a){l++;a /= 10;b *= 10;}b /= 10;//printf("%d %d\n", a, b);int ret = 0;int m1 = 0, m2 = 0;int d = 1;while(l--){int c = x / b;//printf("%d\n", c);if(l == 0){for(int j = 0; j <= c; j++)if(((k-j-m1)%k+k)%k == 0 && ((k-j-m2)%k+k)%k == 0)ret++;break;}for(int j = 0; j < c; j++)ret += dp[l-1][((k-j-m1)%k+k)%k][((k-j*b-m2)%k+k)%k];// printf("%d\n", c);m1 += c;m2 += c*b;x -= c*b;b /= 10;}return ret-1;
}
int main()
{int T;int a, b, k;scanf("%d", &T);while(T--){scanf("%d %d %d", &a, &b, &k);if(k > 82){printf("0\n");continue;}int c = a, d = 1;memset(dp, 0, sizeof(dp));for(int i = 0; i < 10; i++)dp[0][i%k][i%k]++;for(int i = 1; i <= 10; i++){d *= 10;if(d * 10 > b){//printf("%d\n", d);break;}for(int m1 = 0; m1 < k; m1++){for(int m2 = 0; m2 < k; m2++){for(int j = 0; j < 10; j++){dp[i][((m1+j)%k+k)%k][((m2+j*d)%k+k)%k] += dp[i-1][m1][m2];}}}} printf("%d\n", ok(b,k)-ok(a-1,k));}return 0;
}
这篇关于UVa 11361 Investigating Div-Sum Property / 数位DP的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
