https://cn.vjudge.net/problem/HDU-4722
懒得写看，代码注释吧;主要存板子
1 #include <cstdio> 2 #include <cstring> 3 #include <cctype> 4 #include <cmath> 5 #include <set> 6 #include <map> 7 #include <list> 8 #include <queue> 9 #include <deque> 10 #include <stack> 11 #include <string> 12 #include <vector> 13 #include <iostream> 14 #include <algorithm> 15 #include <stdlib.h> 16 #include <time.h> 17 using namespace std; 18 typedef long long LL; 19 const int INF=2e9+1e8; 20 21 const int MOD=1e9+7; 22 const int MAXSIZE=1e6+5; 23 const double eps=0.0000000001; 24 void fre() 25 { 26 freopen("in.txt","r",stdin); 27 freopen("out.txt","w",stdout); 28 } 29 #define memst(a,b) memset(a,b,sizeof(a)) 30 #define fr(i,a,n) for(int i=a;i<n;i++) 31 32 /** 33 dp[i][j] 代表从高位到i位求和余数为j的;先写dfs，最后再把dp加入就好了， 34 还有爆int 需要注意。 35 36 */ 37 38 LL dp[111][20]; 39 int bits[100]; 40 LL dfs(int pos,int sum,bool flag)//pos代表位置，sum代表求和之后的余数，flag代表是否是0～9 41 { 42 if(pos==0) return sum==0; 43 if(flag&&dp[pos][sum]!=-1) return dp[pos][sum]; 44 int len=flag?9:bits[pos];//flag为真 0～9， 45 LL res=0; 46 for(int i=0;i<=len;i++) 47 res+=dfs(pos-1,(sum+i)%10,i!=len||flag);// 48 if(flag) dp[pos][sum]=res; 49 return res; 50 } 51 52 53 LL get(LL x) 54 { 55 if(x<0) return 0; 56 int i=0; 57 while(x>0) bits[++i]=x%10,x/=10; 58 return dfs(i,0,false); 59 } 60 int main() 61 { 62 // test(); 63 int cas=0,ncase; 64 scanf("%d",&ncase); 65 memset(dp,-1,sizeof(dp)); 66 while(ncase--) 67 { 68 int i=0; 69 LL l,r; 70 cin>>l>>r; 71 printf("Case #%d: %I64d ",++cas,get(r)-get(l-1)); 72 } 73 return 0; 74 } 75 76 /**************************************************/ 77 /** Copyright Notice **/ 78 /** writer: wurong **/ 79 /** school: nyist **/ 80 /** blog : http://blog.csdn.net/wr_technology **/ 81 /**************************************************/