题目描述

tabris有一个习惯，无聊的时候就会数圈圈，无论数字还是字母。

现在tabris更无聊啦，晚上睡不着觉就开始数羊，从a只数到b只。

顺便还数了a到b之间有多少个圈。

 

但是tabris笨啊，虽然数羊不会数错，但很可能数错圈的个数。

但是tabris很难接受自己笨这个事实，所以想问问你他一共应该数出多少个圈，这样tabris才好判断他到底笨不笨啊。 

输入描述:

输入一个T，表示数据组数

每组测试数据包含两个正整数a，b。

T∈[1,1000]

a,b∈[1,1014]

输出描述:

每组数据输出结果，并换行。

示例1

输入

111 12 23 34 45 56 67 78 89 910 101 100

输出

0001010211111

备注:

数字的圈的个数请根据样例自行理解。

题解

数位$dp$。

$dp[i][j]$表示数字长度有$i$位，且第$i$位为$j$的总和，统计一下就可以了。

#include 
      
       using namespace std;long long dp[16][10];long long b[20], a[20];long long c[20], sz;/*0 11 02 03 04 15 06 17 08 29 1*/void init() {  memset(a, 0, sizeof a);  a[0] = 1;  a[4] = 1;  a[6] = 1;  a[8] = 2;  a[9] = 1;  b[0] = 1;  for(int i = 1; i <= 15; i ++) {    b[i] = b[i - 1] * 10LL;  }  for(int i = 0; i <= 9; i ++) {    dp[1][i] = a[i];  }  for(int i = 2; i <= 15; i ++) {    for(int j = 0; j <= 9; j ++) {      dp[i][j] = a[j] * b[i - 1];      for(int k = 0; k <= 9; k ++) {        dp[i][j] = dp[i][j] + dp[i - 1][k];      }    }  }}long long get(long long x) {  if(x == 0) return 0;  long long ans = 0;  sz = 0;  while(x) {    sz ++;    c[sz] = x % 10;    x = x / 10;  }  for(int i = 1; i <= sz - 1; i ++) {    for(int j = 1; j <= 9; j ++) {      ans = ans + dp[i][j];    }  }  for(int j = 1; j < c[sz]; j ++) {    ans = ans + dp[sz][j];  }  long long sum = a[c[sz]];  for(int i = sz - 1; i >= 1; i --) {    for(int j = 0; j < c[i]; j ++) {      ans = ans + dp[i][j];      ans = ans + sum * b[i - 1];    }    sum = sum + a[c[i]];  }  return ans;}int main() {  init();  int T;  scanf("%d", &T);  while(T --) {    long long L, R;    scanf("%lld%lld", &L, &R);    printf("%lld\n", get(R + 1) - get(L));  }  return 0;}