菜王的 blog

菜就多练，输不起就别玩。忘记卷积可以拉插就是菜，认为 $O(3^nn^2)$ 没多少分就是蠢，没什么借口可找。

如果你做过 ABC306Ex 和 CF1874E，而且你又不是像我这样的蠢货，你就能场切这个题。

考虑重排之后切 $k$ 刀，本质上就相当于将 $\{1, \dots, n\}$ 划分成 $(k + 1)$ 个可以为空的点集，而能重排成功等价于以下条件：

• 对于每个点序列，其为其导出子 DAG 的一个拓扑序；
• 对于将每个点序列缩成一个大点得出的新图，其也是 DAG。

由于题目中每一段内是有序的，所以对于这样的划分方案，还要乘上每个点集内部的拓扑序方案数。

所以我们考虑类似 ABC306Ex 容斥拓扑序计数的方法，每次加入若干个对应大点入度为 $0$ 的点集，设加入了 $i$ 个大点，则容斥系数为 $(-1)^{i + 1}$。

考虑设 $f_{S, i}$ 表示 $S$ 集合内的点被划分为 $i$ 个非空大点的合法方案数，转移可以枚举加入点集的并 $T$，并枚举 $j$，将 $T$ 划分为 $j$ 个大点。再设辅助数组 $g_{S, i}$ 表示 $S$ 集合内的点被划分为 $i$ 个独立的大点，每个大点内部拓扑序方案数之积，$h_S$ 表示 $S$ 集合里的点的拓扑序方案数，于是得转移方程：

$f_{S, i} = \sum_{T \subseteq S} \mathrm{chk}(T, S / T) \sum_{j = 1}^i f_{S / T, i - j} g_{T, j} (-1)^{j + 1}\\ g_{S, i} = \sum_{T \subseteq S} \mathrm{chk}(T, S / T) \mathrm{chk}(S/T, T) g_{S / T, i - 1} h_T\\ h_S = \sum_{u \in S} \mathrm{chk}(S / u, u) h_{S / u}$

其中 $\mathrm{chk}(A, B)$ 表示是否不存在 $B \to A$ 的边，可以 $O(2^n)$ 预处理出每个点集 $S$ 的入边的并集 $in_S$，于是 $O(1)$ 判断 $in_A \cap B = 0$ 即可。

时间复杂度为 $O(3^nn^2)$，但是 $g, h$ 可以 $O(n3^n)$ 预处理。推出具体的转移方程就能看出这个东西明显跑不满，但是我并没有。

发现转移其实是一个卷积形式，所以我们考虑把 dp 写成多项式形式，即 $[x^i]F_S = f_{S, i}$。则可以得出转移方程：

$F_S = \sum_{T \subseteq S} \mathrm{chk}(T, S / T) F_{S / T} G_T$

其中 $[x^i]G_S = g_{S, i} (-1)^{i + 1}$。根据 $f$ 的定义，$F, G$ 显然都是 $n$ 次多项式，使用类似 CF1874E 中的技巧，给 $x$ 代入 $1 \sim n + 1$ 共 $n + 1$ 个点值，分别求出 $F_{2^n - 1}(x)$ 此时的值，即可 $O(n^2)$ 拉插求出其各项系数，也就是 $f_{2^n - 1, 1 \sim n}$ 的值。而代入一个 $x$ 做上述 dp 是 $O(3^n + n2^n)$ 的，后者是预处理所有 $G$ 的时间复杂度。

算出方案之后转换回概率是简单的，考虑将这 $i$ 段非空段重排，然后与无序的 $(k + 1 - i)$ 段空段归并，再以任意的顺序切割已经钦定好的 $k$ 个位置，得到式子：

$i!k!\binom{k + 1}{i} = \frac{k!(k + 1)!}{(k + 1 - i)!}$

最后除掉总方案数 $(n + k)!$ 即可。于是我们在 $O(n3^n)$ 的时间复杂度内解决了这题，代码在这里。