RT，数位记搜，样例#1输出9

#include<bits/stdc++.h>
#define R register
using namespace std;
long long f[201][201][2];
long long a[201];
int cnt;
long long n,m,d;
string l,r;
long long dfs(int pos, int mod, bool limit, bool zero) {
	if (pos==0) return mod%m==0;
	if (!limit&&f[pos][mod][zero]!=-1) return f[pos][mod][zero];
	int maxn=limit?a[pos]:9;
	long long tmp=0;
	for (int i=0;i<=maxn;i++) {
        if ((cnt-pos+1)%2==0&&i!=d) continue;
        if ((cnt-pos+1)%2==1&&i==d) continue; 
        tmp+=dfs(pos-1,(mod*10+i)%m,limit&&i==maxn,zero&&i==0);
	}
	if (!limit) f[pos][mod][zero]=tmp;
	return tmp;
}
long long solve(string x) {
	memset(f,-1,sizeof(f));
    memset(a,0,sizeof(a));
	cnt=0;
    for (int i=0;i<x.size();i++) {
        a[i+1]=x[i]-'0';
    }
    long long res=0LL;
    cnt=x.size();
	return dfs(x.size(),0,1,1);
}
bool fun(string s) {
    long long sum=0;
    for (int i=0;i<s.size();i++) {
        int x=s[i]-'0';
        if ((i+1)&1) { 
            if (x==d) return 0; 
        }
        else {
             if (x!=d) return 0; 
        }
        sum=(sum*10+x)%m;
    }
    return sum==0;
}
int main() {
    cin >> m >> d >> l >> r;
    cout << solve(r)-solve(l)+fun(l);
	return 0;
}