脚本宝典收集整理的这篇文章主要介绍了SAC#1 - 萌数，脚本宝典觉得挺不错的，现在分享给大家，也给大家做个参考。

P3413 SAC#1 - 萌数

解题思路：

我们反着来考虑这道题：如何判断一个数不含回文串。

思考一下，会发现：当一个数的任意一位都不和前两位的数字相同时，这个数就不含回文串

设 (f[pos][PRe][gpre]) 表示在 (pos) 位时前一位是 (epre) 前两位是 (gpre) 的非回文串数.

利用字符串读入，转移时注意前导零不要识别成合法的前缀，即可解决。

// P3413 SAC#1 - 萌数
#include<bITs/stdc++.h>
using namespace std;
#define int long long
const int mod=1e9+7,N=1005;
string l,r;
int len[N];
int f[N][10][10];
int DFs(int pos,int pre,int gpre,bool lim,bool zero){
	if(pos==0) return 1;
	if(f[pos][pre][gpre]!=-1&&!lim&amp;&!zero&&pre!=-1&&gpre!=-1) return f[pos][pre][gpre];
	int up=lim?len[pos]:9;
	int ans=0;
	for(int i=0;i<=up;i++){
		if(i!=pre&&i!=gpre&&!zero)
			ans=(ans+dfs(pos-1,i,pre,lim&&i==len[pos],0))%mod;
		else if(zero)
			ans=(ans+dfs(pos-1,(i==0&&zero)?-1:i,-1,lim&&i==len[pos],i==0&&zero))%mod;
	}
	if(!lim&&!zero&&pre!=-1&&gpre!=-1) return f[pos][pre][gpre]=ans;
	return ans;
}
int slove(){
	int s=l.length();
	for(int i=0;i<s;i++) len[s-i]=l[i]-'0';
	int ans1=dfs(s,-1,-1,1,1);
	s=r.length();
	for(int i=0;i<s;i++) len[s-i]=r[i]-'0';
	int ans2=dfs(s,-1,-1,1,1);
	ans1--;
	s=l.length();
	for(int i=2;i<=s;i++)
		if(l[i]==l[i-1]||(l[i]==l[i-2]&&(i-2>=1))){
			ans1++; break;
		}
	return (ans2-ans1)%mod;
}
signed main(){
	cin>>l>>r;
	memset(f,-1,sizeof f);
	int L=0,R=0;
	int s1=l.length(),s2=r.length();
	for(int i=0;i<s1;i++) L=(L*10%mod+(l[i]^48))%mod;
	for(int i=0;i<s2;i++) R=(R*10%mod+(r[i]^48))%mod;
	printf("%lldn",((R-L-slove()+1)%mod+mod)%mod);
    System("pause");
	return 0;
} 

脚本宝典总结

以上是脚本宝典为你收集整理的SAC#1 - 萌数全部内容，希望文章能够帮你解决SAC#1 - 萌数所遇到的问题。

如果觉得脚本宝典网站内容还不错，欢迎将脚本宝典推荐好友。

本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ：384754419，请注明来意。