题解：AT_arc197_d 祖孙关系

### 题目描述

给你一个 $N\times N$ 的矩阵 $A$，其中每一项只会是 $0$ 或 $1$。

请找出有多少种不同的 $N$ 个点的树 $G$，使得：

$\forall 1\le i,j\le N,A_{i,j}=1$，当且仅当 $i=j$，或以结点 $1$ 为根时，$i$ 是 $j$ 的祖先或 $j$ 是 $i$ 的祖先。

两棵树不同，当且仅当存在两个结点 $i,j$，在其中一棵树上它们之间有直接连边而在另一棵树上没有。

请输出答案对 $998244353$ 取模后的结果。

### 数据范围

保证 $1\le T\le 10^5,2\le N\le 400,A_{i,j}\in\{0,1\},A_{i,i}=1,A_{i,j}=A_{j,i}$。

保证一个测试点中 $\sum N^2\le 400^2=1.6\times 10^5$。

我们可以记 $s_i$ 为第 $i$ 行的 $0,1$ 情况，我们可以使用 $bitset$ 维护，比如 `bitset<int> s[maxn]` ，其中 $maxn$ 是正方形的边长。考虑如果 $a_{i,j}=1$ 时，要么 $i$ 是 $j$ 的祖先，要么 $j$ 是 $i$ 的祖先，我们知道，如果是一条链，那么 $i$ 能到达的点和 $j$ 能到达的点是一样的。而如果链上有分叉，那么 $j$ 能到达的点 $i$ 一定能到达， $i$ 能到达的点 $j$ 不一定能到达，所以， $i$ 点的到达情况一定包含 $j$ 的到达情况，总结来说：与孩子有关系的节点一定与祖先有关系，但与祖先有关系的节点不一定与孩子有关系。因此可以写出 $s_i|s_j=s_i$ 。但是呢，很容易想到，如果   $a_{i,j}=0$ 的话，那么 $i$ 就不是 $j$ 的祖先，则一定不存在 $s_i|s_j=s_i$ 。还有另一种情况：   $s_i=s_j$ ，此时就是上图的情况， $i$ 和 $j$ 在一条没有分叉的链上，那么，怎样交换 $i$ 和 $j$ 的位置都不会改变情况，假设链上有 $nums$ 个，情况数有$nums!$ 中，其中 $nums!$ 表示 $nums$ 的阶乘。显然，对于 $∀i∈[1,n]$ ，要满足 $a_{i,1}=1,a_{1,i}=1$ ，汇总一下：

> $∀i\in[1,n]a_{i,1}=1,a_{1,i}=1$。
>
>当且仅当 $a_{i,j}=1 $时， $s_i|s_j=s_i$ 或者 $s_i|s_j=s_j$。
>
>当有 $nums$ 个 $s_i$ 相等时，情况数是 $nums$ 的阶乘（相当于 $nums!$）。

OK ，上代码：

```cpp
#include <bits/stdc++.h>
using namespace std;
#define LL long long
const int maxn=405,mod=998244353;
LL fac[maxn];
void solve(){
	int n,a;cin>>n;
	bitset<maxn> s[maxn];
	bool vis[maxn];
	memset(vis,0,sizeof(vis));
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			cin>>a,s[i][j]=a;
	//判断不合法情况
	for(int i=1;i<=n;i++)
		if(!s[i][1] || !s[1][i]){
			cout<<0<<endl;//第一行或第一列有0
			return ;
		}
	for(int i=2;i<=n;i++)
		for(int j=2;j<=n;j++)
			if(((s[i]|s[j])==s[i])||((s[i]|s[j])==s[j])){
				if(!s[i][j]){//i是j的倍数或j是i的倍数但s[i][j]!=1
					cout<<0<<endl;
					return ;
				}
			}else{
				if(s[i][j]){//i不是j的倍数或j不是i的倍数但s[i][j]==1
					cout<<0<<endl;
					return ;
				}
			}
	LL ans=1;
	for(int i=2;i<=n;i++)
		if(!vis[i]){
			int cnt=1;
			for(int j=i+1;j<=n;j++) 
				if(s[i]==s[j]) ++cnt,vis[j]=1;
			ans=ans*fac[cnt]%mod;
		}
	cout<<ans<<endl;
}
int main(){
	int T;
	cin>>T;
	fac[0]=1;
	for(int i=1;i<maxn;i++)
		fac[i]=fac[i-1]*i%mod;
	while(T--) solve();
	return 0;
}
```

正在渲染内容...