题目描述
tabris有一个习惯，无聊的时候就会数圈圈，无论数字还是字母。
现在tabris更无聊啦，晚上睡不着觉就开始数羊，从a只数到b只。
顺便还数了a到b之间有多少个圈。
但是tabris笨啊，虽然数羊不会数错，但很可能数错圈的个数。
但是tabris很难接受自己笨这个事实，所以想问问你他一共应该数出多少个圈，这样tabris才好判断他到底笨不笨啊。
输入描述:
输入一个T，表示数据组数
每组测试数据包含两个正整数a，b。
T∈[1,1000]
a,b∈[1,1014]
输出描述:
每组数据输出结果，并换行。
示例1
输入
11 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 1 100
输出
0 0 0 1 0 1 0 2 1 1 111
备注:
数字的圈的个数请根据样例自行理解。
题解
数位$dp$。
$dp[i][j]$表示数字长度有$i$位，且第$i$位为$j$的总和，统计一下就可以了。
#include <bits/stdc++.h>
using namespace std;long long dp[16][10];
long long b[20], a[20];
long long c[20], sz;/*
0 1
1 0
2 0
3 0
4 1
5 0
6 1
7 0
8 2
9 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;
}