题解 CF1349F2

写在前面： - 作者诚挚感谢传奇特级大师 yqiangt 的倾囊相授。 - 本做法比所有现有做法都要 **简单的多**。 - 前半部分与其他题解相同。觉得讲的烂可以看其他的。 - 很多地方需要广义求逆偏移系数。注意。 ___ F1 做法左转 F1 题解区。我们直接开始处理式子。 $$ \text{ans}_i = \sum_{j=1}^n\left<\begin{matrix}j\\i-1\end{matrix}\right>\dfrac{n!}{j!} $$ “黑盒”欧拉数是必须被打开的。考虑方法。 [欧拉数板题](https://www.luogu.com.cn/problem/P5825)中我们拥有一个差卷积的式子。但直接将其代入难以化简。 考虑该差卷积的推导过程——我们希望能在中间某一步突然要素察觉。 当时的做法是：设出至少 $k$ 个上升以容斥。容易知道这个 至少/恰好 是 **二项式**演绎/反演 的关系。 考虑统计至少 $k$ 个上升的长度为 $n$ 的排列个数：根据套路，我们考虑 **“块”** 的结构——“块”是单调上升的子段。则此时至少 $k$ 个上升等价于有 $n-k$ 个块。使用 EGF 组合，个数即为 $[\dfrac{x^n}{n!}](e^x-1)^{n-k}$。 代入二项式反演即可得到一个欧拉数的通项，虽然包含取系数。（导出差卷积只需将 $(e^x-1)^{n-k}$ 展开化简二重和式）但是不妨代入答案一试。 $$ \begin{aligned} \text{ans}_i &= \sum_{j=1}^n\dfrac{n!}{j!}\sum_{k=i-1}^{j-1}(-1)^{k-(i-1)}\binom{k}{i-1}[\dfrac{x^j}{j!}](e^x-1)^{j-k}\\ &= n!\sum_{k=0}^{n-1}(-1)^{k-i+1}\binom{k}{i-1}\sum_{j=k+1}^{n}[x^j](e^x-1)^{j-k}\\ &= n!\sum_{k=0}^{n-1}(-1)^{k-i+1}\binom{k}{i-1}\sum_{j=1}^{n-k}[x^k]\left(\dfrac{e^x-1}{x}\right)^j \end{aligned} $$ 驻足观察。此时前后两个 $\sum$ 几乎完全割裂——后一个中甚至没有指标 $i$ 的出现。 同时，若我们求出了 $t_k = \sum_{j=1}^{n-k}[x^k](\dfrac{e^x-1}{x})^j$，$\text{ans}$ 可以一次差卷积完成。所以问题变成求 $t_k$。 设 $F = \dfrac{e^x-1}{x}$，则 $t_k = [x^k]F\dfrac{1-F^{n-k}}{1-F} = [x^k](\dfrac{F}{1-F}-\dfrac{F^{n-k+1}}{1-F})$。$\dfrac{F}{1-F}$ 直接算出即可。考虑后面那一坨，设其为 $r_k$。 因为 $[x^0]F = 1$，因而我们无法直接使用拉反 Tish。仿佛做不太动了。 正 片 开 始。 **直接将 $F$ 代入**，我们得到 $r_k = [x^k]\dfrac{F^{n-k+1}}{1-F} = [x^n]\dfrac{(e^x-1)^{n-k+1}}{x-e^x+1}$。 重新构造复合的形式，我们现在令 $G = e^x-1$，不难构造外层函数 $H_k = \dfrac{x^{n-k+1}}{G^{(-1)}-x}$，使得 $r_k = [x^n]H_k(G)$。 - 填坑：不难解方程得到 $G^{(-1)} = \ln (1+x)$。 这个 $H$ 很烦！我不想导它！那就上扩展另类拉格朗日反演： $$ \begin{aligned} r_k = [x^n]H_k(G) &= [x^n]H_kG^{(-1)}{'}\left(\dfrac{x}{G^{(-1)}}\right)^{n+1}\\ &= [x^{k-1}]\dfrac{1}{G^{(-1)}-x}G^{(-1)}{'}\left(\dfrac{x}{G^{(-1)}}\right)^{n+1}\\ \end{aligned} $$ 可以直接计算。我们做完了。$O(n\log n)$。 - 重新审视我们的推导过程：采用扩展另类拉格朗日反演除了方便了我们的计算之外，**也保持了 $H_k$ 的形式**依然好看，使得最后答案全部规约到一个多项式上。 代码：这还写不出来？实在需要私信找 我/@滑大稽 要。