[AtCoder] ARC 107 C – Shuffle Permutation

問題

方針

例えば、\( 1 \) 行目と \( 2 \) 行目が交換可能であり、\( 1 \) 行目と \( 3 \) 行目が交換可能であるとき、各 \( 1, 2, 3 \) 行の順番を任意に並び替えることができます。したがって列に対しても同じことが言えるので、交換可能な行と列のグループを Union-Find で管理します。また、行を入れ替えたとき列の情報は変わらないので、独立して行と列の操作を行うことができます。

ある行の交換可能なグループのサイズを \( n \) とすると、このグループの操作によって、\( n! \) 通りのパターンが考えられます。なので、全ての行と列の交換可能なグループのサイズの階乗の積が答えとなります。

コード