ABC357G - Stair-like Grid、LGV公式とLU分解による解法

問題

略解

「通行禁止」を「長さ0のパスと交わるの禁止」と読み替えLGV公式を適用し，「積の行列式＝行列式の積」を利用すべくLU分解する．通行禁止点が規則的に並んでいてくれていれば分解はFPS商で高速に行える．下記の画像も参照．

https://scrapbox.io/files/69d3674c3caed06dfe68fdf9.png

提出

元ポスト