P10219 [省选联考 2024] 虫洞 题解

· · 题解

P10219 [省选联考 2024] 虫洞 题解

题意

给定合法的 m 个 n 排列 p^x_i, 你需要再添加 k 个 n 排列, 使得这 (m + k) 个排列依旧合法. 定义 m 个 n 排列合法, 当且仅当 \forall i \in [1,n], p^x_{p^y_i} = p^y_{p^x_i} \space (x, y \in [1, m]).

--- ### Sub1 $\space \space \space n \le 5, m \le 3, k \le 3

按题意枚举即可.

Sub2 \space \space \space m = 0, k = 1

答案显然为 n!.

Sub3 \space \space \space m = k = 1

把给定的排列画出来, 显然形成若干个环. 考虑一个大小为 s 的环, 其每条出边对应的点也必定在同一个环, 且恰好不重不漏地包含了这个环中的每个点. 此时有 s 种方案. 故答案为

\sum_s {s^{c_s} \times c_s!}

其中 c_s 为大小为 s 的环的数量.

Sub4 \space \space \space k \le 100

下称一个连通块为一组合法排列形成的弱联通分量. 当 m > 1 时, 判断一个连通块是否能连向另一个连通块就没那么简单了, 考虑能连的连通块之间的具体关系.

定义大小为 s 的连通块 G_1 与 G_2 同构, 当且仅当存在两个 s 排列 q_{1, i} 和 q_{2, i}, 使得对于所有 G_1 中的边 (q_{1, i}, q_{1, j}), G_2 中都有对应的边 (q_{2,i}, q_{2, j}), 反之亦然. 则可以立即得出同构具有转递性, 新加一个排列可以视为合并这两个连通块. 并且两个不同构的连通块完全不相关, 因此可以分开考虑.

对于如何判断两个连通块是否同构的问题以后再考虑.

故只需考虑现在有 i 个大小为 s 的连通块, 加入 k 个排列后依旧合法的方案数. 设 f_{i, j, s} 表示 i 个大小为 s 的连通块, 还要加 j 个排列, 最终要合并成一个连通块的方案数. 则得知 f_{i, k, s} 后可简单 Dp 算出答案, 以后再考虑. 考虑如何转移 f_{i, j, s}.

下面引出一些定理.

由此, 可以得出 f 的转移方程

