【-73】P3413 SAC#1 - 萌数[数位dp]

题目描述

辣鸡蒟蒻SOL是一个傻逼,他居然觉得数很萌!

好在在他眼里,并不是所有数都是萌的。只有满足“存在长度至少为2的回文子串”的数是萌的——也就是说,101是萌的,因为101本身就是一个回文数;110是萌的,因为包含回文子串11;但是102不是萌的,1201也不是萌的。

现在SOL想知道从l到r的所有整数中有多少个萌数。

由于答案可能很大,所以只需要输出答案对1000000007(10^9+7)的余数。

输入输出格式

输入格式:

输入包含仅1行,包含两个整数:l、r。

输出格式:

输出仅1行,包含一个整数,即为答案。

输入输出样例

输入样例#1:

1 100

输出样例#1:

10

输入样例#2:

100 1000

输出样例#2:

253

说明

记n为r在10进制下的位数。
对于10%的数据,n <= 3 。
对于30%的数据,n <= 6 。
对于60%的数据,n <= 9 。
对于全部的数据,n <= 1000,l < r 。

题解

数位dp
很容易知道,每一个萌数都包括1个长度为2或者长度为3的回文数

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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
#include<bits/stdc++.h>
using namespace std;
int read()
{
char s;
int k=0,base=1;
while((s=getchar())!='-'&&s!=EOF&&!(s>='0'&&s<='9'));
if(s==EOF)exit(0);
if(s=='-')base=-1,s=getchar();
while(s>='0'&&s<='9')
{
k=k*10+(s-'0');
s=getchar();
}
return k*base;
}
void write(int x)
{
if(x<0)
{
putchar('-');
write(-x);
}
else
{
if(x/10)write(x/10);
putchar(x%10+'0');
}
}
const long long mod=1000000007;
long long f[1005][10][10];//f[i][j][k]表示第i位为j,第i-1位为k时不是萌数的方案总数
//注意位数为从右往左数
string L,R;
int ll,lr;
inline void dp(int x)//预处理
{
for (int i=2;i<=x;i++)
for (int j=0;j<=9;j++)
for (int k=0;k<=9;k++)
if (j!=k)
{
for (int l=0;l<=9;l++)
{
if (j!=l&&k!=l)//从前往后推
f[i][j][k]+=f[i-1][k][l];
}
if (i==2) f[i][j][k]++;//只有2位特判
f[i][j][k]=(f[i][j][k]%mod+mod)%mod;//取模
}

}
inline int solve(string x)
{
int X=-1,Y=-1;
int n=x.length();
if (n==1) return 0;
long long tot=0,ans=0;
bool flag=true;
for (int i=0;i<n;i++) tot=(tot*10+x[i]-'0')%mod;//统计范围内有多少个数
for (int k=2;k<n;k++)//前面的先算出来
for (int i=1;i<=9;i++)
for (int j=0;j<=9;j++)
{
ans+=f[k][i][j];
ans%=mod;
}
for (int i=n;i>1;i--)//从大往小一位一位处理
{
int xx=x[n-i]-'0';
for (int j=0;j<xx;j++) if (j==0&&i==n) continue; //最大的一位为0已经算过了
else
for (int k=0;k<=9;k++)
{
if (j!=k&&X!=k&&X!=j&&Y!=j)//统计
ans=(ans+f[i][j][k])%mod;
}
if (xx==Y||xx==X)//前面几位出现回文
{
flag=false;
break;
}
Y=X;X=xx;//X:上一位(更大的),Y:上上位
}
if (n>1) ans+=10;//把0~10加上去,这些也不是萌数
int xx=x[n-1]-'0';
X=x[n-2]-'0';
Y=x[n-3]-'0';
if (flag)
for (int i=0;i<=xx;i++)//最后2位
{
if (i!=X&&i!=Y) ans++;
}
ans%=mod;
return ((tot+1-ans)%mod+mod)%mod;//加的1:0,所有数-不萌的数=萌数
}
int main()
{
cin>>L>>R;
ll=L.length();
lr=R.length();
dp(lr+1);
long long ans=((solve(R)-solve(L))%mod+mod)%mod;
for (int i=0;i<ll-1;i++)
{
if (L[i]==L[i+1]||(i!=ll-2&&L[i]==L[i+2]) )
{
ans++;break;
}
}
printf("%lld",ans);
return 0;
}