CFR Educational 8 D. Magic Numbers ( 桁DP )

Problem - D - Codeforces
Just make clear how one state can transfer to another, it will be easy.

#include <bits/stdc++.h>
using namespace std;
const int MAXM = 2000 + 3;
const int MAXP = 2000 + 3;
const int MOD = 1e9 + 7;
#define rep( i, a ) for( int i = 0; i < (int)( a ); ++i )

int n;
int m, d;
char a[ MAXP ], b[ MAXP ];

int dp[ MAXP ][ 2 ][ MAXM ]; // pos / less / mod

int count( char *s, bool inc ){
    memset( dp, 0, sizeof(dp) );
    dp[ 0 ][ 0 ][ 0 ] = 1;
    rep( i, n ) rep( j, 2 ) rep( k, m ){
        int lim = j ? 9 : s[ i ] - '0';
        rep( l, lim + 1 ){
            if( ( i & 1 ) && l != d ) continue;
            if( !( i & 1 ) && l == d ) continue;
            ( dp[ i + 1 ][ j || l < lim ][ ( k * 10 + l ) % m ]
            += dp[ i ][ j ][ k ] ) %= MOD;
        }
    }
    int ans = 0;
    rep( j, 2 ){
        if( !j && !inc ) continue;
        ( ans += dp[ n ][ j ][ 0 ] ) %= MOD;
    }
    return ans;
}

void solve(){
    n = strlen( a );
    int acnt = count( a, false );
    int bcnt = count( b, true );
    int ans = bcnt - acnt;
    ans %= MOD; ans += MOD; ans %= MOD;
    printf("%d\n", ans);
}

int main(){
    scanf("%d%d", &m, &d);
    scanf("%s%s", a, b);
    solve();
    return 0;
}