rt,在 #35 个点 TLE。

记录。

#include<bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;
const int mod=1000000007;
int m,d,n[2005],tot,f[2005][2005][5],ans1,ans2;
string r,t,l;
bool flag;
int dfs(int x,int rest,bool lead,bool lim,int temp){ 
	if(!x) return rest==0;
	if(!lead && !lim && f[x][rest][temp]!=-1) return (f[x][rest][temp]%mod+mod)%mod;
	int res=lim?n[x]:9,cnt=0;
	for(int i=0;i<=res;i++){
		if(lead && !i) cnt+=(dfs(x-1,(rest*10+i)%m,1,lim && i==res,temp)%mod+mod)%mod;
		else{
			if(temp==0){
				if(i!=d) continue;
				cnt+=(dfs(x-1,(rest*10+i)%m,0,lim && i==res,1)%mod+mod)%mod;
			}
			else{
				if(i==d) continue;
				cnt+=(dfs(x-1,(rest*10+i)%m,0,lim && i==res,0)%mod+mod)%mod;
			}
		}
	}
	if(!lead && !lim) f[x][rest][temp]=(cnt%mod+mod)%mod;
	return (cnt%mod+mod)%mod;
}
signed main(){
	cin>>m>>d>>t>>r;
	if(t[t.size()-1]!='0') t[t.size()-1]--;
	else{
		int temp;
		for(int i=t.size()-1;i>=0;i--){
			if(t[i]!='0'){
				temp=i;
				break;
			}
		}
		t[temp]--;
		for(int i=temp+1;i<t.size();i++){
			t[i]='9';
		}
	}
	for(int i=0;i<t.size();i++){
		if(t[i]!='0') flag=1;
		if(flag){
			string c=" ";
			c[0]=t[i];
			l.append(c);
		}
	}
	if(t[0]=='0' && t.size()==1){
		l.append("0");
	}
	for(int i=l.size()-1;i>=0;i--) n[++tot]=l[i]-'0';
	memset(f,-1,sizeof(f));
	ans1=(dfs(tot,0,1,1,1)%mod+mod)%mod;
	tot=0;
	for(int i=r.size()-1;i>=0;i--) n[++tot]=r[i]-'0';
	//memset(f,-1,sizeof(f));
	ans2=(dfs(tot,0,1,1,1)%mod+mod)%mod;
	cout<<((ans2-ans1)%mod+mod)%mod;
	return 0;
}

麻烦大佬们了。