CF1516E Baby Ehab Plays with Permutations

首先我们列出二元生成函数 \(F(x, y)\)，\(F(x, y) [x^{i}] [y^{j}]\) 表示长度为 \(i\) 的序列，有 \(j\) 个循环，每一个循环的长度 \(> 1\)，是关于 \(x\) 的 \(\rm EGF\)。可以知道 \(F(x, y) = e^{y (- x - \ln(1 - x))}\)。

对 \(x\) 求偏导可以得到递推柿：

因此得到

在官方题解中的 \(dp_{n, k} = \sum\limits_{i = 0} F(x,y) [x^{i+k}] [y^{i}] n^{\underline{i+k}}\)。

构造一个新函数 \(G(x, y)\) 满足 \([x^{n}] [y^{k}] G(x, y) = [x^{n}] [y^{n-k}] F(x,y)\)。

可以得到递推：\(n[x^{n}]G(x, y) = (n-1) y [x^{n-1}] G(x, y) + y [x^{n-2}] G(x,y)\)。

然后让 \(G_i = G(x, y) [x^i]\) ：

要求的 \(dp_{n, k} = \sum\limits_{i = 0} n^{\underline{i}} G_{i} [y^{k}]\)，所以我们算出来 \(\sum\limits_{i = 0} n^{\underline{i}} G_{i}\) 即可。

这是这一部分的实现

接下来是没有实现过的东西：这个可以分治 \(\rm FFT\) 维护矩阵算，时间复杂度 \(\Theta(k \log^2 k)\)。

CF1516E Baby Ehab Plays with Permutations

原文：https://www.cnblogs.com/zkyJuruo/p/14687763.html