文章目录
R
e
s
u
l
t
Result
Result
H
y
p
e
r
l
i
n
k
Hyperlink
Hyperlink
D
e
s
c
r
i
p
t
i
o
n
Description
Description
S
o
l
u
t
i
o
n
Solution
Solution
C
o
d
e
Code
Code
R
e
s
u
l
t
Result
Result
H
y
p
e
r
l
i
n
k
Hyperlink
Hyperlink
https://www.luogu.com.cn/problem/P3413
D
e
s
c
r
i
p
t
i
o
n
Description
Description
求
[
L
,
R
]
[L,R]
[L,R]中有多少个数含有一个回文子串
数据范围：
L
≤
R
≤
1
0
1000
L\leq R\leq 10^{1000}
L≤R≤101000
S
o
l
u
t
i
o
n
Solution
Solution
显然一个回文子串必然含有一个长度为2或者3的回文子串，显然我们只用考虑后面的 这样的话我们就只关心是否存在某一位和前面那位或者前面的前面那位相同即可
设
f
r
e
s
t
,
l
a
s
t
,
h
f
f_{rest,last,hf}
frest,last,hf表示剩余
r
e
s
t
rest
rest位，上一位为
l
a
s
t
last
last，当前方案是否合法 （有人会问为什么不保存上一位的上一位，因为
l
a
s
t
last
last和
h
f
hf
hf就足够转移了【
l
l
a
s
t
llast
llast仅用于判断，不用于转移，所以不需要保存】）
L
,
R
L,R
L,R特别大的话当做字符串处理即可，
L
−
1
L-1
L−1也要特殊处理
接下来就套数位
d
p
dp
dp的板子了
C
o
d
e
Code
Code
#include<cctype>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define LL long long
#define mod 1000000007
using namespace std
;char s1
[1010],s2
[1010];
int a
[1010],m
;
LL f
[1010][10][2];
inline LL
read()
{
char c
;LL d
=1,f
=0;
while(c
=getchar(),!isdigit(c
)) if(c
=='-') d
=-1;f
=(f
<<3)+(f
<<1)+c
-48;
while(c
=getchar(),isdigit(c
)) f
=(f
<<3)+(f
<<1)+c
-48;
return d
*f
;
}
inline LL
dfs(int rest
,int last
,int llast
,bool lead
,bool limit
,bool hf
)
{
if(rest
==0) return hf
;
if(lead
&&limit
==0&&f
[rest
][last
][hf
]!=-1) return f
[rest
][last
][hf
];
int cancse
=limit
?a
[rest
]:9;
LL res
=0;
for(register int i
=0;i
<=cancse
;i
++)
(res
+=dfs(rest
-1,i
,lead
?last
:-1,lead
||i
,limit
&&i
==cancse
,hf
||((i
==llast
)&&lead
||(i
==last
)&&lead
)))%=mod
;
if(lead
&&limit
==0&&llast
!=-1) f
[rest
][last
][hf
]=res
;
return res
;
}
inline LL
solve(char s
[])
{
m
=strlen(s
);
for(register int i
=1;i
<=m
;i
++) a
[i
]=s
[m
-i
]^48;
memset(f
,-1,sizeof(f
));
return dfs(m
,-1,-1,0,1,0);
}
signed main()
{
scanf("%s%s",s1
,s2
);
int i
=1,n
=strlen(s1
);
while(s1
[n
-i
]=='0'&&i
<n
) s1
[n
-i
]='9',i
++;
s1
[n
-i
]-=1;
printf("%lld",(solve(s2
)-solve(s1
)+mod
)%mod
);
}
