\(\text{「CF715E」Complete the Permutations}\)

\(\text{Link}\)

\(\text{Describe}\)

给定长为 \(n\) 的且部分确定的置换 \(p,q\)。定义 \(p,q\) 距离为通过交换 \(p\) 任意两项变为 \(q\) 的最小步数，对于 \(0\le k\le n-1\) 求通过补全 \(p,q\) 使得 \(p,q\) 距离为 \(k\) 的方案数对 \(998244353\) 取模的结果。

\(\text{Solution}\)

给定置换 \(p,q\)，我们记每个 \(p_i\) 连向 \(q_i\) 所得图的置换环数为 \(\text{cyc}\)，那么 \(p,q\) 的距离为 \(n-\text{cyc}\)，转换为求有 \(\text{cyc}\) 的置换数量.

在一个不确定的置换中，我们会产生 \(4\) 种边。

\(0\rightarrow 0\)，我们记为 \(E\).

\(p\rightarrow 0\;(p\not =0)\)，我们记为 \(P\).

\(0\rightarrow q\;(q\not =0)\)，我们记为 \(Q\).

\(p\rightarrow q\;(p,q\not =0)\)，我们记为 \(F\).

我们可以发现 \(F\) 边可以将 \(p,q\) 视作一个点（对于置换图可以缩点）。

一个重要的观察，通过手玩几组样例后发现 \(P,E\) 或 \(Q,E\) 可以合并，且与 \(E\) 合并后 \(E\) 边数量不变

考虑 \(0\rightarrow q\) 和 \(0\rightarrow q\) 可以合并为 \(0\rightarrow q\)；
考虑 \(0\rightarrow q\) 和 \(0\rightarrow 0\) 可以合并为 \(0\rightarrow 0\)；
考虑 \(0\rightarrow q\) 和 \(p\rightarrow 0\) 不可以合并；

所以我们对于每一类边考虑生成函数（我们用 \(P,Q,E\) 分别表示对应边的数量）

\[[z^k]P(z)=\sum_{t=k}^P\binom{P}{t}\begin{bmatrix}t\\k\end{bmatrix}(P-t+E-1)^{\underline{P-t}} \]

\[[z^k]Q(z)=\sum_{t=k}^Q\binom{Q}{t}\begin{bmatrix}t\\k\end{bmatrix}(Q-t+E-1)^{\underline{Q-t}} \]

考虑 \(P\) 的组合意义 \(\binom{P}{t}\) 为将所有 \(P\) 边选出 \(t\) 条用来拼成环，而 \(\begin{bmatrix}t\\k\end{bmatrix}\) 为 \(t\) 条边拼成
\(k\) 个环的方案数，我们将剩余的边与 \(P\) 或 \(E\) 合并，由于合并后 \(P\) 边会变少，所以是下降幂，\(Q\) 的组合意义类似。

\[[z^k]E(z)=E!\begin{bmatrix}E\\k\end{bmatrix} \]

考虑将 \(E\) 条边分成 \(k\) 个环为 \(\begin{bmatrix}E\\k\end{bmatrix}\)，注意我们可以在原本排列上以任意顺序确定 \(E\) 条边所以要乘上 \(E!\)，最后答案为 \([z^k]P(z)Q(z)E(z)\)，这里 \(n\le 250\)，暴力 \(O(n^2)\) 卷积即可。

\(\text{Details}\)

考虑 \(0\rightarrow q\) 和 \(p\rightarrow 0\) 在 \(p=q\) 可以合并为 \(0\rightarrow 0\) 边；
已确定的置换可能已经存在置换环，需要排除其影响

\(\text{Ex}\)

此题存在 \(O(n\log n)\) 做法，我们发现卷积我们可以 \(\text{NTT}\) 并不是瓶颈，而瓶颈在于预处理下列式子的值

\[[z^k]P(z)=\sum_{t=k}^P\binom{P}{t}\begin{bmatrix}t\\k\end{bmatrix}(P-t+E-1)^{\underline{P-t}}\\ [z^k]Q(z)=\sum_{t=k}^Q\binom{Q}{t}\begin{bmatrix}t\\k\end{bmatrix}(Q-t+E-1)^{\underline{Q-t}}\\ \]