是一道数位DP。可以用记忆化搜索解决。
这道题细节非常多。可以考虑分步进行。
求\(L?\)到\(R?\)之间的符合条件的数，可以等价为求\(\text{1~R}?\)之间的符合条件的数减去$text{1~L-1}$之间符合条件的数。
那我先写一个搜索求解\(L?\)：
void DFS (int X , int K , int U , int _4 , int _8 , int T) {
//变量名介绍：X代表当前的位数，K代表当前位所填的数字，U=1表示卡上界，否则不卡。_4和_8分别是有没有出现过4和8，T=3表示已完成三连号，否则表示未完成，且T等于当前连号。
if (X == N - 1) {
if (T == 3) ++ Ans ;
return ;
}
//如果符合条件，就累加答案。
int Goto = Base - 1 ;
if (U) Goto = L[X + 1] ;
//如果卡了上界，应该进行特判。
for (int i = 0 ; i <= Goto ; ++ i) {
if (_4 && i == 8) continue ;
if (_8 && i == 4) continue ;
//如果同时出现8和4就跳过这一步。
if (T == 3) {
DFS ( X + 1 , i , L[X + 1] == i && U ? 1 : 0 ,
i == 4 || _4 ,i == 8 || _8 , 3) ;
} else DFS ( X + 1 , i , L[X + 1] == i && U ? 1 : 0 ,
i == 4 || _4 ,i == 8 || _8 , i == K ? T + 1 : 1) ;
}
}上面的代码可以在数位较少时得出正确结果。但是当数位较大(\(10^{10}≤L<10^{11}?\))就会TLE。
搜索是盲目的，因为它做了很多重复性的工作。(By Instructor Li)
对于\(\text{DFS (int X , int K , int U , int _4 , int _8 , int T)}?\)，它的同一组参数所得到的结果应该是一样的。这是进行记忆化搜索的前提。
具体地说，开一个数组\(\text{ F[20][10][2][2][2][4]}\)。其中六个维度分别对应\(\text{DFS}\)的六个参数。
我们每次搜索完成后，把Ans的改变量\(\delta Ans\)结果记录在上述数组里，下一次遇到同一组参数，只要在\(Ans\)增加上已记录的答案，然后返回即可。
改进版本：
void DFS (int X , int K , int U , int _4 , int _8 , int T) {
//这一部分的变量名解释和刚才一样。
if (X == N - 1) {
if (T == 3) ++ Ans ;
return ;
}
if (F[X][K][U][_4][_8][T] != -1) {
Ans += F[X][K][U][_4][_8][T] ;
return ;
}
//遇到同一组参数，只要在$Ans$增加上已记录的答案，然后返回即可。
F[X][K][U][_4][_8][T] = Ans;
int Goto = Base - 1 ;
if (U) Goto = L[X + 1] ;
for (int i = 0 ; i <= Goto ; ++ i) {
if (_4 && i == 8) continue ;
if (_8 && i == 4) continue ;
if (T == 3) {
DFS ( X + 1 , i , L[X + 1] == i && U ? 1 : 0 , i == 4 || _4 ,i == 8 || _8 , 3) ;
} else DFS ( X + 1 , i , L[X + 1] == i && U ? 1 : 0 , i == 4 || _4 ,i == 8 || _8 , i == K ? T + 1 : 1) ;
}
F[X][K][U][_4][_8][T] = Ans - F[X][K][U][_4][_8][T] ;
//把Ans的改变量δAns结果记录在上述数组里
}- 这个版本已经可以快速完成求解。
其他要点：
- 注意开\(\text{long long}\)
- 注意细节，例如\(L-1\)的边界情况。
Thanks !