题目内容

定义一个整数是蛇形数，当且仅当它的每一位都大于等于它的右边一位。例如，$8,31$和$220$是蛇形数，但$35$和$202$ 不是。

题解思路

这道题要求我们计算区间[l,r]中有多少个整数是蛇形数，其中蛇形数定义为每一位数字都大于等于它右边的数字。

由于范围非常大$(l, r ≤ 10^{18})$ ，不能暴力枚举每个数字。这类题目可以使用数位DP（数字动态规划）来解决。

算法思路

1. 定义函数count(n)计算1到n范围内蛇形数的个数
2. 区间[l,r]内的蛇形数个数 = count(r) - count(l-1)