自动搬运

查看原文

来自洛谷，原作者为

	Karry5307 兄弟会背叛你，女人会离开你，金钱会诱惑你，生活会刁难你，只有数学不会，不会就是不会，怎么学都不会

搬运于2025-08-24 22:29:53，当前版本为作者最后更新于2021-03-23 08:51:06，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

---

题意

设 $\text{cyc}_\pi$ 将长为 $n$ 的排列 $\pi$ 当成置换时所能分解成的循环个数。给定两个整数 $n,k$ 和一个 $k-1$ 次多项式，对 $1\leq m\leq n$ 求：

$$\sum\limits_{\pi}F(\text{cyc}_{\pi})$$

其中 $\pi$ 是长度为 $m$ 且不存在位置 $i$ 使得 $\pi_i=i$ 的排列。

$\texttt{Data Range:}1\leq n,k\leq 10^5$。

题解

转置原理。

本篇题解同时适用于 P7438 P7439 和 P7440。

首先将给出的多项式转成牛顿级数，即 $F(x)=\sum\limits_{i}f_i\dbinom{x}{i}$，然后考虑对每一个 $\dbinom{x}{i}$ 单独计算，即

$$\sum\limits_{\pi}\dbinom{\text{cyc}_\pi}{i}$$

也即对所有错排求环数选 $i$ 个的答案。

对于错排而言其 EGF 为 $e^{-x-\ln(1-x)}$，而一元的生成函数不足以表达出环数这个信息，所以再加一个元区分一下，即 $e^{(1+y)(-x-\ln(1-x))}$。

其中 $1+y$ 表示的是如果选这个环则贡献为 $y$，否则贡献为 $1$，如果不熟悉组合符号化的读者可以使用 DP 得到结果，这里简单讲一下。

设 $f_{i,j}$ 表示长度为 $i$ 的排列选 $j$ 个环的答案，考虑枚举 $n$ 所在的环的长度，则有

$$f_{i,j}=\sum\limits_{k\geq 2}\binom{n-1}{k-1}(k-1)!(f_{i-k,j}+f_{i-k,j-1}) $$

同样可以得到上面的式子。

考虑对 GF 求偏导，则有

$$\frac{\partial}{\partial x}F(x,y)=\frac{x(1+y)}{1-x}F(x,y) $$$$[x^n]\frac{\partial}{\partial x}F(x,y)=[x^n]\frac{x(1+y)}{1-x}F(x,y) $$$$(n+1)[x^{n+1}]F(x,y)=[x^n]\frac{y}{1-x}F(x,y)+[x^n]\frac{1}{1-x}F(x,y) $$$$(n+1)[x^{n+1}y^m]F(x,y)=[x^ny^{m-1}]\frac{1}{1-x}F(x,y)+[x^ny^m]\frac{1}{1-x}F(x,y) $$$$(n+1)[x^{n+1}y^m]F(x,y)=\sum_{i}[x^iy^{m-1}]F(x,y)+[x^iy^m]F(x,y) $$

递推系数即可，复杂度 $O(nk)$，可以通过 P7438。

---

现在考虑 $k=10^5$ 求一项，这个时候由于是 $1+y$ 不好处理，考虑先求 $[x^n]e^{y(-x-\ln(1-x))}$。

考虑拉格朗日反演，设 $\dfrac{G^2(x)}{2}=-x-\ln(1-x)$，其复合逆为 $H(x)$，则 $F(x,y)$ 实质上是 $G(x)$ 与 $e^{\frac{x^2y}{2}}$ 的复合，则根据拓展拉格朗日反演有

$$[x^n]e^\frac{G^2(x)y}{2}=\frac{1}{n}[x^{n-1}]xye^{\frac{x^2y}{2}}\left(\frac{x}{H(x)}\right)^n $$

注意到

$$xye^{\frac{x^2y}{2}}=\sum\limits_{i}\frac{x^{2i+1}y^{i+1}}{2^ii!} $$

所以有

$$\frac{1}{n}[x^{n-1}y^m]xye^{\frac{x^2y}{2}}\left(\frac{x}{H(x)}\right)^n=\frac{1}{n2^{m-1}(m-1)!}[x^{n-2m}]\left(\frac{x}{H(x)}\right)^n $$

如果知道复合逆的话可以直接算，现在考虑求 $H(x)$。由于 $G(x)$ 有简单的封闭形式可以牛迭，即

$$\frac{G^2(x)}{2}=-x-\ln(1-x)$$

那么有

$$\frac{x^2}{2}=-H(x)-\ln(1-H(x))$$

即

$$2H(x)+2\ln(1-H(x))+x^2=0$$

直接牛迭即可，注意中间有可能会对一个没有常数项的多项式求逆，这里分子分母同时除以 $x$ 即可，同时 $H(x)$ 的初值为 $x$，而且由于除法的原因次数会不对，多迭代一次即可，可以通过 P7439。

alpha1022 和 cmd_block 的牛迭式子与这个有所不同，感兴趣的读者可以看看。

---

现在考虑 P7440，也就是本题。设 $G(x,y)=e^{(1+y)(-x-\ln(1-x))}$，目标变成了计算

$$\sum\limits_{i}f_i[y^i]G(x,y)$$

考虑转置原理，变成求

$$\sum\limits_{i}f_i[x^i]G(x,y)$$

对 $G(x,y)$ 求偏导则有

$$\frac{\partial}{\partial x}G(x,y)=\frac{x(1+y)}{1-x}G(x,y) $$

设 $F_i=[x^i]G(x,y)$ 则有

$$F_i=\frac{i-1}{i}F_{i-1}+\frac{y+1}{i}F_{i-2}$$

用矩阵表示一下则有

$$\begin{pmatrix}F_i&F_{i-1}\end{pmatrix}=\begin{pmatrix}F_{i-1}&F_{i-2}\end{pmatrix}\begin{pmatrix}\dfrac{i-1}{i}&1\\\dfrac{y+1}{i}&0\end{pmatrix} $$

设

$$\begin{pmatrix}F_i&F_{i-1}\end{pmatrix}=\begin{pmatrix}F_{i-1}&F_{i-2}\end{pmatrix}A_i $$

则实际上的就是

$$\sum\limits_{i}\begin{pmatrix}f_i&0\end{pmatrix}\prod_{j=1}^{i}A_j $$

右边的矩阵乘积可以使用分治 FFT，然后算这个也可以分治算，时间复杂度 $O(n\log^2n+k\log^2k)$。