f_{i, j, s} = \sum_{x | i} f_{x, j - 1, s \times \frac{i}{x}} \times g_{i, x} \times s^{i - x + 1} $$ g_{i, x} = g_{i - \frac{i}{x}, x - 1} \times {i - 1 \choose \frac{i}{x} - 1} \times (\frac{i}{x} - 1)! $$ $g_{i, 1} = 1$, 可以 $O(n \ln n)$ 预处理. 发现 $s$ 在方程中仅以阶乘的底数出现, 考虑猜一个 $f_{i, j, s}$ 与 $f_{i, j, 1}$ 的关系. $i - x + 1$ 可以理解为 $当前的连通块数量 - 加入一个排列之后的连通块数量 + 1$. 考虑最终的连通块数量为 $1$, 会加入 $j$ 个连通块, 那么裂项相加可得 $s^{i + j - 1}$ 的系数. 大胆猜测 $$ f_{i, j, s} = f_{i, j, 1} \times s^{i + j - 1} $$ 则当 $s = 1$ 时 $$ f_{i, j, 1} = \sum_{x | i} f_{x, j - 1, 1} \times (\frac{i}{x})^{x + j - 2} \times g_{i, x} $$ <details><summary>Proof</summary> > 考虑数学归纳法, 当 $i = 1$ 时显然成立, 现假设对于前 $i - 1$ 项都成立. > > $$ f_{i, j, s} = \sum_{x | i} f_{x, j - 1, s \times \frac{i}{x}} \times g_{i, x} \times s^{i - x + 1} $$ > > $$ f_{i, j, s} = \sum_{x | i} f_{x, j - 1, 1} \times (s \times \frac{i}{x})^{x + j - 2} \times g_{i, x} \times s^{i - x + 1} $$ > > $$ f_{i, j, s} = \sum_{x | i} f_{x, j - 1, 1} \times (\frac{i}{x})^{x + j - 2} \times g_{i, x} \times s^{i + j - 1} $$ > > 又因为有 > > $$ f_{i, j, 1} = \sum_{x | i} f_{x, j - 1, \frac{i}{x}} \times g_{i, x} $$ > > $$ f_{i, j, 1} = \sum_{x | i} f_{x, j - 1, 1} \times (\frac{i}{x})^{x + j - 2} \times g_{i, x} $$ > > 故 > > $$ f_{i, j, s} = f_{i, j, 1} \times s^{i + j - 1} $$ </details> 现在可以 $O(nk \ln n)$ 预处理 $f$. 考虑计算答案. 考虑当前的连通块等价类中, 连通块大小为 $s$, 共有 $c$ 个连通块, 要加 $k$ 个排列 (题中所给). 设 $d_i$ 表示前 $i$ 个连通块缩成若干个连通块 (不一定同构) 的方案数, 有 $$ d_i = \sum_j d_j \times f_{i - j, k, s} \times {i - 1 \choose i - j - 1} $$ $d_0 = 1$, 可以 $O(n^2)$ 计算, 答案即为每个等价类的 $d_c$ 之积. 现在考虑如何判断两个连通块同构. 对于一个连通块, 枚举一个排列 $p^x \space (x \in [1, m])$, 从任意一个点开始进行 BFS, 维护已经到达过的点的序列, 每次将 $p^x_i$ 在序列中的编号加入答案序列. 下一次 BFS 将已经到达过的点的序列作为队列的初始状态. 则只需对答案序列进行哈希即可. 可以理解为对于第 $x$ 个排列, 此时有 $i$ 个连通块, 大小为 $s$, 先将前 $i - 1$ 个连通块间对应的点 (见上文同构定义中的 $q_1$ 与 $q_2$) 标上模 $s$ 同余的编号, 那么只需最后 $s$ 条边构成的排列相同, 那么就是同构的连通块. 这个哈希的复杂度为 $O(nm)$, 经测试, 最好使用双哈希. 总时间复杂度 $O(nm + nk \ln n + n^2)$. --- ### Sub5 $\space \space \space$ 无限制 上面复杂度的瓶颈在于 $O(nk \ln n)$ 的预处理 $f_{i, j, 1}$. 考虑优化. - $g_{i, x} = \frac{i!}{x! \space (\frac{i}{x})^x}$. <details> <summary>Proof</summary> > 考虑随机一个排列 $s$, $s_{[1, \frac{i}{x}]}$ 表示第一个环的元素集合及顺序, 以此类推. 由于是一个环, $s_1$ 需要是 $s_{[1, \frac{i}{x}]}$ 中的最小值, 概率为 $\frac{1}{\frac{i}{x}}$; 这 $x$ 个环都要满足上述要求, 概率为 $\frac{1}{(\frac{i}{x})^x}$. 由于这 $x$ 个环间是无序的, 需要让每个环内最小的元素有序, 概率为 $\frac{1}{x!}$. 排列共有 $i!$ 个, 故方案数为 $\frac{i!}{x! \space (\frac{i}{x})^x}$. </details> 则有优化后的方程 $$ f_{i, j, 1} = \sum_{x | i} f_{x, j - 1, 1} \times (\frac{i}{x})^{x + j - 2} \times \frac{i!}{x! \space (\frac{i}{x})^x} $$ $$ f_{i, j, 1} = \sum_{x | i} f_{x, j - 1, 1} \times \frac{i! \times i^{j - 2}}{x! \times x^{j - 2}} $$ 设 $h_{i, j} = \frac{f_{i, j, 1}}{i! \times i^{j - 2}}$, 有 $$ h_{i, j} = \sum_{x | i} \frac{h_{x, j - 1}}{x} $$ 考虑其实际意义, $h_{i, j}$ 表示所有长为 $i$ 的序列 $a_l$, 满足第 $1$ 项为 $1$, 第 $i$ 项为 $j$ 的因数, $a_l | a_{l + 1}$, 它们的权值之和. 一个序列 $a_i$ 的权值定义为 $\prod_i \frac{1}{i}$. 由于第二维 $j$ 的范围与 $k$ 同阶 ($10^{15}$), 而最终计算答案只需要 $h_{i, k}$, 考虑在第二维倍增. 考虑一个长为 $j + k$ 的序列, 枚举 $a_{j + 1}$, 有 $$ h_{i, j + k} = \sum_{x | i} h_{x, j} \times h_{\frac{i}{x}, k} \times (\frac{1}{x})^k $$ 故可以在 $O(n \ln n \log k)$ 内计算出 $h_{i, k}$. 还原出 $f_{i, k, s}$ 是简单的. 总时间复杂度 $O(nm + n \ln n \log k + n^2)$.