题解：AT_agc070_b [AGC070B] Odd Namori

· · 题解

安慰自己不要太烦\ 没有你的我只是不习惯

容斥宇宙题。

考虑题面的三条限制。对于限制一，相当于图是一个内向基环树森林，与长度为 n 值域为 [1,n] 的序列构成双射，接下来我们称与当前图对应的序列为 p。

对于限制二我们容易想到容斥：钦定若干环，奇环的容斥系数为 1，偶环的容斥系数为 -1。这样一个图如果有一个偶环，那么偶环选或不选之间的系数抵消，贡献是 0；一个图如果没有偶环，那么奇环的系数恰好是 2^{环的数量}，很好！

但是我们暴力枚举若干个环再计数太劣了。我们设钦定在环上的点构成的集合为 S，若 |S|\geq 2，选出编号最小和次小的点 u,v，然后交换 p_u 和 p_v。

由于交换操作的性质，操作后的图与原图构成双射，而无论是把一个奇环拆成奇环和偶环，还是把两个奇环合并成偶环，容斥系数都恰好 \times -1，所以所有 |S|\geq 2 的钦定方案的贡献的和 =0。

对于 |S|=1 的方案是好求的，放在序列上相当于钦定 p_{i}=i，答案是 n\times n^{n-1}=n^n。

考虑有限制三怎么做，我们尝试像上面一样交换 p 的两个元素构成双射。

还是讨论 S，希望能通过交换构成双射，又因为容斥系数恰好 \times -1 就能抵消了。

若 S 上的点在树上构成了 \geq 2 个连通块，选出 连通块的根 中编号最小和次小的点 u,v 交换即可。首先由于交换不会改变 S，也就不会改变 S 构成 连通块的根 这个集合。然后，操作之后显然仍然满足限制三。

所以只需要考虑 S 在树上构成 1 个连通块。选出最小的有序对 (u,v)，满足 \text{fa}_u=\text{fa}_v 并交换，与上面同理构成双射。

所以 S 只能构成一条 祖先-后代 链，设深度最浅的点为 u，其儿子为 v，若 p_u\ne u，交换 p_u 和 p_v 同理能构成双射。此时只考虑 p_u=u，再令 u 为深度第二浅的点，其儿子为 v……

我们可以一直进行下去，直到 \forall x\in S,p_x=x，此时 S 内部的方案数就是 1。其他点的答案是 (n-1)^{n-|S|}\times [1\notin S]\frac{n}{n-1}，因为 p_{1} 可以选 n 个数而其他点由于有父亲只能选 n-1 个数。

此时我们可以写出一个 O(n^2) 的做法了，暴力枚举这条链即可。我们枚举 S 最深的点 x，发现答案只跟 \text{dep}_x 有关，所以推导一下发现只需要预处理 \sum_{i=1}^d (n-1)^i 即可。

时间复杂度 O(n)。

我真的忘了\ 我只剩我一口\ 在这里 想着你