有趣的子区间
时间限制:10000ms
单点时限:1000ms
内存限制:256MB
描述
如果一个区间[a, b]内恰好包含偶数个回文整数，我们就称[a, b]是有趣的区间。
例如[9, 12]包含两个回文整数9和11,所以[9, 12]是有趣的区间。[12, 20]包含0个回文整数，所以[12, 20]也是有趣的。
现在给定一个区间[a, b]，请你求出[a, b]中所有满足a ≤ p ≤ q ≤ b的子区间[p, q]有多少个有趣的。
输入
第一行包含两个整数a和b。
对于30%的数据，1 ≤ a ≤ b ≤ 1000
对于60%的数据，1 ≤ a ≤ b ≤ 100000
对于100%的数据, 1 ≤ a ≤ b ≤ 1000000000
输出
有趣的子区间数目
- 样例输入
-
10 20
- 样例输出
-
46
预处理是不难的，对称枚举也不多。我想着试一试数位DP。