Language: C++

#include<bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;++i)
#define FOR(i,a,b) for(int i=a;i<=b;++i)
#define LL long long
using namespace std;
static const LL INF = 1LL<<61LL;
static const int MOD = 10000;
char c[]={'0','1','2','3','4','5','6','7','8','9'};
typedef pair<LL,LL> PLL;

string str1,str2;
int M;
int sum;
LL mem1[501][10][2][501];
LL mem2[501][10][2][501][3];
LL mem2[501][10][2][501][3];


int cal1(int n,int p,int pp,int mod,string s){
    int res=0;
    if(mem1[n][p][pp][mod]!=0){
        return mem1[n][p][pp][mod];
    }
    if(n==str2.size()-2){
        return 0;
    }
    else if(n==0){
        rep(i,10){
            int temp=mod*10;
            temp+=i;
            if(i>p||i<p){
                int a;
                if(i<p)a=1;
                else if(i>p)a=0;
                if(!(temp%M)&&n+2>str1.size()){
                    sum++;
                    res+=cal1(n+1,i,a,0,s+c[i])+1;
                }
                else res+=cal1(n+1,i,a,temp%M,s+c[i]);
            }
        }
    }
    else {
        rep(i,10){
            int temp=mod*10;
            temp+=i;
            if(pp&&p<i){
                if(!(temp%M)&&n+1>str1.size()-1){
                    sum++;
                    res+=cal1(n+1,i,0,0,s+c[i])+1;
                }
                else res+=cal1(n+1,i,0,temp%M,s+c[i]);
            }
            else if(!(pp)&&p>i){
                if(!(temp%M)&&n+1>str1.size()-1){
                    sum++;
                    res+=cal1(n+1,i,1,0,s+c[i])+1;
                }
                else res+=cal1(n+1,i,1,temp%M,s+c[i]);
            }
        }
    }
    return mem1[n][p][pp][mod]=res%MOD;
}

int cal2(int n,int p,int pp,int mod,int f,string s){
    int res=0;
    if(mem2[n][p][pp][mod][f]!=0)return mem2[n][p][pp][mod][f];
    if(n==str1.size()-1&&mod==0){
        //if(s[0]=='9')cout<<s<<endl;
        return 1;
    }
    else if(n==str1.size()-1) return 0;
    rep(i,10){
        int b=f;
        if(b==1){
            if(str1[n+1]-'0'<i){
                b=0;
            }
            if(str1[n+1]-'0'==i){
                b=1;
            }
            if(str1[n+1]-'0'>i){
                continue;
            }
        }
        int temp=mod*10;
        temp+=i;

        if(n==0){
            if(i>p||i<p){
                int a;
                if(i<p)a=1;
                else if(i>p)a=0;
                if(!(temp%M)&&n+2>str1.size()){
                    res+=cal2(n+1,i,a,0,b,s+c[i]);
                }
                else res+=cal2(n+1,i,a,temp%M,b,s+c[i]);
            }
        }
        else{
            if((pp&&p<i)||(n==0&&p<i)){
                res+=cal2(n+1,i,0,temp%M,b,s+c[i]);
            }
            else if((!(pp)&&p>i)||(n==0&&p>i)){
                res+=cal2(n+1,i,1,temp%M,b,s+c[i]);
            }
        }
    }
    return mem2[n][p][pp][mod][f]=res%MOD;
}

int cal3(int n,int p,int pp,int mod,int f,string s){
    int res=0;
    if(mem3[n][p][pp][mod][f]!=0)return mem3[n][p][pp][mod][f];
    if(n==str2.size()-1&&mod==0){
        //cout<<s<<endl;
        //cout<<s<<endl;
        return 1;
    }
    else if(n==str2.size()-1) return 0;
    rep(i,10){
        int b=f;
        if(b==1){
            if(str2[n+1]-'0'>i){
                b=0;
            }
            if(str2[n+1]-'0'==i){
                b=1;
            }
            if(str2[n+1]-'0'<i){
                continue;
            }
        }
        int temp=mod*10;
        temp+=i;
        if(n==0){
            if(i>p||i<p){
                int a=(i<p);
                if(!(temp%M)&&n+2>str1.size()){
                    res+=cal3(n+1,i,a,0,b,s+c[i]);
                }
                else res+=cal3(n+1,i,a,temp%M,b,s+c[i]);
            }
        }
        else{
            if((pp&&p<i)||(n==0&&p<i)){
                res+=cal3(n+1,i,0,temp%M,b,s+c[i]);
            }
            else if((!(pp)&&p>i)||(n==0&&p>i)){
                res+=cal3(n+1,i,1,temp%M,b,s+c[i]);
            }
        }
    }
    return mem3[n][p][pp][mod][f]=res%MOD;
}

