AtCoder Regular Contest 107, C : Shuffle Permutation

問題文

　https://atcoder.jp/contests/arc107/tasks/arc107_c

問題概要

　$N \times N$ 行列 $a$ と整数 $K$ が与えられる．$a$ の要素は $1$ ～ $N^2$ の整数をちょうど一つずつ含む．ここで，次の 2 種類の操作を好きな順序で好きな回数行うことができる．

• 任意の $i$ ($1 \leq i \leq N$) について $a_{ i, x } + a_{ i, y } \leq K$ であるような $x, y$ について，$x$ 行と $y$ 行を交換する
• 任意の $i$ ($1 \leq i \leq N$) について $a_{ x, i } + a_{ y, i } \leq K$ であるような $x, y$ について，$x$ 列と $y$ 列を交換する

　操作後に得られる行列の種類は何種類あるか？　$\pmod{ 998{,}244{,}353 }$ で求めよ．

制約

• $1 \leq N \leq 50$
• $1 \leq K \leq 2 \times N^2$

解法

　行に対して操作をしたとき，各要素がある列は変化せず，同様に，列に操作したときは各要素がある行は変化しません．よって，行の対あるいは列の対について，交換可能性的なものは操作によって変化しません．
　また，互いに交換可能な行同士・列同士の間では任意の順列を作れます．なので答えとしては，この，順列を好きに作れる塊ごとに作れる順列の総数をかけたものになります．よって，素集合データ構造などを使って塊のサイズを求めたあと，塊のサイズの階乗をとってかけ合わせたものが答えです．

コード

constexpr int MOD = 998244353;

class DisjointSetForest;
// DisjointSetForest( N )
// find( x )
// same( x, y )
// unite( x, y )
// groups()
// groupSize( x )

LL perm( const int N )
{
	return N == 0 ? 1 : N * perm( N - 1 ) % MOD;
}

int main()
{
	IN( int, N, K );
	VVI A( N, VI( N ) );
	cin >> A;

	DisjointSetForest dsf( 2 * N );

	REP( x, N )
	{
		REP( y, x + 1, N )
		{
			{
				bool ok = true;
				REP( i, N )
				{
					ok &= A[x][i] + A[y][i] <= K;
				}
				if ( ok )
				{
					dsf.unite( x, y );
				}
			}
			{
				bool ok = true;
				REP( i, N )
				{
					ok &= A[i][x] + A[i][y] <= K;
				}
				if ( ok )
				{
					dsf.unite( N + x, N + y );
				}
			}
		}
	}

	map< int, int > ps;
	REP( i, 2 * N )
	{
		ps[ dsf.find( i ) ] = dsf.groupSize( i );
	}

	LL res = 1;
	FOR( p, ps )
	{
		( res *= perm( p.snd ) ) %= MOD;
	}
	cout << res << endl;

	return 0;
}