AOJ 0570 - ジグザグ数 (Zig-Zag Numbers)

解法

$B$ 以下のジグザグ数の個数から、 $A-1$ 以下のジグザグ数の個数を引くと答えになるので、あとは $X$ 以下のジグザグ数の個数を求める方法がわかればよいです。
桁が明らかに大きいので桁DPをしていきます。
$dp[i][j][k][l][o]$ について、
$i$ : 今見ている桁の番号
$j$ : $X$ 以下が確定しているかどうか(1,0で管理)
$k$ : 今の桁と1つ前の桁について、ジグザグの増加と減少がどちらか(1,0で管理)
$l$ : 今どの番号を当てはめるか(0 ~ 9)
$o$ : 今の段階でのmod $M$ の値
を考えていきます。
状態数が多い(~~面倒くさい~~)のでざっくりでいきますが、1つ前の遷移と今の遷移を見比べたときに、 $k$ は交互になるように遷移していきます。そして、ジグザグの増加(減少)の条件を満たすように、今見ている桁の数字と1つ前の桁の数字を当てはめていきます。あとは、桁DPおなじみの $X$ 以下かどうかの判定を行いつつ、 $o$ の値をうまく計算しながらDPをしていけばよいです…
のですが、 $p$ 桁の数字 $X$ に対して、 $p$ 桁未満の数字を数え上げるとき、
$0000...$ のように0埋めされている、と考えてしまうと、これはジグザグ数ではなくなってしまいます。ので、 $i$ 桁目の遷移を考えるときに、それより上の桁が0埋めされている数についてあらかじめカウントしてあげる必要があります。
このコーナーケースの処理も書くと、この問題の答えを求めることができます。