問題概要
整数 $n$, $m$, $k$ と，長さ $k + 1$ の整数の組の列 $((x_1, y_1), (x_2, y_2), \dots, (x_{k + 1}, y_{k + 1}))$ が $(x_i, y_i)$ は，サイズ $n\times m$ のグリッドのセルの座標であり，重複は無い．
$(x_i, y_i)$ と $(x_{i + 1}, y_{i + 1})$ の間に1つずつセルを挿入して， 縦横につながった単純パスを作る方法の数 (作れなければ $0$) を mod $10^9 + 7$ で求めよ．
制約
$1 \leq n, m \leq 1000$， $nm \geq 3$，$1 \leq k \leq \lfloor (nm - 1) / 2 \rfloor$
解
略解．click to open
$P_i = (x_i, y_i)$ と書く．$\{|x_i - x_{i + 1}|, |y_i - y_{i + 1}|\}$ は， (1) $\{0, 2\}$ であるか，(2) $\{1, 1\}$ であるか，でなければならない． 間に入れる点は，(1) では1つに決まる．(2) では，2つの点のうちのどちらか．
そこで，これらの候補点全体を頂点とするグラフを考え，(1) では自己ループの辺を置き， (2) では，その2点を結ぶ辺を置く． 「このグラフの各辺にどちらかの向きをつけ，どの点の入次数も1以下にする」方法の数が答となる．
連結成分ごとに求めて掛け合わせれば良い．
- (辺の数) < (頂点の数) の場合: 木であり，各点を根にして，葉の方に向かう向きを付けられるので， 求める数は，頂点数に一致する．
- (辺の数) = (頂点の数) の場合: サイクルが1つだけある．
- (頂点の数) = 1 の場合: 求める数は 1．
- (頂点の数) >= 2 の場合: 求める数は 2．
- (辺の数) > (頂点の数) の場合: 鳩の巣原理で，求める数は 0．