洛谷 3413 萌数

发表于 | 分类于 |

首先，显然在一个回文串首尾各添加一个相同字符，结果仍是回文串。
所以这题需要判断的就只有两种子串 \(\overline{aa},\overline{aba}\)。
其他情况都能转化成这俩。

然后就是数位 DP。
我的状态也很复杂啊……
记搜的话，记录位数、上一位、上上位、前面是否满足萌数的要求、上一位是否为前导零、上上位是否为前导零、是否贴着边界。

令 \(l - 1\) 的过程有点麻烦，可以按照高精的套路写。
不过直接跑 \(r - l\) 然后特判 \(l\) 貌似也行。

代码： 

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
#include <cstdio>
#include <cstring>
using namespace std;
const int LEN = 1e3;
const long long mod = 1e9 + 7;
char l[LEN + 5],r[LEN + 5];
int d[LEN + 5],tot;
long long f[LEN + 5][10][10][2][2][2];
long long ans;
long long dfs(int x,int num,int pre,int lovely,int lead,int prelead,int top)
{
    if(!x)
        return lovely;
    if(!top && ~f[x][num][pre][lovely][lead][prelead])
        return f[x][num][pre][lovely][lead][prelead];
    int bound = top ? d[x] : 9;
    long long ret = 0;
    for(register int i = 0;i <= bound;++i)
        ret = (ret + dfs(x - 1,i,num,lovely || (!lead && i == num) || (!prelead && i == pre),lead && !i,lead,top && i == bound)) % mod;
    if(!top)
        f[x][num][pre][lovely][lead][prelead] = ret;
    return ret;
}
int main()
{
    memset(f,-1,sizeof f);
    scanf("%s %s",l,r);
    for(register int i = strlen(r) - 1;~i;--i)
        d[++tot] = r[i] ^ '0';
    ans = dfs(tot,0,0,0,1,1,1);
    tot = 0;
    for(register int i = strlen(l) - 1;~i;--i)
        d[++tot] = l[i] ^ '0';
    --d[1];
    for(register int i = 1;i <= tot;++i)
        if(d[i] < 0)
            d[i] += 10,--d[i + 1];
    ans -= dfs(tot,0,0,0,1,1,1);
    printf("%lld\n",(ans + mod) % mod);
}