本题由世界上最蒟蒻最辣鸡最撒比的Sol提供。
寂月城网站是完美信息教室的官网。地址:http://191.101.11.174/mgzd 。
题目描述辣鸡蒟蒻Sol是一个傻逼,他居然觉得数很萌!
好在在他眼里,并不是所有数都是萌的。只有满足“存在长度至少为2的回文子串”的数是萌的——也就是说,101是萌的,因为101本身就是一个回文数;110是萌的,因为包含回文子串11;但是102不是萌的,1201也不是萌的。
现在Sol想知道从l到r的所有整数中有多少个萌数。
由于答案可能很大,所以只需要输出答案对1000000007(10^9+7)的余数。
输入格式输入包含仅1行,包含两个整数:l、r。
还以为我这个辣鸡会被卡时没想到这么水??? 你记录一下last,last1来判断是否存在长度至少为2的回文子串 并用flag表示来的路上是否已经存在 注意前导0隔位回文是错的 你在遍历一下l是不是符合条件的数,减去
#include<bits/stdc++.h>#define re return#define ll long long#define inc(i,l,r) for(ll i=l;i<=r;++i)using namespace std;ll n,m,len,num[1002],f[1005][2][10][10];ll mod=1000000007;template<typename T>inline voID rd(T&x){ len=0; char c;bool f=0; while((c=getchar())<‘0‘||c>‘9‘); num[++len]=c^48; while((c=getchar())>=‘0‘&&c<=‘9‘) num[++len]=c^48;}inline ll dfs(int pos,int limit,int flag,int last,int last1,int lead){ if(pos==len+1)re flag; if(lead&&!limit&&(~last1)&&(~f[pos][flag][last][last1]))re f[pos][flag][last][last1]; int up=limit?num[pos]:9; ll res=0; inc(i,0,up) { if(flag)res=(res+dfs(pos+1,limit&&i==up,flag,i,last,1))%mod; else res=(res+dfs(pos+1,lead&&(last==i|last1==i),lead?last:-1,lead|i))%mod; } if(!limit&&(~last1))f[pos][flag][last][last1]=res; re res;}inline bool judge(){ if(num[2]==num[1])re 1; inc(i,3,len) { if(num[i]==num[i-1])re 1; if(num[i]==num[i-2])re 1; } re 0;}int main(){ freopen("in.txt","r",stdin); memset(f,-1,sizeof f); rd(n); ll ans1=dfs(1,1,0,-1,0)-judge(); rd(m); ll ans2=dfs(1,0); printf("%lld",(ans2-ans1+mod)%mod); re 0;}总结
以上是内存溢出为你收集整理的SAC#1 - 萌数全部内容,希望文章能够帮你解决SAC#1 - 萌数所遇到的程序开发问题。
如果觉得内存溢出网站内容还不错,欢迎将内存溢出网站推荐给程序员好友。
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)