提出 #65508607

---

ソースコード 拡げる

#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <string>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <array>
#include <iomanip>
#include <utility>
#include <tuple>
#include <functional>
#include <bitset>
#include <cassert>
#include <complex>
#include <stdio.h>
#include <time.h>
#include <numeric>
#include <random>
#include <unordered_set>
#include <unordered_map>
#define all(a) (a).begin(), (a).end()
#define rep(i, n) for (ll i = 0; i < (n); i++)
#define req(i, a, b) for (ll i = (a); i < (b); i++)
#define pb push_back
#define debug(x) cerr << __LINE__ << ' ' << #x << ':' << (x) << '\n'
#define debug2(x, y) cerr << __LINE__ << ' ' << #x << ':' << (x) << ',' << #y << ':' << (y) << '\n'
#define debug3(x, y, z) cerr << __LINE__ << ' ' << #x << ':' << (x) << ',' << #y << ':' << (y) << ',' << #z << ':' << (z) << '\n'
using namespace std;
typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef long double ld;
template<class T> using P = pair<T, T>;
template<class T> using pri_l = priority_queue<T>;
template<class T> using pri_s = priority_queue<T, vector<T>, greater<T>>;
constexpr int inf = 1000000010;
constexpr int inf2 = 2000000010;
constexpr ll INF = 1000000000000000010;
constexpr ll INF4 = 4000000000000000010;
constexpr int mod1e9 = 1000000007;
constexpr int mod998 = 998244353;
constexpr ld eps = 1e-12;
constexpr ld pi = 3.141592653589793238;
constexpr ll ten(int n) { return n ? 10 * ten(n - 1) : 1; };
int dx[] = { 1,0,-1,0,1,1,-1,-1,0 }; int dy[] = { 0,1,0,-1,1,-1,1,-1,0 };
ll mul(ll a, ll b) { return (b != 0 && a > INF / b ? INF : a * b); }
void fail() { cout << "-1\n"; exit(0); } void no() { cout << "No\n"; exit(0); }
template<class T> void er(T a) { cout << a << '\n'; exit(0); }
template<class T, class U> inline bool chmax(T& a, const U& b) { if (a < b) { a = b; return true; } return false; }
template<class T, class U> inline bool chmin(T& a, const U& b) { if (a > b) { a = b; return true; } return false; }
template<class T> istream& operator >>(istream& s, vector<T>& v) { for (auto& e : v) s >> e; return s; }
template<class T> ostream& operator <<(ostream& s, const vector<T>& v) { for (auto& e : v) s << e << ' '; return s; }
template<class T, class U> ostream& operator << (ostream& s, const pair<T, U>& p) { s << p.first << ' ' << p.second; return s; }

struct fastio {
	fastio() {
		cin.tie(0); cout.tie(0);
		ios::sync_with_stdio(false);
		cout << fixed << setprecision(20);
		cerr << fixed << setprecision(20);
	}
}fastio_;

namespace rdv {
	random_device seed_gen;
	mt19937_64 engine(seed_gen());
	ll rnum(ll r) { return engine() % r; } // [0, r)
	ll rnum(ll l, ll r) { return rnum(r - l) + l; } // [l, r)
	ll rng(ll l, ll r) { return rnum(l, r + 1); } // [l, r]
	double rng01() { return engine() * pow(2, -64); }
	template<class T> void shuf(vector<T>& v) { shuffle(all(v), engine); }
	void shuf(string& s) { shuffle(all(s), engine); }
}

using namespace rdv;

template<class T> vector<int> compress(vector<T> v) {
	int n = v.size();
	vector<T> tmp = v;
	sort(tmp.begin(), tmp.end());
	tmp.erase(unique(tmp.begin(), tmp.end()), tmp.end());
	vector<int> res(n);
	for (int i = 0; i < n; i++) res[i] = lower_bound(tmp.begin(), tmp.end(), v[i]) - tmp.begin();
	return res;
}

#include <atcoder/all>
using namespace atcoder;

constexpr ll mod = mod998;
using mint = static_modint<mod>;

