No.035 D

$i$ 番目と $i+1$ 番目のチェックポイントの間のコースの数は, $p^{\prime}_i = p_{i+1} - p_i, q^{\prime}_i = q_{i+1} - q_i$ とすると,

$$\frac{(p^{\prime}_i+q^{\prime}_i)!}{p^{\prime}_i! q^{\prime}_i!}$$

となる.

これを総乗を計算するセグメントツリーで管理するのが基本方針である.

しかし, このままでは桁数が大きくなりすぎるので対応できない.

そこで, 対数で管理することにする. 対数ならば相乗ではなく総和で管理すればよく, 経路数が多い方は少ない方の2倍以上という制約から誤差もごまかせる範囲である.

なお, 階乗(の対数)はあらかじめ計算しておく.