自动搬运

查看原文

来自洛谷，原作者为

	MoSalah 退役不退学

搬运于2025-08-24 22:38:35，当前版本为作者最后更新于2022-06-03 21:56:15，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

这道题非常有意思。

看这个数据范围你就知道要推式子吧。

题意：

一个并查集，最开始 $fa_i=i$。在这个数组进行多次带路径压缩的合并操作，保证每次合并的两个点 $i$ 和 $j$ 的关系是 $fa_i \ne fa_j$。给定 $fa$ 的大小 $n$，有多少种 $fa$ 数组可以通过两次合并得到，取余 $998244353$。

那么考虑所有不可以的建树方法：

• 一个 $\text{father}$ 有三个 $\text{son}$

这样就会有 $6$ 种操作方式，不可能满足题目。

• 一个非根的 $\text{father}$ 有两个 $\text{son}$

这样就有两种方式，如果再添加一条边则会出现四种操作方式，不可能满足题目。

也就是说

这棵构造的树一定是两种结构：

〇 $\leftarrow$ 〇 $\leftarrow$ 〇 $\leftarrow$ 〇

和

〇 $\leftarrow$ 〇 $\leftarrow$ 〇

$\uparrow$

〇

比较抽象，就是表示了两种建树方式，分别是一条直线和在根处分成两个叉。

当然，分了叉之后两条边长度就必须是 $1$。

如果叉的一条边长度为 $2$，那么这个树长这样：

〇 $\leftarrow$ 〇 $\leftarrow$ 〇

$\uparrow$

〇

单独的那条边可以穿插在 $\text{merge}$ 任意的位置，然而另一条则不是，就有三种顺序。

到这里我们知道上面的第二种结构只有一种可能性，就是：

〇 $\leftarrow$ 〇

$\uparrow$

〇

所以，大小为 $n$ 的并查集合并后只能有 $1$ 个三个点的树或者 $2$ 个两个点的树，再大就不可行了。

那么，整理公式：

〇 $\leftarrow$ 〇

〇 $\leftarrow$ 〇

或者

〇 $\leftarrow$ 〇

$\uparrow$

〇

是可行的。

第一种方案数 $\binom{n}{4} \times \frac{\binom{4}{2}}{2}\times2\times2$

第二种方案数 $\binom{n}{3} \times 3$

整理公式，得答案为：

$\frac{n(n-1)(n-2)^2}{2}$

每组样例都这样算，别忘了取模，还有，取错模可是 $40\text{pts}$ 哦！

代码来了，只给关键

printf("%lld\n",1ll*(n-1)*n/2%mod*(n-2)%mod*(n-2)%mod%mod);

给个赞再走吧谢谢。