[luogu3413]萌数

luogu

考虑数位dp

怎么判断一个数是不是萌数?

只要知道其中某一位和它的前一位相等或者和前一位的前一位相等,那么它就是一个萌数

什么样的数不是萌数?

对于它的每一位都有\(w_i\neq w_{i-1}\)和\(w_i\neq w_{i-2}\)

记f[a][b][i]表示前一位是b,b的前一位是a,当前是第i位的萌数个数

其他的套模板做就好

#include<bits/stdc++.h>

using namespace std;

const int _=1005,mod=1e9+7;

int re(){

    int x=0,w=1;char ch=getchar();

    while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}

    while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();

    return x*w;

}

char w[_];

int ans,len,L,R,f[11][11][_];

void add(int&x,int y){x=(x+y)%mod;}

bool check(){//不想写高精所以单独check一下左端点

    for(int i=2;i<=len;i++)

        if(w[i]==w[i-1]||w[i]==w[i-2])return 0;

    return 1;

}

int dfs(int p,int t1,int t2,bool lim,bool zero){

    if(p==len+1)return 1;

    if(!lim&&!zero&&f[t1][t2][p]!=-1)return f[t1][t2][p];

    int up=lim?w[p]-'0':9,res=0;

    for(int i=0;i<=up;i++){

        if(i==t1||i==t2)continue;

        if(zero&&!i)add(res,dfs(p+1,10,10,lim&&(i==up),1));

        else add(res,dfs(p+1,t2,i,lim&&(i==up),0));

    }

    return (!lim&&!zero)?f[t1][t2][p]=res:res;

}

int main(){

    memset(f,-1,sizeof(f));

    scanf("%s",w+1);len=strlen(w+1);

    for(int i=1;i<=len;i++)L=(1ll*L*10%mod+w[i]-'0')%mod;

    if(check())ans=mod-1;

    add(ans,dfs(1,10,10,1,1));

    memset(f,-1,sizeof(f));

    scanf("%s",w+1);len=strlen(w+1);

    for(int i=1;i<=len;i++)R=(1ll*R*10%mod+w[i]-'0')%mod;

    ans=(dfs(1,10,10,1,1)-ans+mod)%mod;

    printf("%lld\n",(1ll*R-L+1+mod-ans+mod)%mod);

    return 0;

}

巴特西

[luogu3413]萌数

[luogu3413]萌数

最新文章

热门文章