洛谷P3413 SAC#1 - 萌数（数位dp）

题目描述

辣鸡蒟蒻SOL是一个傻逼，他居然觉得数很萌！

好在在他眼里，并不是所有数都是萌的。只有满足“存在长度至少为2的回文子串”的数是萌的——也就是说，101是萌的，因为101本身就是一个回文数；110是萌的，因为包含回文子串11；但是102不是萌的，1201也不是萌的。

现在SOL想知道从l到r的所有整数中有多少个萌数。

由于答案可能很大，所以只需要输出答案对1000000007（10^9+7）的余数。

输入输出格式

输入格式：

输入包含仅1行，包含两个整数：l、r。

输出格式：

输出仅1行，包含一个整数，即为答案。

输入输出样例

输入样例#1：复制

1 100

输出样例#1：复制

输入样例#2：复制

100 1000

输出样例#2：复制

说明

记n为r在10进制下的位数。

对于10%的数据，n <= 3。

对于30%的数据，n <= 6。

对于60%的数据，n <= 9。

对于全部的数据，n <= 1000，l < r。

题解

　　我数位dp门都没入呢……

　　别指望我能讲啥，自己看代码理解吧……

　　只要注意一下下面代码里的$Pre$和$per$，一个表示前一个数，一个表示前两个数，因为回文数只会有$aba$和$aa$两种类型，然后只要注意特判一下当前位置是$1$的就行了

 //minamoto

 #include<iostream>

 #include<cstring>

 #include<cstdio>

 #define ll long long

 using namespace std;

 const int N=,mod=1e9+;

 char s1[N],s2[N];ll dp[N][N][];int a[N];

 ll dfs(int pos,int Pre,int per,int t,int k,int flag){

     if(pos<=) return t;

     if(!flag&&~dp[pos][Pre][t]) return dp[pos][Pre][t];

     int end=flag?a[pos]:;ll res=;

     for(int i=;i<=end;++i)

     (res+=dfs(pos-,i,k?Pre:-,t||(i==Pre&&k)||(i==per&&k),k||i,flag&&(i==end)))%=mod;

     if(!flag&&k&&~per) dp[pos][Pre][t]=res;

     return res;

 }

 int solve(char *s){

     int len=,slen=strlen(s+);

     while(slen) a[++len]=s[slen--]-'';

     memset(dp,-,sizeof(dp));

     return dfs(len,-,-,,,);

 }

 int main(){

     scanf("%s%s",s1+,s2+);

     int len=strlen(s1+);

     if(s1[len]!=) s1[len]-=;

     else s1[len-]-=,s1[len]='';

     printf("%d\n",(solve(s2)-solve(s1)+mod)%mod);

     return ;

 }

巴特西

洛谷P3413 SAC#1 - 萌数（数位dp）

题目描述

输入输出格式

输入输出样例

说明

最新文章

热门文章