Link
Solution
从高位到低位DP 表示第位为，卡不卡下界，卡不卡上界，有无，有无，有重复次的了/最后一位已经重复了次
Code
所有的循环都加大括号有种错落有致的赶脚～
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
void Divide(int64 x,int bit[],int &n) {
for(n=0;x;x/=10) bit[++n]=x%10;
}
int main() {
freopen("input","r",stdin);
static int lb[20],rb[20],ln,rn;
static int64 f[12][10] [2][2] [2][2] [3];
//第[]位，为[]，卡/不卡下[]/上[] 是否有4[]/8[] 0:有3位了 1/2:已经重复了1/2次[]
int64 L,R;is>>L>>R;
Divide(L,lb,ln);
Divide(R,rb,rn);
for(int x=0;x<10;++x)
f[11][x][x==lb[11]][x==rb[11]][x==4][x==8][1]=lb[11]<=x && x<=rb[11];
for(int i=10;i;--i) {
for(int cx=0;cx<10;++cx) {
for(int px=0;px<10;++px) {
for(int pl=0;pl<2;++pl) {
for(int pr=0;pr<2;++pr) {
for(int p4=0;p4<2;++p4) {
for(int p8=0;p8<2;++p8) {
for(int p3=0;p3<3;++p3) {
if((pl && cx<lb[i]) || (pr && cx>rb[i]) || (p4 && p8)) continue;
f[i][cx][pl && cx==lb[i]][pr && cx==rb[i]][p4 || cx==4][p8 || cx==8][!p3?0:(cx==px?(p3+1)%3:1)]+=f[i+1][px][pl][pr][p4][p8][p3];
}
}
}
}
}
}
}
}
int64 Ans=0;
for(int x=0;x<10;++x) {
for(int cl=0;cl<2;++cl) {
for(int cr=0;cr<2;++cr) {
for(int c4=0;c4<2;++c4) {
for(int c8=0;c8<2;++c8) {
Ans+=(!c4 || !c8)*f[1][x][cl][cr][c4][c8][0];
}
}
}
}
}
os<<Ans<<'\n';
return 0;
}