[省选联考 2024] 重塑时光 题解

· · 题解

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

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

可能更佳的阅读体验

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

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

所以我们考虑类似 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) 的时间复杂度内解决了这题，代码在这里。