#include <bits/stdc++.h>
using namespace std;
#define fast ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define ll long long
#define all(v) v.begin(),v.end()
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define pi pair<int,int>
#define REP(i,n) for(int i=0;i<n;i++)
const int N = 2e5+10;
const ll mod = 1e9+7;
int m,d;
string a,b;
int dp[2001][2][2001];
int solve(int pos,int f1,int rem,string x){
if(pos==(int)a.length()){
if((rem%m)==0)
return 1;
return 0;
}
if(dp[pos][f1][rem]!=-1)
return dp[pos][f1][rem];
int ulmt;
if(f1)
ulmt=9;
else
ulmt=(x[pos]-'0');
int ans=0;
for(int i=0;i<=ulmt;++i){
int nf1,nrem,nis;
if(f1==0 and i==ulmt)
nf1=0;
else if(f1==0 and i<ulmt)
nf1=1;
else
nf1=1;
nrem=(10*rem+i)%m;
if(pos%2==1 and i==d){
ans+=solve(pos+1,nf1,nrem,x);
if(ans>=mod)
ans-=mod;
break;
}
else if(pos%2==0 and i!=d){
ans+=solve(pos+1,nf1,nrem,x);
if(ans>=mod)
ans-=mod;
}
}
return dp[pos][f1][rem] = ans;
}
int main(){
fast;
cin >> m >> d >> a >> b;
memset(dp,-1,sizeof(dp));
int a1 = solve(0,0,0,b);
memset(dp,-1,sizeof(dp));
int a2 = solve(0,0,0,a);
bool ok=true;
int rem=0;
for(int i=0;i<(int)a.length();++i){
if(i%2==1 and (a[i]-'0')!=d){
ok=false;
}
if(i%2==0 and (a[i]-'0')==d){
ok=false;
}
rem=(10*rem+(a[i]-'0'))%m;
}
int ans;
if(ok and rem==0)
ans=(a1-a2+1+mod)%mod;
else
ans=(a1-a2+mod)%mod;
cout<<ans<<"\n";
}
state of your dp is kind of $$$O(n^2)$$$ and for each state you are running a loop which is $$$O(n)$$$ and hence total time complexity would be $$$O(n^3)$$$ which will result in TLE. Editorial solution is $$$O(n^2)$$$. So you might optimize your recursive dp or it might not be possible to do so in recursive. Also using recursive/iterative depends on the problem and the observations you have made.
You're passing string
xby value, it creates a copy everytimethis is definitely it.
Also I read somewhere that the order in which matrices are multiplied matters a lot when accessing memory, so how to decide which dimensions to put first in dp ?
Usually, smaller dimensions should be kept first. Ref