AOJ Zig-Zag Numbers ( 桁DP )

Zig-Zag Numbers | Aizu Online Judge
一桁の場合はなんだとあれ必ずZig-Zag数という性質上、「今有効一桁だけ」、「今全部０」、「それ以外の状態」と三つに分けてそれぞれ別に判断しなけらばならない。桁dpをする時はleading zeroが方法数にどんな影響を与えるのかを予めよく考えよう。

#include <bits/stdc++.h>
using namespace std;
const int MAXM = 500;
const int MAXLEN = 500 + 5;
const int MOD = 1e4;
#define rep( i, a ) for(int i = 0; i < (int)( a ); ++i)

string a, b;
int m;

// pos, less, 0s leading / 1dig leading / decreasing / increasing, last dig, % m
int way[MAXLEN][2][4][10][MAXM];
int dp(const string &s, bool inc){ // inc: <= s or < s
    memset( way, 0, sizeof(way) );
    way[0][0][0][0][0] = 1;
    rep( i, s.size() ) rep( j, 2 ) rep( k, 4 ) rep( l, 10 ) rep( p, m ){
        int lim = j ? 9 : s[ i ] - '0';
        rep( d, lim + 1 ){
            if( k == 0 )
                ( way[i + 1][j || d < lim][d != 0][d][d % m]
                  += way[i][j][k][l][p] ) %= MOD;
            else if( k == 1 && d != l )
                ( way[i + 1][j || d < lim][d < l ? 2 : 3][d][( p * 10 + d ) % m]
                  += way[i][j][k][l][p] ) %= MOD;
            else if( k == 2 && d > l )
                ( way[i + 1][j || d < lim][3][d][( p * 10 + d ) % m]
                  += way[i][j][k][l][p] ) %= MOD;
            else if( k == 3 && d < l )
                ( way[i + 1][j || d < lim][2][d][( p * 10 + d ) % m]
                  += way[i][j][k][l][p] ) %= MOD;
        }
    }
    int res = 0;
    rep( j, 2 ) rep( k, 4 ) rep( l, 10 ){
        if( !inc && !j ) continue; // -> s, if not included, discard it
        ( res += way[ s.size() ][j][k][l][0] ) %= MOD;
    }
    return res;
}

void solve(){
    int ans = dp( b, true ) - dp( a, false ); // way( [ 0, b ] ) - way( [ 0, a ) ) = way( [ a, b ] )
    ans %= MOD; ans += MOD; ans %= MOD;
    cout << ans << endl;
}

int main(){
    ios::sync_with_stdio(false);
    cin >> a >> b >> m;
    solve();
    return 0;
}