1 #include <algorithm> 2 #include <iostream> 3 #include <cstring> 4 #include <cstdlib> 5 #include <cstdio> 6 #include <vector> 7 #include <ctime> 8 #include <queue> 9 #include <list>10 #include <set>11 #include <map>12 using namespace std;13 #define INF 0x3f3f3f3f14 typedef long long LL;15 16 LL dp[12][12];17 int bit[12];18 LL dfs(int len, int zer, int sum, int flag)19 {20     if(len < 1){21         if(zer == 0)22             return 1;23         return sum;24     }25     if(dp[len][sum] != -1 && flag && zer)//注意zer26         return dp[len][sum];27     int te = flag ? 9 : bit[len];28     LL res = 0;29     for(int i = 0; i <= te; i++)30     {31         int Sum = sum, Zer = zer;32         if(zer == 0 && i != 0)33             Zer = 1;34         if(i == 0 && zer == 1)35             Sum++;36         res += dfs(len-1, Zer, Sum, flag || i < te);37     }38     if(flag && zer)//注意zer,一定要写39         dp[len][sum] = res;40     return res;41 }42 LL solve(LL n)43 {44     int len = 0;45     memset(bit, 0, sizeof(bit));46     while(n)47     {48         bit[++len] = n % 10;49         n /= 10;50     }51     return dfs(len, 0, 0, 0);52 }53 int main()54 {55     int t;56     LL l, r;57     memset(dp, -1, sizeof(dp));58     scanf("%d", &t);59     for(int ca = 1; ca <= t; ca++)60     {61         scanf("%lld %lld", &l, &r);62         printf("Case %d: %lld\n", ca, solve(r)-solve(l-1));63     }64     return 0;65 }