RT

#include<bits/stdc++.h>
#define N 1010
#define NUM 11
#define re register
#define int long long
using namespace std;
inline int read(){int x=0,w=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*w;}
const int mod=1e9+7;
int dp[N][NUM][NUM][2][2][2];
char s1[N],s2[N];

int num[N],len,slen,len1,len2;
 
inline int dfs(int pos,int pre,int gpre,bool f,bool _0,bool free)
{
	if(pos<=0) return f;
	if(~dp[pos][pre][gpre][f][_0][free]) return dp[pos][pre][gpre][f][_0][free];
	int CE= free ? 9 : num[pos],res=0;
	for(re int i=0;i<=CE;i++)
		res=(res+dfs(pos-1,i,pre,f||((i==pre)&&_0)||((i==gpre)&&_0),_0||(i!=0),free||(i<CE))%mod)%mod;
	return dp[pos][pre][gpre][f][_0][free]=res;
}

inline int calc(char s[])
{
	slen=strlen(s+1);len=0;
	for(re int i=slen;i>=1;i--) num[++len]=s[i]-'0';
	while(!num[len]) len--;
	memset(dp,-1,sizeof(dp));
	return dfs(len,-1,-1,0,0,0);
}

signed main()
{
	scanf("%s%s",s1+1,s2+1);
	int len=strlen(s1+1),p;
	for(p=len;p>=1&&s1[p]=='0';p--) s1[p]='9';
	s1[p]-=1;	
	printf("%lld\n",((calc(s2)-calc(s1))%mod+mod)%mod);
	return 0;
}

本地、IDE测试样例一都没过，本来打算测一下复杂度对不对，结果就A了

测评记录