istream& operator >>(istream& s, mint& m) { ll y; s >> y; m = y; return s; }
ostream& operator <<(ostream& s, mint& m) { return s << m.val(); }
ostream& operator <<(ostream& s, const vector<mint>& v) { for (auto& e : v) s << e.val() << ' '; return s; }

vector<mint> fac, inv, facinv;

void modcalc(int n) {
	fac.resize(n); inv.resize(n); facinv.resize(n);
	fac[0] = 1; fac[1] = 1; inv[1] = 1;
	facinv[0] = 1; facinv[1] = 1;
	for (ll i = 2; i < n; i++) {
		fac[i] = fac[i - 1] * i;
		inv[i] = -inv[mod % i] * (mod / i);
		facinv[i] = facinv[i - 1] * inv[i];
	}
}

/*mint comb(ll n, ll k) {
	if (n < 0 || k < 0 || n < k) return 0;
	return fac[n] * facinv[k] * facinv[n - k];
}

mint perm(ll n, ll k) {
	if (n < 0 || k < 0 || n < k) return 0;
	return fac[n] * facinv[n - k];
}

mint hom(ll n, ll k) {
	if (n < 0 || k < 0 || n == 0 && k > 0) return 0;
	if (n == 0 && k == 0) return 1;
	return fac[n + k - 1] * facinv[k] * facinv[n - 1];
}*/

mint comb(ll n, ll r) {
	if (n < 0 or r < 0 or n < r) return 0;
	r = min(r, n - r);
	mint ans = 1;
	for (int i = 1; i <= r; i++) {
		ans *= n + 1 - i;
		ans *= inv[i];
	}
	return ans;
}

mint hom(ll n, ll r) {
	if (n < 0 or r < 0 or (n == 0 && r > 0)) return 0;
	if (n == 0 && r == 0) return 1;
	return comb(n + r - 1, r);
}

int op(int a, int b) { return a + b; }
int e() { return 0; }

int target;
bool f(int a) { return a < target; }

class Tree {
public:
	vector<vector<int>> graph;
	vector<int> par, tour, in, out, dep;
	vector<P<int>> edge;
	vector<vector<int>> anc;
	void dfs(int n, int p, int d) {
		tour.push_back(n);
		par[n] = p; dep[n] = d;
		for (int i : graph[n]) {
			if (i == p) continue;
			dfs(i, n, d + 1);
			tour.push_back(n);
		}
	}
	Tree(int n) {
		graph.resize(n);
		par.resize(n); dep.resize(n);
		in.resize(n); out.resize(n);
	}
	Tree(vector<vector<int>> graph_, int root = 0) {
		graph = graph_;
		int n = graph.size();
		par.resize(n); dep.resize(n);
		dfs(root, -1, 0);
		int sz = tour.size();
		in.resize(n); out.resize(n);
		rep(i, n) in[i] = -1;
		rep(i, sz) {
			if (in[tour[i]] == -1) in[tour[i]] = i;
			out[tour[i]] = i;
		}
	}
	void input_and_init(int root = 0) {
		int n = graph.size();
		rep(_, n - 1) {
			int u, v;
			cin >> u >> v;
			u--; v--;
			graph[u].push_back(v);
			graph[v].push_back(u);
		}
		dfs(root, -1, 0);
		int sz = tour.size();
		rep(i, n) in[i] = -1;
		rep(i, sz) {
			if (in[tour[i]] == -1) in[tour[i]] = i;
			out[tour[i]] = i;
		}
	}
	bool subtree(int u, int v) { return in[u] <= in[v] && out[v] <= out[u]; }
	void build_edge() {
		// 辺の並びを作る
		if (!edge.empty()) return;
		int sz = tour.size();
		edge.resize(sz - 1);
		rep(i, sz - 1) {
			int u = tour[i], v = tour[i + 1];
			if (dep[u] < dep[v]) edge[i] = { v, 1 };
			else edge[i] = { u, -1 };
		}
	}
	P<int> get_interval(int u, int v) {
		// 頂点だと [l, r], 辺だと [l, r) に対応
		int l, r;
		if (out[u] < in[v]) l = out[u], r = in[v];
		else if (out[v] < in[u]) l = out[v], r = in[u];
		else if (subtree(u, v)) l = in[u], r = in[v];
		else l = in[v], r = in[u];
		return make_pair(l, r);
	}
	void build_lca() {
		int n = graph.size();
		int maxd = *max_element(all(dep));
		int sz = 1, tmp = 1;
		while (tmp < maxd) {
			sz++;
			tmp *= 2;
		}
		anc.resize(sz);
		rep(i, sz) anc[i].resize(n + 1);
		rep(j, n) anc[0][j] = par[j] == -1 ? n : par[j];
		anc[0][n] = n;
		rep(i, sz - 1) rep(j, n + 1) anc[i + 1][j] = anc[i][anc[i][j]];
	}
	int get_ancestor(int v, int k) {
		assert(anc.size() != 0);
		int sz = anc.size();
		for (int i = sz - 1; i >= 0; i--) if (k >> i & 1) v = anc[i][v];
		return v;
	}
	int lca(int u, int v) {
		assert(anc.size() != 0);
		if (dep[u] > dep[v]) swap(u, v);
		int d = dep[v] - dep[u];
		int sz = anc.size();
		rep(i, sz) if (d >> i & 1) v = anc[i][v];
		for (int i = sz - 1; i >= 0; i--) {
			if (anc[i][u] != anc[i][v]) {
				u = anc[i][u];
				v = anc[i][v];
			}
		}
		if (u != v) u = par[u];
		return u;
	}
	int jump(int u, int v, int d) {
		// u から v 方向へ d jump, dist(u, v) < d のとき -1
		// ライブラリ整備をサボって log をつけている
		int l = lca(u, v);
		int d0 = dep[u] - dep[l], d1 = dep[v] - dep[l];
		if (d0 + d1 < d) return -1;
		if (d <= d0) return get_ancestor(u, d);
		else return get_ancestor(v, d0 + d1 - d);
	}
	int dist(int u, int v) {
		int l = lca(u, v);
		return dep[u] + dep[v] - 2 * dep[l];
	}
};

