\(\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\) 的组合意义类似。
考虑将 \(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}}\\ \]待更新
标签：begin,end,Complete,text,置换,Permutations,bmatrix,CF715E,rightarrow From： https://www.cnblogs.com/JIEGEHHHH/p/17794873.html