AtCoder ARC #107 : C - Shuffle Permutation

Cはまだ簡単。
https://atcoder.jp/contests/arc107/tasks/arc107_c

問題

N*Nの行列が与えられる。
各要素には、1～N^2が1回ずつ現れる。

正整数Kが与えられるとき、以下を任意回数行えるとする。

• 2つの行をswapする。ただし、2つの行における各列の和はそれぞれK以下であること。
• 2つの列をswapする。ただし、2つの列における各行の和はそれぞれK以下であること。

上記手順により構成できる行列は何通りか。

解法

前者の処理を行っても、以後の後者の処理の可否に影響しないし、その逆も然り。
そこで、Union-Findで互いに交換可能な行の集合と列の集合を連結していこう。
各連結成分の要素数に対し、その階乗を掛け合わせたものが解。

int N,K;
int A[51][51];
const ll mo=998244353;
template<int um> class UF {
	public:
	vector<int> par,rank,cnt;
	UF() {par=rank=vector<int>(um,0); cnt=vector<int>(um,1); for(int i=0;i<um;i++) par[i]=i;}
	void reinit() {int i; FOR(i,um) rank[i]=0,cnt[i]=1,par[i]=i;}
	int operator[](int x) {return (par[x]==x)?(x):(par[x] = operator[](par[x]));}
	int count(int x) { return cnt[operator[](x)];}
	int operator()(int x,int y) {
		if((x=operator[](x))==(y=operator[](y))) return x;
		cnt[y]=cnt[x]=cnt[x]+cnt[y];
		if(rank[x]>rank[y]) return par[x]=y;
		rank[x]+=rank[x]==rank[y]; return par[y]=x;
	}
};

UF<51> UFR,UFC;
ll fact[55];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>K;
	FOR(y,N) FOR(x,N) cin>>A[y][x];
	
	fact[0]=1;
	for(i=1;i<=50;i++) fact[i]=fact[i-1]*i%mo;
	
	int y1,y2,x1,x2;
	FOR(y2,N) FOR(y1,y2) {
		int ok=1;
		FOR(x,N) if(A[y1][x]+A[y2][x]>K) ok=0;
		if(ok) UFR(y1,y2);
	}
	FOR(x2,N) FOR(x1,x2) {
		int ok=1;
		FOR(y,N) if(A[y][x1]+A[y][x2]>K) ok=0;
		if(ok) UFC(x1,x2);
	}
	
	ll ret=1;
	FOR(i,N) {
		if(UFR[i]==i) ret=ret*fact[UFR.count(i)]%mo;
		if(UFC[i]==i) ret=ret*fact[UFC.count(i)]%mo;
	}
	cout<<ret<<endl;
}

まとめ

えらくARC多いな。