No.612

$T$ 回歩いたときに $d \leq ax+by+cz \leq e$ となる組み合わせの数を求める問題である.

これを

1回歩くごとに $\pm a, \pm b, \pm c$ の点数が入る. 点数の合計 $S$ が $d \leq S \leq e$ となる組み合わせの数を求めよ.

と読み替える. これで DP の問題になる.

$i$ 回歩いたときに合計が $j$ 点になる組み合わせの数を $C(i, j)$ とすると,

$$C(i, j) = C(i-1, j \pm a) + C(i-1, j \pm b) + C(i-1, j \pm c)$$

となる.