int main() {
	modcalc(1000);
	int T;
	cin >> T;
	while (T--) {
		int n;
		cin >> n;
		vector<vector<int>> a(n, vector<int>(n));
		rep(i, n) rep(j, n) cin >> a[i][j];
		vector<int> c(n);
		rep(i, n) c[i] = count(all(a[i]), 1);
		vector<P<int>> p(n);
		rep(i, n) p[i] = { c[i],i };
		sort(all(p), greater<>());
		vector<bool> used(n);
		vector<vector<int>> g(n, vector<int>());

		vector<int> path = { 0 };
		auto dfs = [&](auto dfs, int v) -> void {
			used[v] = true;
			rep(nxt, n) {
				int i = p[nxt].second;
				if (used[i]) continue;
				bool valid = true;
				for (int j : path) if (a[i][j] == 0) valid = false;
				if (valid) {
					g[i].push_back(v);
					g[v].push_back(i);
					path.push_back(i);
					dfs(dfs, i);
					path.pop_back();
				}
			}
		};

		dfs(dfs, 0);
		bool ng = false;
		rep(i, n) if (!used[i]) ng = true;
		if (ng) {
			cout << "0\n";
			continue;
		}
		Tree t(g);
		rep(i, n) rep(j, n) {
			bool f0 = a[i][j];
			bool f1 = t.subtree(i, j) or t.subtree(j, i);
			if (f0 != f1) ng = true;
		}
		if (ng) {
			cout << "0\n";
			continue;
		}
		mint ans = 1;
		vector<vector<int>> d(n, vector<int>());
		rep(i, n) {
			for (int j : g[i]) if (j != t.par[i]) d[i].push_back(j);
		}
		vector<bool> f(n);
		vector<int> ord(n);
		rep(i, n) ord[i] = i;
		sort(all(ord), [&](int i, int j) {return t.dep[i] < t.dep[j]; });
		modcalc(500);
		for (int i : ord) {
			if (f[i] or i == 0) continue;
			f[i] = true;
			int cnt = 1;
			int cur = i;
			while (ssize(d[cur]) == 1) {
				cnt++;
				cur = d[cur][0];
				f[cur] = true;
			}
			ans *= fac[cnt];
		}
		cout << ans << '\n';
	}
}

提出情報

ジャッジ結果