P8378 [PFOI Round1] Two Sequences 题解
MoSalah
·
·
题解
这道题非常有意思。
看这个数据范围你就知道要推式子吧。
题意：
一个并查集，最开始 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);
给个赞再走吧谢谢。