Submission #65511800

---

Source Code Expand

#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
using namespace std;
typedef long long ll;
const int N=405,mod=998244353;
ll Fact[N];
void pre(){
	Fact[0]=1;
	for(int i=1;i<N;i++)Fact[i]=i*Fact[i-1]%mod;
}
bool subset(vector<int>a,vector<int>b){
	int n=a.size();
	for(int i=0;i<n;i++){
		if(a[i]&&!b[i])return 0;
	}
	return 1;
}
int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	pre();
	int T;
	cin>>T;
	while(T--){
		int n;
		cin>>n;
		vector<vector<int>>a(n,vector<int>(n));
		for(int i=0;i<n;i++){
			for(int j=0;j<n;j++){
				cin>>a[i][j];
			}
		}
		if(a[0]!=vector<int>(n,1)){
			cout<<"0\n";
			continue;
		}
		map<vector<int>,int>id;
		vector<vector<int>>groups,gval;
		for(int i=0;i<n;i++){
			if(!id.count(a[i])){
				id[a[i]]=groups.size();
				groups.push_back({i});
				gval.push_back(a[i]);
			}else groups[id[a[i]]].push_back(i);
		}
		int m=groups.size();
		vector<pair<int,int>>edges;
		vector<int>order(m);
		iota(order.begin(),order.end(),0);
		sort(order.begin(),order.end(),[&](int a,int b){
			return count(gval[a].begin(),gval[a].end(),1)>count(gval[b].begin(),gval[b].end(),1);
		});
		vector<int>parent(m,-2);
		bool bad=0;
		for(int ii=0;ii<m;ii++){
			int i=order[ii];
			int cnt_i=count(gval[i].begin(),gval[i].end(),1);
			if(ii==0){
				if(cnt_i!=n){
					bad=1;
					break;
				}
				parent[i]=-1;
			}else{
				int best=-1,best_size=N+1;
				for(int jj=0;jj<ii;jj++){
					int j=order[jj];
					int cnt_j=count(gval[j].begin(),gval[j].end(),1);
					if(cnt_j<=cnt_i)continue;
					if(subset(gval[i],gval[j])&&cnt_j<best_size){
						best_size=cnt_j;
						best=j;
					}
				}
				if(best==-1){
					bad=1;
					break;
				}
				parent[i]=best;
			}
		}
		if(bad){
			cout<<"0\n";
			continue;
		}
		long long ans=1;
		for(int i=0;i<m;i++){
			int sz=groups[i].size();
			if(parent[i]==-1)ans=ans*Fact[sz-1]%mod;
			else ans=ans*Fact[sz]%mod;
		}
		cout<<ans<<"\n";
	}
	return 0;
}

Submission Info

Judge Result