P3413 SAC#1 - 萌数
斯德哥尔摩
2018-10-16 20:31:10
[P3413 SAC#1 - 萌数](https://www.luogu.org/problemnew/show/P3413)
首先$\text{回文串}>2$就好啦。。。
所以我们只要判断两种情况：$aa$或者$aba$。
设$dp[i][j][k]$表示第$i$位为$j$，$i-1$位为$k$的所有萌数个数。
那么显然对于重复很难判断。。。
有$2$种方法可以解决这个问题：
1. 再开一维数组记录是否出现。
2. 把$dp[i][j][k]$记录的是当前状态下不是萌数的个数。
第一种显然可做，但是第二种更好。
因为$\text{全集}-\text{非萌数的个数}$就是答案。
那么这样的话只要特判$i==1$的情况，$dp$数组可以方便的求了。
之后就是数位$dp$了~~（开始瞎搞。。。）~~
附代码：
```cpp
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<string>
#include<cstring>
#define MAXN 1010
#define MOD 1000000007LL
using namespace std;
long long ans,dp[MAXN][10][10];
string l,r;
inline int read(){
int date=0,w=1;char c=0;
while(c<'0'||c>'9'){if(c=='-')w=-1;c=getchar();}
while(c>='0'&&c<='9'){date=date*10+c-'0';c=getchar();}
return date*w;
}
void make(){
int m=MAXN-10;
for(int i=2;i<=m;i++)
for(int j=0;j<=9;j++)
for(int k=0;k<=9;k++){
if(j==k)continue;
for(int x=0;x<=9;x++){
if(x==j||x==k)continue;
dp[i][j][k]+=dp[i-1][k][x];
}
if(i==2)dp[i][j][k]++;
dp[i][j][k]%=MOD;
}
}
long long solve(string str){
int x=-1,y=-1,n=str.length();
long long num=0,ans=0;
bool flag=true;
for(int i=0;i<n;i++)num=(num*10+str[i]-'0')%MOD;
for(int i=1;i<n;i++)
for(int j=1;j<=9;j++)
for(int k=0;k<=9;k++)
ans=(ans+dp[i][j][k])%MOD;
if(n>1)ans+=10;
for(int i=n;i>1;i--){
int f=str[n-i]-'0';
for(int j=0;j<f;j++)
if(i!=n||j!=0)
for(int k=0;k<=9;k++){
if(x==j||y==j||j==k||x==k)continue;
ans=(ans+dp[i][j][k])%MOD;
}
if(f==x||f==y){
flag=false;
break;
}
y=x;x=f;
}
if(flag)for(int j=0;j<=str[n-1]-'0';j++)if(j!=x&&j!=y)ans=(ans+1)%MOD;
return (num+1-ans+MOD)%MOD;
}
void work(){
cin>>l>>r;
ans=(solve(r)-solve(l)+MOD)%MOD;
for(int i=1;i<l.length();i++)if(l[i]==l[i-1]||(i>1&&l[i]==l[i-2])){ans++;break;}
printf("%lld\n",ans%MOD);
}
int main(){
make();
work();
return 0;
}
```