题解：AT_arc197_d [ARC197D] Ancestor Relation

· · 题解

题目传送门

思路

好题要赞，建议评蓝。

题目描述

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

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

两棵树不同，当且仅当存在两个结点 $i,j$，在其中一棵树上它们之间有直接连边而在另一棵树上没有。 请输出答案对 $998244353$ 取模后的结果。

这题显而易见的位运算。

我们令 N \times N 的矩阵为 A_{i,j}，则不妨用一个 bitset 表示每一行中 a_j 的 0 或 1 总体情况。我们令这个 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 上面：

同时还有 s_i=s_j 的情况。则可以再次判掉剩下的无解情况。

接下来考虑有解情况。根据上面的推导，我们发现交换 i 和 j 的位置不会改变情况，假设链上有 cnt 个，很明显排列组合一下情况数有 cnt!。

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

bitset 维护做到了 O(\frac{n^3}{w})。可以尝试推导一下时间复杂度。

代码

#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;
}

撒花！