题解：AT_arc197_d [ARC197D] Ancestor Relation

思路

好题要赞，建议评蓝。

题目描述

给你一个 $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$ 取模后的结果。

这题显而易见的位运算。

我们令

N \times N

的矩阵为

A_{i,j}

，则不妨用一个

\text{bitset}

表示每一行中

a_j

的

0

或

1

总体情况。我们令这个

\text{bitset}

为

s_i

。

更具题目定义，我们有若

a_{i,j}=1（i \not = j）

，则

i

和

j

为祖先关系，即要么

i

是

j

的祖先，要么

j

是

i

的祖先。所以

i

和

j

同链。因为题目说

1

为根，则

\forall i \in [1,N]，a_{i,1}=a_{1,i}=1

。可以判掉一部分无解情况。

定义

i

和

j

有关系当且仅当

a_{i,j}=a_{j,i}=1

。

我们有如下结论：

结论

1

：与子树内节点有关系的节点一定与祖先有关系。
结论

2

：与祖先有关系的节点不一定与子树内节点有关系。

证明：

与子树内节点的节点一定在子树内的点到根节点

1

的唯一路径上（唯一链），而祖先一定处于这个位置（祖先的定义），所以结论

1

成立。

同理，我们可以举出“与祖先有关系的节点一定与子树内节点有关系。”的反例。例如，我们设祖先为

k

，若

k

节点分叉，随意选

2

条链即可举出反例。

所以我们有公式，一下钦定

i

处于

j

上面：

若 $a_{i,j}=a_{j,i}=1$ ，则 $s_i$ 一定包含 $s_j$ ，即 $s_i | s_j =s_i$ 。
若 $a_{i,j}=a_{j,i}=0$ ，则一定不存在 $s_i | s_j =s_i$ 。

同时还有

s_i=s_j

的情况。则可以再次判掉剩下的无解情况。

接下来考虑有解情况。根据上面的推导，我们发现交换

i

和

j

的位置不会改变情况，假设链上有

\text{cnt}

个，很明显排列组合一下情况数有

cnt!

。

所以预处理一下阶乘，在算一下即可。

\text{bitset}

维护做到了

O(\frac{n^3}{w})

。可以尝试推导一下时间复杂度。

代码

CPP

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=405;
const int mod=998244353;
int t,n,jc[N];
bool vis[N];
signed main(){
	jc[0]=1;
	for(int i=1;i<=400;i++) jc[i]=jc[i-1]*i%mod;
	scanf("%lld",&t);
	while(t--){
		scanf("%lld",&n);
		memset(vis,0,sizeof(vis));
		bitset <N> s[N];
		memset(vis,0,sizeof(vis));
		for(int i=1;i<=n;i++)
			for(int j=1,x;j<=n;j++)
				scanf("%lld",&x),s[i][j]=x;
		bool f=0;
		for(int i=1;i<=n;i++)
			if(!s[i][1]||!s[1][i]){f=1;break;}
		if(f==1){printf("0\n");continue;}
		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]))&&!s[i][j]){f=1;break;}
				else if((s[i]|s[j])!=s[i]&&(s[i]|s[j])!=s[j]&&s[i][j]){f=1;break;}
		    if(f==1) break;
		}
		if(f==1){printf("0\n");continue;}
		int 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*jc[cnt]%mod;
			}
		printf("%lld\n",ans);
	}
	return 0;
}

撒花！

题解：AT_arc197_d [ARC197D] Ancestor Relation

文章操作

思路

题目描述

代码

相关推荐

评论

题解：AT_arc197_d [ARC197D] Ancestor Relation