传送门 题目描述 给出一个区间[l,r][l,r][l,r], 求这个区间内有多少个数字满足如下条件: 每相邻两个数位和为素数 其中至少一个数位为 111 没有前导 000 数据范围 1≤l≤r≤10101 \le l \le r \le 10^{10}1≤l≤r≤1010 思路 典型的 数位DP 计算方式为 f(r)−f(l−1)f(r) - f(l-1)f(r)−f(l−1) f(x)f(x)f(x) 代表 [0,x][0,x][0,x]中符合条件的数字,我们通过从高到低枚举 xxx 的每一位来进行记忆化搜索即可 不懂 数位DP 的可以去看下这篇blog CODE /**...