B - Special Subsets¶

题意¶

$1$ 以上 $N$ 以下の整数すべてから成る集合を $S$ とします。

$f$ は $S$ から $S$ への関数であり、 $f(1),f(2),\ldots,f(N)$ の値が $f_1,f_2,\ldots,f_N$ として与えられます。

$S$ の空でない部分集合 $T$ であって、次の両方の条件を満たすものの個数を $998244353$ で割った余りを求めてください。

全ての $a\in T$ について $f(a)\in T$ である。
全ての $a,b\in T$ について $a\neq b$ ならば $f(a)\neq f(b)$ である。

解析¶

对于每一个 $f(i)=f_i$ ，我们都连一条有向边 $(i,f_i)$ 。那么题目要求的条件可以改写为：

若 $i\in T$ ，则所有能够通过 $i$ 到达的点也属于 $T$
所有点入度小于 $2$

因为每个点都恰好有一条出边，且该边连向的点也属于 $T$ ，故 $T$ 的诱导子图恰好含有 $|T|$ 条边。由于 $T$ 中所有点入度之和等于 $|T|$ ，且所有点入度小于 $2$ ，由狄利克雷原理可知所有点的入度都恰为 $1$ 。故任何合法的 $T$ 都是若干个环上所有点的集合。

由于原图中每个弱连通分量的边数与点数相等，故原图的每个弱连通分量都是一个基环树，包含且仅包含一个环。因此环的数目等于弱连通分量的数目，用并查集处理即可。

实现¶

#include <bits/stdc++.h>

const int maxn = 2e5 + 19, mod = 998244353;

int fa[maxn];
int find(int node){
    return fa[node] == node ? node : fa[node] = find(fa[node]);
}

int n, ans;

int main(){
    std::scanf("%d", &n), std::iota(fa + 1, fa + 1 + n, 1);
    for(int i = 1, f; i <= n; ++i){
        std::scanf("%d", &f);
        if(find(f) != find(i))
            fa[find(f)] = find(i);
    }
    ans = 1;
    for(int i = 1; i <= n; ++i)
        if(find(i) == i)
            ans = (ans + ans) % mod;
    ans = (ans + mod - 1) % mod;
    std::printf("%d\n", ans);
}

来源¶

AtCoder Regular Contest 114 B - Special Subsets

B - Special Subsets¶

题意¶

解析¶

实现¶

来源¶

评论