不能更水的一道题。

记录[tex]aaaaa\cdots \rightarrow current[/tex](即我们当前DP到的串)的[tex]first[/tex](第一个数),[tex]last[/tex](最后一个数),[tex]cnt[/tex](数的个数),[tex]sum[/tex](数的和)以及[tex]ans[/tex](这段的答案)。往上做时可以直接合并信息。

需要预处理某一位为[tex]x[/tex]接下来的位任意的时候的信息。

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#define MAXN 100005
const long long mask=1000000007;
inline long long mod(long long a){return (a%mask+mask)%mask;}
struct info{long long first,last,cnt,sum,ans;};
inline info extend(info x,long long offs)
{
	info ret;
	ret.first=mod(x.first+offs);
	ret.last=mod(x.last+offs);
	ret.cnt=x.cnt;
	ret.sum=mod(x.sum+x.cnt*offs);
	ret.ans=mod(x.ans+(x.sum*2-x.first-x.last)*offs+(x.cnt-1)*mod(offs*offs));
	return ret;
}
inline info merge(info x,info y,long long offs)
{
	info ret;
	ret.first=mod(x.first+offs);
	ret.last=mod(y.last+offs);
	ret.cnt=mod(x.cnt+y.cnt);
	ret.sum=mod(x.sum+x.cnt*offs+y.sum+y.cnt*offs);
	ret.ans=mod(mod(x.ans+(x.sum*2-x.first-x.last)*offs+(x.cnt-1)*mod(offs*offs))+mod(y.ans+(y.sum*2-y.first-y.last)*offs+(y.cnt-1)*mod(offs*offs))+(x.last+offs)*(y.first+offs));
	return ret;
}
int a,b,n;
long long pow10[MAXN],pow2[MAXN];
char sl[MAXN],sr[MAXN];
info f[MAXN][2];
int main()
{
	pow10[0]=pow2[0]=1;
	for(int i=1;i<MAXN;i++) pow10[i]=mod(pow10[i-1]*10),pow2[i]=mod(pow2[i-1]*2);
	scanf("%d%d",&a,&b);
	f[0][0]=(info){a,a,1,a,0},f[0][1]=(info){b,b,1,b,0};
	for(int i=1;i<MAXN;i++) f[i][0]=merge(f[i-1][0],f[i-1][1],mod(a*pow10[i])),f[i][1]=merge(f[i-1][0],f[i-1][1],mod(b*pow10[i]));
//	for(int i=0;i<3;i++) printf("%lld %lld\n",f[i][0].ans,f[i][1].ans);
	scanf("%s%s",sl,sr),n=strlen(sl);
	info al,ar;
	if(sl[n-1]==b+'0') al=merge(f[0][0],f[0][1],0); else al=f[0][0];
	if(sr[n-1]==b+'0') ar=merge(f[0][0],f[0][1],0); else ar=f[0][0];
	for(int i=n-2;~i;i--)
	{
		if(sl[i]==b+'0') al=merge(f[n-1-i][0],extend(al,mod(b*pow10[n-1-i])),0);
		else al=extend(al,mod(a*pow10[n-1-i]));
	}
	for(int i=n-2;~i;i--)
	{
		if(sr[i]==b+'0') ar=merge(f[n-1-i][0],extend(ar,mod(b*pow10[n-1-i])),0);
		else ar=extend(ar,mod(a*pow10[n-1-i]));
	}
	printf("%lld\n",mod(ar.ans-al.ans));
	return 0;
}