int cal4(int n,int p,int pp,int mod,int f,string s){
    int res=0;
    //cout<<s<<" "<<f<<" "<<mod<<endl;
    if(mem2[n][p][pp][mod][f]!=0)return mem2[n][p][pp][mod][f];
    if(n==str2.size()-1&&mod==0){
        return 1;
    }
    else if(n==str2.size()-1) return 0;
    rep(i,10){
        int b=f;
        if(b==2){
            //cout<<s+c[i]<<endl;
            if(str2[n+1]-'0'>i){
                b=0;
            }
            if(str2[n+1]-'0'==i){
                b=2;
            }
            if(str2[n+1]-'0'<i){
                continue;
            }
        }
        else if(b==1){
            //cout<<s+c[i]<<endl;
            if(str1[n+1]-'0'<i){
                b=0;
            }
            if(str1[n+1]-'0'==i){
                b=1;
            }
            if(str1[n+1]-'0'>i){
                continue;
            }
        }
        int temp=mod*10;
        temp+=i;
        if(n==0){
            if(i>p||i<p){
                int a=(i>p);
                //cout<<a<<endl;
                if(!(temp%M)&&n+2>str1.size()){
                    res+=cal4(n+1,i,a,0,b,s+c[i]);
                }
                else res+=cal4(n+1,i,a,temp%M,b,s+c[i]);
            }
        }
        else{
            if((!(pp)&&p<i)||(n==0&&p<i)){
                res+=cal4(n+1,i,1,temp%M,b,s+c[i]);
            }
            else if((pp&&p>i)||(n==0&&p>i)){
                res+=cal4(n+1,i,0,temp%M,b,s+c[i]);
            }
        }
    }
    return mem2[n][p][pp][mod][f]=res%MOD;
}


int main(){
    LL ans=0;
    cin>>str1>>str2;
    cin>>M;
    FOR(i,1,9){
        string s;
        if(str1.size()==str2.size()){
            if(str1[0]-'0'<i&&str2[0]-'0'>i)ans+=cal4(0,i,0,i%M,0,s+c[i]);
            else if(str1[0]-'0'==i)ans+=cal4(0,i,0,i%M,1,s+c[i]);
            else if(str2[0]-'0'==i)ans+=cal4(0,i,0,i%M,2,s+c[i]);
            continue;
        }
        ans+=cal1(0,i,0,i%M,s+c[i]);
        if(str2[0]-'0'>=i&&i!=0){
            if(str2[0]-'0'>i)ans+=cal3(0,i,0,i%M,0,s+c[i]);
            else ans+=cal3(0,i,0,i%M,1,s+c[i]);
        }
        if(str1[0]-'0'<=i&&i!=0){
                if(str1[0]-'0'<i)ans+=cal2(0,i,0,i%M,0,s+c[i]);
                else ans+=cal2(0,i,0,i%M,1,s+c[i]);
        }
    }
    cout<<ans%MOD<<endl;
}

Compiler output:
a.cc:16:4: error: redefinition of 'long long int mem2 [501][10][2][501][3]'
   16 | LL mem2[501][10][2][501][3];
      |    ^~~~
a.cc:15:4: note: 'long long int mem2 [501][10][2][501][3]' previously declared here
   15 | LL mem2[501][10][2][501][3];
      |    ^~~~
a.cc: In function 'int cal3(int, int, int, int, int, std::string)':
a.cc:115:8: error: 'mem3' was not declared in this scope; did you mean 'mem2'?
  115 |     if(mem3[n][p][pp][mod][f]!=0)return mem3[n][p][pp][mod][f];
      |        ^~~~
      |        mem2
a.cc:155:12: error: 'mem3' was not declared in this scope; did you mean 'mem2'?
  155 |     return mem3[n][p][pp][mod][f]=res%MOD;
      |            ^~~~
      |            mem2