luogu 3413 SAC#1 - 萌数
2021-02-13 05:15
阅读：548
题目描述
辣鸡蒟蒻SOL是一个傻逼，他居然觉得数很萌！
好在在他眼里，并不是所有数都是萌的。只有满足“存在长度至少为2的回文子串”的数是萌的——也就是说，101是萌的，因为101本身就是一个回文数；110是萌的，因为包含回文子串11；但是102不是萌的，1201也不是萌的。
现在SOL想知道从l到r的所有整数中有多少个萌数。
由于答案可能很大，所以只需要输出答案对1000000007（10^9+7）的余数。
输入输出格式
输入格式：
输入包含仅1行，包含两个整数：l、r。
输出格式：
输出仅1行，包含一个整数，即为答案。
输入输出样例
输入样例#1： 复制
1 100
输出样例#1： 复制
10
输入样例#2： 复制
100 1000
输出样例#2： 复制
253
说明
记n为r在10进制下的位数。
对于10%的数据，n
对于30%的数据，n
对于60%的数据，n
对于全部的数据，n
用记忆化搜索实现数位dp
如果没有限位就可以记忆化
有限位就要往下递归
还要考虑前导0
1 #include2 #include 3 #include 4 #include 5 #include 6 using namespace std; 7 typedef long long lol; 8 lol f[1001][12][12][2],Mod=1e9+7; 9 char s1[1001],s2[1001],s[1001]; 10 lol dfs(int pos,int pre,int bef,int t,int k,int flag) 11 {int i; 12 if (pos0) return t; 13 if (!flag&&f[pos][pre+1][bef+1][t]!=-1) return f[pos][pre+1][bef+1][t]; 14 int end; 15 lol cnt=0; 16 if (flag) end=s[pos]-‘0‘; 17 else end=9; 18 for (i=0;i) 19 { 20 cnt+=dfs(pos-1,i,k?pre:-1,t||((i==pre)&&k)||((i==bef)&&k),k||(i!=0),flag&&(i==end)); 21 cnt%=Mod; 22 } 23 if (!flag&&k&&bef!=-1) f[pos][pre+1][bef+1][t]=cnt; 24 return cnt; 25 } 26 lol solve(char ch[]) 27 {int i; 28 memset(f,-1,sizeof(f)); 29 int len=strlen(ch); 30 for (i=0;i ) 31 s[len-i-1]=ch[i]; 32 while (s[len-1]==‘0‘) len--; 33 return dfs(len-1,-1,-1,0,0,1); 34 } 35 int main() 36 {int i; 37 cin>>s1>>s2; 38 int len=strlen(s1); 39 s1[len-1]--; 40 for (i=len-1;i>=0;i--) 41 if (s1[i]‘0‘) s1[i]+=10,s1[i-1]--; 42 printf("%lld\n",(solve(s2)-solve(s1)+Mod)%Mod); 43 }
上一篇：js递归实现深拷贝
下一篇：Windows 10清理磁盘空间
文章来自：搜素材网的编程语言模块，转载请注明文章出处。
文章标题：luogu 3413 SAC#1 - 萌数
文章链接：http://soscw.com/index.php/essay/54748.html
文章标题：luogu 3413 SAC#1 - 萌数
文章链接：http://soscw.com/index.php/essay/54748.html
评论
亲，登录后才可以留言！