?
求出区间[A,B]内能被K整除且各位数字之和也能被K整除的数的个数。（1 ≤ A ≤ B < 231 and 0 < K < 10000）
算是最简单的数位dp了，k在这里是10000，三维数组都开不开。但是想想会发现A,B最多有10位，各位数字之和不会超过90，那么当 k >= 90时，就不用dp，因为个位数字之和对k取余不会等于0。所以数组只需开到dp[12][90][90]。
#include #include #include #include #include #include #include #include #include #include #include #include #include #define LL __int64 #define eps 1e-12 #define PI acos(-1.0) using namespace std; const int INF = 0x3f3f3f3f; const int maxn = 4010; int dp[15][92][92]; int a,b,k; int dig[15]; int dfs(int len, int mod1, int mod2, int up) { if(len == 0) return mod1 == 0 && mod2 == 0; if(!up && dp[len][mod1][mod2] != -1) return dp[len][mod1][mod2]; int res = 0; int n = up ? dig[len] : 9; for(int i = 0; i <= n; i++) { int tmod1 = (mod1*10 + i)%k; int tmod2 = (mod2 + i)%k; res += dfs(len-1,tmod1,tmod2,up&&i==n); } if(!up) dp[len][mod1][mod2] = res; return res; } int cal(int num) { int len = 0; while(num) { dig[++len] = num%10; num /= 10; } return dfs(len,0,0,1); } int main() { int test; scanf(%d,&test); for(int item = 1; item <= test; item++) { scanf(%d %d %d,&a,&b,&k); if(k >= 90) { printf(Case %d: 0 ,item); continue; } memset(dp,-1,sizeof(dp)); printf(Case %d: %d ,item,cal(b) - cal(a-1)); } return 0; }