题意：

求在[a,b]（a,b不含前导0）中的d−magic数中有多少个是m的倍数。

分析：

计数dp

Let’s call a number d-magic if digit d appears in decimal presentation of the number on even positions and nowhere else.

仔细读题并观察例子就可以明确d−magic数从左到右所有偶数位置上都是d，奇数位上不能是d。

求[a,b]，即可转化为求[1,a],[1,b]中的满足条件的数，最后相减，注意判断a是否满足条件。

设dp[i][j][k]表示前缀为i位，余数为j，等于(1)或者小于(0)上限的方案数。容易想到状态转移的过程，注意分填入的数字小于和等于上限对应元素两种情况处理。

代码：

#include<cstdio>

#include<cstring>

const int mod = 1e9+7, maxn = 2005;

int m, d;

int dp[maxn][maxn][2];

char a[maxn], b[maxn];

int num[maxn];

int solve(char* A)

{

    memset(dp, 0, sizeof(dp));

    memset(num, 0, sizeof(num));

    int cnt = strlen(A);

    for(int i = 0; i < cnt; i++){

        num[i+1] = A[i] - '0';

    }

    for(int i = 1; i<=num[1];i++){

        if(i == d)continue;

        if(i < num[1]){

            dp[1][i%m][0]++;

        }else{

            dp[1][i%m][1]++;

        }

    }

    for(int i = 2; i <= cnt; i++){

        for(int j = 0; j < m; j++){

            if(i%2==0){

                dp[i][(j * 10 + d)%m][0] = (dp[i][(j * 10 + d)%m][0] + dp[i - 1][j][0])%mod;

                if(d < num[i])

                    dp[i][(j * 10 + d)%m][0] = ( dp[i][(j * 10 + d)%m][0] + dp[i - 1][j][1])%mod;

                else if(d == num[i])

                    dp[i][(j * 10 + d)%m][1] = ( dp[i][(j * 10 + d)%m][1] + dp[i-1][j][1])%mod;

            }else{

                for(int k = 0; k < 10; k++){

                    if(k == d) continue;

                        dp[i][(j * 10 + k)%m][0] = (dp[i][(j * 10 + k)%m][0] + dp[i - 1][j][0])%mod;

                    if(k < num[i])

                        dp[i][(j * 10 + k)%m][0] = ( dp[i][(j * 10 + k)%m][0] + dp[i - 1][j][1])%mod;

                    else if(k == num[i])

                        dp[i][(j * 10 + k)%m][1] = ( dp[i][(j * 10 + k)%m][1] + dp[i-1][j][1])%mod;

                    }

                }

            }

        }

    return (dp[cnt][0][0] + dp[cnt][0][1])%mod;

}

int is(char* a)

{

    int res = 0;

    for(int i = 0; i < strlen(a); i++){

        int a1 = a[i] - '0';

        if(i%2 == 0){

            if(a1 == d) return 0;

        }

        if(i%2==1){

            if(a1 != d)  return 0;

        }

        res = (res*10 +a1)%m;

    }

    return res == 0;

}

int main (void)

{

    scanf("%d%d",&m,&d);

    scanf("%s%s", a, b);

    printf("%d\n", (solve(b) - solve(a) +is(a)+mod)%mod) ;

    return 0;

}