Kazun の競プロ記録

競技プログラミングに関する様々な話題を執筆します.

AtCoder Beginner Contest 232 E 問題 Rook Path

AtCoder ABC ABC232 E問題 500 pts

問題

提出解答

問題の概要

$H$ 行 $W$ マスからなるチェス盤とルークがある. このルークは最初, マス $(x_1, y_1)$ にある. ちょうど $K$ 回移動の後, このルークが $(x_2, y_2)$ にあるような移動の方法の数を求めよ. ただし, $1$ 回の移動では必ず違うマスに移動しなければならない.

制約

$2 \leq H,W \leq 10^9$
$1 \leq K \leq 10^6$
$1 \leq x_1, x_2 \leq H$
$1 \leq y_1, y_2 \leq W$

解法

縦と横の移動が独立なので, 以下のようにして求めることができる:

長さの列のうち, 以下の条件を全て満たすような列の数をとする.
- 各項は $1$ 以上 $L$ 以下の整数
- $T_0=p, T_a=q$
- $i=1,2, \dots, a$ に対して, $T_{i-1} \neq T_i$

このとき, 求めるべき答えは,

$\displaystyle \sum_{a=0}^K \dbinom{K}{a} E(H,a; x_1, x_2) E(L, K-a; y_1, y_2)$

である.

以下, $E(L,a;z,z')$ を求めることにする. $a=0$ のときは, $E(L,0;z,z')=[z=z'$ ] である. $a \gt 0$ のとき,

$\displaystyle E(L,a;z,z')=\sum_{\substack{1 \leq w \leq K \\ w \neq z'}}E(L,a-1;z,w)$

である. ここで, 対称性から, $1 \leq w,w' \leq L$ で, $w,w' \neq z$ ならば, $E(L,a;z,w)=E(L,a;z,w')$ である.

よって, $1 \leq w \leq L$ を $z \neq w$ となるようにとり, 固定する. そして, $p_a:=E(L,a;z,z), q_a:=E(L,a;z,w)$ とする. すると,

$p_a=(L-1) q_{a-1}, \quad q_a=p_{a-1}+(L-2)q_{a-1}$

が成り立ち, $p_0=1, q_0=0$ の初期条件から, $p_K, q_K$ を $O(K)$ で求めることができる.

以上から, 縦横それぞれに適切に $p_a$ か $q_a$ を選ぶことで, 求めるべき答えを $O(K)$ で求めることができた.