P3413 SAC#1 – 萌数

题目

洛谷

数位动规用爆搜真好玩

做法

含有回文串实际我们仅需判断是否有\(2/3\)回文串

\(Dfs(now,num,pre,ly,lead,prel,top)\)：

在第\(now\)位

\(now-1\)位，\(now-2\)位

是否合法

\(now-1\)位是否为前导\(0\)，\(now-2\)为是否为前导\(0\)

是否受限

My complete code

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL maxn=1009,p=1e9+7;
LL ans;
LL a[maxn],f[maxn][10][10][2][2][2];
char s1[maxn],s2[maxn];
LL Dfs(LL now,LL num,LL pre,LL ly,LL lead,LL prel,LL top){
if(!now) return ly;
if(!top && f[now][num][pre][ly][lead][prel]!=-1) return f[now][num][pre][ly][lead][prel];
LL ret(0);
LL Up=top?a[now]:9;
for(LL i=0;i<=Up;++i)
    (ret+=Dfs(now-1,i,num,ly||(!lead&&i==num)||(!prel&&i==pre),lead&&!i,lead,top&&(i==Up))%p)%=p;
if(!top) f[now][num][pre][ly][lead][prel]=ret;
return ret;
}
int main(){
scanf(" %s %s",s1+1,s2+1);
LL nl(strlen(s1+1)),nr(strlen(s2+1));
LL tot(0);
for(LL i=nr;i>=1;--i) a[++tot]=s2[i]-'0';
memset(f,-1,sizeof(f));
ans+=Dfs(tot,0,0,0,1,1,1);
tot=0;
for(LL i=nl;i>=1;--i) a[++tot]=s1[i]-'0';
if(nl==1 && a[1]==0){
cout<<ans;
return 0;
}
--a[1];
LL now(1);
while(a[now]<0){
a[now]=9;
--a[++now];
}
while(a[tot]==0) --tot;
ans=(ans-Dfs(tot,0,0,0,1,1,1)+p)%p;
cout<<ans;
return 0;
}