No.012 D

$i$ 番目の人の進み方の組み合わせの数を $S_i$ とすると, $\prod S_i$ が答えである. 以下で $S_i$ を計算する.

$x_i \geq 0,\ y_i \geq 0$ としても一般性を失わない. 以下 $x, y$ とする.

まずは $x, y$ だけ戻らないといけないので, $T \geq x+y$ でなければならない. また偶奇性から $T$ と $x+y$ の偶奇は一致しなければならない.

右へ移動する回数が決まれば左上下に移動する回数は決まるので, 原点への移動の組み合わせ数は,

$$S_i = \sum_{i=0}^{(T-x-y)/2} \frac{T!}{i!(i+x)!((T-2i-x-y)/2)!((T-2i-x-y)/2+y)!}$$

となる. $w = (T-x-y)/2$ とおくと,

$$S_i = \sum_{i=0}^w \frac{(2w+x+y)!}{i!(i+x)!(w-i)!(w-i+y)!}$$

となる. これを変形して,

$$\begin{align} S_i &= {}_{2w+x+y}C_{w+x} \sum_{i=0}^w \frac{(w+x)!(w+y)!}{i!(i+x)!(w-i)!(w-i+y)!} \\ &= {}_{2w+x+y}C_{w+x} \sum_{i=0}^w {}_{w+x}C_{w-i} \cdot {}_{w+y}C_i \end{align}$$

となる. ここで,

$$(1+z)^{w+x} (1+z)^{w+y} = (1+z)^{2w+x+y}$$

を展開して $z^w$ の係数を比較すると,

$$S_i = {}_{T}C_{w+x} \cdot {}_{T}C_w$$

となる.

part1 のテストケースは $modulo$ が素数なので, 階乗とその逆元をあらかじめ計算しておくことで $S_i$ の計算が $O(1)$ でできるので十分間に合う.

part2 以降のテストケースは $S_i$ を都度計算したのでは間に合わない.

そこで, $\prod S_i$ で分母と分子で $1 \dots T$ の数値が何回掛けられているかを求め, 分子で掛けられている回数から分母で掛けられている回数を引いたものを求める. この結果がマイナスになることもありうるので, 上から順に約数で割ってより小さな素因数に分解していく.

何回掛けられているかを求める計算ではいもす法を使って高速化する.