题解 P3413 【SAC#1 - 萌数】

· · 题解

题解-萌数

\texttt{Introduction}

夫蒟蒻初学数位 \texttt{dp}，寻水题而得《萌数》，乃谔谔做之。初适，做之悠然。而样例不过，渐生焦躁，AC时已过三，而错之甚奇，乃记之。

博客中此文

\texttt{Description}

萌数 求区间 [L,R] 中有长度大于 2 的回文子串的数量。 数据范围：1\le L<R\le 10^{1000}。

\texttt{Solution}

数位 \texttt{dp} 典型题，如果你没学过数位 \texttt{dp} 就跳进传送门→[传送门]。用记忆化搜索模型，用 \texttt{DP(n)} 表示 [1,n] 区间中的答案，p 表示 n 的位数，nl_i 表示 n 从右往左第 i 位。

\texttt{Dfs(int~w,int~d,int~ld,bool~free,bool~hw)}

表示：

当前要求从右往左第 w 位数。

第 w+1 位数为 d。

第 w+2 位数为 ld。

如果前 p-w 位和 n 相同，free=0；否则 free=1。

如果前 p-w 位中已经出现了“长度大于 2 的回文子串”，fw=1；否则 fw=0。

如果找到的第 w 个数字 i 满足 i==d 或 i==ld，就说明有了长度至少为 2 的回文子串。用 f_{w,d,ld,hw} 数字记下答案，完成记忆化搜索。

code

lng Dfs(int w,int d,int ld,bool free,bool hw){
    if(!w) return hw;
    if(free&&~f[w][d][ld][hw]) return f[w][d][ld][hw];
    int up=free?9:nl[w]; lng res=0;
    for(int i=0;i<=up;i++)
        (res+=Dfs(w-1,i,d,free||i<up,hw||i==d||i==ld))%=mod;
    /*
    下一位是w-1位，下一个数的上一个数是i，下一个数的上上个数是d。
    如果原来就free==1或者i与n的第w位不相同下一个free=1。
    如果原来就有了长度为2的回文子串或i,d形成回文子串或i,d,ld形成回文子串，下一个fw=1。
    */
    if(free) f[w][d][ld][hw]=res;
    return res;
}

所以

+\sum_{j=1}^{nl_p-1}\texttt{Dfs(p-1,j,10,1,0)} +\texttt{Dfs(p-1,}nl_p\texttt{,10,0,0)}

。为什么 ld=10 ？因为 ld 还不存在，而且如果你赋值为 0，会影响 \texttt{Dfs} 结果；如果你赋值为 -1，会在记忆化数组的下标上 \texttt{RE}。所以赋值为 10 是较好选择，然后记忆化数组的下标范围就要开 11。蒟蒻因为这里赋值成 -1 而 \texttt{WA} 了两次。

code

lng DP(char*n,lng a){
    int p=strlen(n+1); lng res=0;
    for(int i=1;i<=p;i++) nl[i]=n[p+1-i]-'0';
    nl[1]+=a;
    if(p==1&&nl[1]<=0) return 0;
    for(int i=1;nl[i]<0&&i<=p;i++)
        nl[i]+=10,nl[i+1]--;
    while(!nl[p]&&p>1) p--;
    // debug(p,nl);
    memset(f,-1,sizeof f);
    for(int i=1;i<=p-1;i++)
        for(int j=1;j<=9;j++)
            (res+=Dfs(i-1,j,10,1,0))%=mod;  
    for(int j=1;j<=nl[p];j++)
        (res+=Dfs(p-1,j,10,j<nl[p],0))%=mod;
    return res;
}

然后最后答案就是 \texttt{DP(R)}-\texttt{DP(L-1)}，因为 L 和 R 远爆 \texttt{long long}，所以用字符串输入或处理。

\texttt{Code}

#include <bits/stdc++.h>
using namespace std;

//&Start
#define lng long long

//&Debug
template<class T>
void debug(int x,T*arr){
    for(int i=1;i<=x;i++)
        cout<<arr[i]<<"\n "[i<x];
}

//&DP
const int W=1010,D=10;
const lng mod=1e9+7;
char L[W],R[W];
int nl[W];
lng f[W][D][D+1][2];
lng Dfs(int w,int d,int ld,bool free,bool hw){
    if(!w) return hw;
    if(free&&~f[w][d][ld][hw]) return f[w][d][ld][hw];
    int up=free?9:nl[w]; lng res=0;
    for(int i=0;i<=up;i++)
        (res+=Dfs(w-1,i,d,free||i<up,hw||i==d||i==ld))%=mod;
    if(free) f[w][d][ld][hw]=res;
    return res;
}
lng DP(char*n,lng a){
    int p=strlen(n+1); lng res=0;
    for(int i=1;i<=p;i++) nl[i]=n[p+1-i]-'0';
    nl[1]+=a;
    if(p==1&&nl[1]<=0) return 0;
    for(int i=1;nl[i]<0&&i<=p;i++)
        nl[i]+=10,nl[i+1]--;
    while(!nl[p]&&p>1) p--;
    // debug(p,nl);
    memset(f,-1,sizeof f);
    for(int i=1;i<=p-1;i++)
        for(int j=1;j<=9;j++)
            (res+=Dfs(i-1,j,10,1,0))%=mod;  
    for(int j=1;j<=nl[p];j++)
        (res+=Dfs(p-1,j,10,j<nl[p],0))%=mod;
    return res;
}

//&Main
int main(){
    scanf("%s %s",L+1,R+1);
    printf("%lld\n",(DP(R,0)-DP(L,-1)+mod)%mod);
    return 0;
}

祝大家学习愉快！