Dungeon Creation (AOJ 2393)

AOJ Online Judge

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2393

問題

H*Wの盤面に仕切りをしいて迷路を作りたい。ただしある地点から別の地点への行きたかはちょうど一通りなければならい。迷路の作り方は何通りあるか？
1<=H<=500
1<=W<=15

解法

迷路の作り方は全域木の数と一致する。なので行列木定理を使って計算すれば良い。行列のサイズが5000くらいになるが、帯行列になるためガウスの消去法を行なっても伝播するのが30行くらいなので間に合う。