摘要：
解释：数字$DP$，$f_{i，j}$表示在$i$位置，除了$0$之外还有$j$方案数据点：无C++代码：#include＜cstio＞#include˂cstring＞intTim，num[20]；longlongM[5][20]；longlongrun｛ifreturn0；if（！
题目大意：多个询问，每个询问问$[l,r](1leqslant lleqslant rleqslant10^{18})$内有多少个数满足非零数位小于等于$3$。
题解：数位$DP$，$f_{i,j}$表示在第$i$位，有$j$个数位不是$0$的方案数
卡点：无
C++ Code：
#include <cstdio>
#include <cstring>
int Tim, num[20];
long long M[5][20];
long long run(int x, int cnt, int lim) {
if (cnt > 3) return 0;
if (!x) return 1;
if ((~M[cnt][x]) && !lim) return M[cnt][x];
long long ans = 0;
for (int op = lim, i = lim ? num[x] : 9; ~i; i--, op = 0) {
ans += run(x - 1, cnt + bool(i), op);
}
if (!lim) M[cnt][x] = ans;
return ans;
}
long long solve(long long x) {
int len = 0;
while (x) {
num[++len] = x % 10;
x /= 10;
}
return run(len, 0, 1);
}
int main() {
scanf("%d", &Tim);
memset(M, -1, sizeof M);
while (Tim --> 0) {
long long l, r;
scanf("%lld%lld", &l, &r);
printf("%lld
", solve(r) - solve(l - 1));
}
return 0;
}