自动搬运

查看原文

来自洛谷，原作者为

	飞雨烟雁 尽管我们走不了最短路，但图仍是连通图，TLE之前，没有一个节点叫失败。

搬运于2025-08-24 22:29:52，当前版本为作者最后更新于2022-10-21 13:31:04，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

本题解提供一种无需生成函数的做法。

---

注：以下所有排列 $\pi$ 均为错排，$|\pi|$ 表示排列 $\pi$ 的长度。

---

记 $c_{n,i}=\sum_\pi[|\pi|=n][\text{cyc}_ \pi=i]$，即在长度为 $n$ 的错排中，恰能分解为 $i$ 个循环的排列个数。先列个关于 $c_{n,i}$ 的表：

$n,i$	$1$	$2$	$3$
$2$	$1$
$3$	$2$
$4$	$6$	$3$
$5$	$24$	$20$
$6$	$120$	$130$	$15$

不难发现 $c_{n,i}=(n-1)(c_{n-1,i}+c_{n-2,i-1})$，以下证明：

对长度为 $n$ 的排列 $\pi$ 的最后一个数所在循环长度进行分类讨论：

• 显然其循环长度不可能为 $1$。

• 若其循环长度为 $2$，则将这个数字和与它构成循环的那个数一起拿走，剩下一个长度为 $(n-2)$ 的错排。因为原错排有 $i$ 个循环，现拿掉了一个循环，故剩下 $(i-1)$ 个循环，所以剩余部分有 $c_{n-2,i-1}$ 种方案。对于拿掉的那两个数，一个必须是 $\pi_n$，另一个是 $1\sim n-1$ 中任意一个，有 $(n-1)$ 种情况。

• 若其循环长度大于等于 $3$，则将 $\pi_n$ 拿走，并让指向 $\pi_n$ 的那个数指向 $\pi_n$ 所指的那个数（见下例）。那么剩下的 $(n-1)$ 个数仍是错排，且循环数为 $i$，故方案数为 $c_{n-1,i}$。对于 $\pi_n$，它原先可以插在任意一个数的前面，共有 $(n-1)$ 个位置可插。

$$\begin{pmatrix}1&2&3&4\\2&4&1&3\end{pmatrix}\rightarrow\begin{pmatrix}1&2&3\\2&3&1\end{pmatrix} $$

综上，方案数为 $c_{n,i}=(n-1)(c_{n-1,i}+c_{n-2,i-1})$。

---

再看题目要求，记 $\text{Ans}_ m=\sum_{|\pi|=m}F(\text{cyc}_ \pi)$，$F(x)=\sum_if_ix^i$。

若直接展开 $F(\text{cyc}_ \pi)$ 则得：

$$\begin{aligned} \text{Ans}_ m&=\sum_{j}f_j\sum_{|\pi|=m}(\text{cyc}_ \pi)^j\\ &=\sum_{j}f_j\sum_ic_{m,i}\,i^j \end{aligned} $$

记 $b_{m,j}=\sum_ic_{m,i}\,i^j$，可以证明有递推式：

$$b_{m,j}=(m-1)(b_{m-1,j}+\sum_{i=0}^j\binom jib_{m-2,i}) $$

但是要是这样递推下去，时间复杂度是 $O(n^3)$ 的，不如不要。

---

考虑采用 P4827 中的方法，用第二类斯特林数展开普通幂。因为：

$$m^n=\sum_{i=0}^ni!\binom mi\begin{Bmatrix} n \\i \end{Bmatrix} $$

所以可以用这个东西展开 $(\text{cyc}_ \pi)^j$，代入原式有：

$$\begin{aligned} \text{Ans}_ m&=\sum_{j=0}^{k-1}f_j\sum_{|\pi|=m}\sum_{i=0}^ji!\binom {\text{cyc}_ \pi}i\begin{Bmatrix} j \\i \end{Bmatrix}\\ &=\sum_{i=0}^{k-1}\Bigg(i!\sum_{j=i}^{k-1}f_j\begin{Bmatrix} j \\i \end{Bmatrix}\Bigg)\sum_{|\pi|=m}\binom {\text{cyc}_ \pi}i \end{aligned} $$

记 $p_{m,i}=\sum_{|\pi|=m}\binom{\text{cyc}_ \pi}{i}$，列表观察：

$m,i$	$0$	$1$	$2$
$2$	$1$		$0$
$3$	$2$
$4$	$9$	$12$	$3$
$5$	$44$	$64$	$20$

发现 $p_{m,i}=(m-1)(p_{m-1,i}+p_{m-2,i}+p_{m-2,i-1})$，以下证明：

$$ \begin{aligned} p_{m,i}&=\sum_{|\pi|=m}\binom{\text{cyc}_ \pi}i\\ &=\sum_{j}\binom jic_{m,j}\\ &=(m-1)\sum_{j}\binom ji(c_{m-1,j}+c_{m-2,j-1})\\ &=(m-1)\Big(p_{m-1,i}+\sum_{j}\binom {j-1}{i}c_{m-2,j-1}+\sum_{j}\binom {j-1}{i-1}c_{m-2,j-1}\Big)\\ &=(m-1)(p_{m-1,i}+p_{m-2,i}+p_{m-2,i-1}) \end{aligned} $$

证毕，则可在 $O(nk)$ 的时间内把所有的 $p_{m,i}(m\le n, i<k)$ 求出。

关于 $i!\sum_{j=i}^{k-1}f_j\begin{Bmatrix} j \\i \end{Bmatrix}$ 这一部分，可以暴力 $O(k^2)$ 求出。

至此，本题可在 $O(nk+k^2)$ 的时间复杂度内完成。