题解

思路

把每个 $i$ 向 $f_i$ 连一条有向边，得到每点出度恰为 $1$ 的函数图。

做法

条件一要求选中点的后继仍被选中，条件二要求 $f$ 在所选集合上为单射；有限集合上的单射也是满射，因此每个被选点还恰有一个被选前驱。于是合法集合不能包含朝环汇入的树枝，只能对每个有向环选择“整环加入”或“整环不加入”。若环数为 $c$，答案就是 $2^c-1$。

函数图的每个弱连通分量恰好含一个有向环。将每条 $i\to f_i$ 忽略方向并用并查集合并后，根节点数量就是 $c$。最后快速计算 $2^c-1\pmod{998244353}$。

复杂度

时间复杂度为 $O(N\alpha(N))$，空间复杂度为 $O(N)$。