题解 P7440 【「KrOI2021」Feux Follets】

· · 题解

题意

设 \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 的排列。

### 题解 转置原理。 本篇题解同时适用于 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)$。