题解 P3413 【SAC#1 - 萌数】

· · 题解

因为所要求的区间相当的大，因此我们不妨从它的数位入手进行dp。

根据萌数的性质，倘若要满足一个长度为len的字符串是萌数，那么这个串只需至少包含一个长度为2（对应偶回文），或者至少包含一个长度为3（对应奇回文）的回文串即可。至此，我们将题目进行了转化，即：如果一个串包含有一个长度为2或者长度为3的字符串，那么这个数就是萌数。

因此我们只需要讨论一个串的当前位pos，它的前一位pre1，以及它的前两位pre2即可。因此我们可以设计一个dp[pos][pre1][pre2]的dp数组。但是我们发现，如果这样去设计状态的话，部分合法以及非法状态会发生重叠：如果当前的枚举到的状态是dp[1][2][3]的状态（即代表枚举到的子串的状态位123）。此时的这个状态中，合法状态33123以及非法状态45123将会发生重叠。因此为了防止这种情况，我们考虑再开多一维判断是否在之前是否已经合法子串。故我们可以设计dp[pos][pre1][pre2][exist]代表，当前位置位pos，前一位为pre1，前两位为pre2，且之前存在/不存在子串的方案数。

而我们发现，当设计了exist这个状态之后，我们就不需要记录前两位pre2的信息了，因此我们只需要开一个三维的dp数组dp[pos][pre1][exist]即可。

而把状态设计好之后，我们就只需要直接套用记忆化搜索的数位dp的板子就可以很简单的解决了。

Code：

#include <bits/stdc++.h>
#define maxn 1005
using namespace std;
typedef long long ll;
ll dp[maxn][15][2];
char L[maxn],R[maxn];
int bit[maxn],len;
const int mod=1e9+7;
ll dfs(int pos,int pre1,int pre2,int exist,int lead,int limit){
    if(pos==0) return exist;
    if(pre1!=-1&&pre2!=-1&&!lead&&!limit&&dp[pos][pre1][exist]!=-1)
        return dp[pos][pre1][exist];
    int up=limit?bit[pos]:9;
    ll res=0;
    for(int i=0;i<=up;i++){
        int p=(lead&&i==0)?-1:i;
        res+=dfs(pos-1,p,pre1,exist|(p!=-1 && (p==pre1||p==pre2)),p==-1,limit&&(p==up));
        res%=mod;
    }
    if(pre1!=-1&&pre2!=-1&&!lead&&!limit) dp[pos][pre1][exist]=res;
    return res;
}
ll solve(char *str,bool sub){
    len=strlen(str);
    for(int i=1;i<=len;i++)
        bit[len-i+1]=str[i-1]-'0';
    if(sub){
        int now=1;
        while(bit[now]==0) bit[now++]=9;
        bit[now]--;
        while(!bit[len] && len) len--;
    }
    memset(dp,-1,sizeof(dp));
    return dfs(len,-1,-1,0,1,1);
}
int main()
{
    scanf("%s%s",L,R);
    printf("%lld",((solve(R,0)-solve(L,1))%mod+mod)%mod);
    return 0;
}