ARC107 C - Shuffle Permutation

概要

与えられた行列を条件に合うように動かすとき、最終的に何通りの行列が得られるか

ポイント

この問題におけるポイントは、
・行の操作、列の操作はそれぞれ独立で、どんなに操作しても位置関係は変わらない
ということ。
しっくり来なければ、行列のある一行(あるいは一列)に印をつけ、何回も操作を行ってみてください。どんなに操作しても印が一列になっているはずです。

例(5*5の配列)

行1と行3を入れ替え

列2と4を入れ替え

解法

このポイントがわかれば、あとは楽です
方針としては、
①どの行同士が交換可能かをグラフとして保存
②できたグラフについてのすべての連結成分について、その成分の要素数の階乗をかけ合わせる(ある連結成分iの要素数がS[i]で連結成分がm個のとき、S[0]!*S[1}*...*S[m])
③①、②を列に対しても同様に行い、行での結果*列での結果が答え

(ぼくはUnionFindができないので、こうやってグラフでやっています)

コード

① どの行同士が交換可能かをグラフとして保存

	vector<vector<ll>>able_swap_num_i(n,vector<ll>());//グラフ定義
 
	rep(i,n){ //見る行
		rep(x,n){ //比較対象の行
			if(x==i) continue; //比較対象が自分の場合はスルー
			bool ok=true; //その行と交換可能か
			rep(y,n){//列ごとに見る
				if(a[i][y]+a[x][y]>k){ 
                                        //条件を満たしていないので、その行とは交換できない
					ok=false;
					break;
				}
			}
			if(ok){
                                //有向グラフっぽいけど、この逆の場合(iとxが逆)もあるので無向グラフ
				able_swap_num_i[i].push_back(x);
			}
		}
	}

②できたグラフについてのすべての連結成分について、その成分の要素数の階乗をかけ合わせる

グラフ走査には、幅優先探索を使います

	vector<ll>dist(n,-1); //本来は距離用だけど、今回は訪問済みかの印
	ll swaps_i=1; //行について考えたときの答え
 
	rep(i,n){
                //訪問済みならスルー
		if(dist[i]!=-1) continue;
 
                //BFSここから
		queue<ll>que;
		que.push(i);
		ll members=1; //連結成分内の要素数
		dist[i]=0;
		while(!que.empty()){
			ll now=que.front();
			que.pop();
			for(ll next:able_swap_num_i[now]){
				if(dist[next]!=-1)continue;
				que.push(next);
				dist[next]=dist[now]+1;
				++members;
			}
		}
		
                //階乗
		rep(i,members){
			swaps_i*=(i+1)%mod;
			swaps_i%=mod;
		}
	}

列についても同じように。

ソースコード全体
半分くらいまでは関係ないです