【学习笔记】CF1349F2 Slime and Sequences (Hard Version)

多项式工业警告！！！

点击看题意

思路来自 这位大佬 。

为什么这么好的题解没人评论。

Part 1

前置知识：拉格朗日反演（多项式复合），分式域（引入负整数次项）。

条件：有两个幂级数$F(x),G(x)$，有$G(F(x))=x$，即$F,G$互为复合逆。

$F,G$应常系数为$0$且$[x^1]$系数非$0$。

首先引入分式域。对于无法求逆的整式$F(x)$，找出$G(x)=F(x)/x^k$，则$\frac{1}{F(x)}=x^{-k}\frac{1}{G(x)}$。这也说明了分式域下存在负指数（这通常在对整式求逆时出现）。注意，此时乘法卷积仍然是良定义。

引理：（默认$F(x)$满足上述条件）
$$[x^{-1}]F^{\prime }(x)F(x{)}^k=[k=-1]$$

证明：当$k\ne -1$时左式可以看作$(\frac{1}{k+1}F(x{)}^{k+1}{)}^{\prime }$，而求导不可能产生$[x^{-1}]$项（$\ln (x)$是例外，但是在$x=0$处无定义，所以不合法）；当$k=-1$时可以验证答案就是$1$。

扩展拉格朗日反演：
$$[x^n]H(G(x))=\frac{1}{n}[x^{n-1}]H^{\prime }(x){\left(\frac{x}{F(x)}\right)}^n$$

另类扩展拉格朗日反演：

$$[x^n]H(G(x))=[x^n]H(x){\left(\frac{x}{F(x)}\right)}^{n+1}{F}^{\prime }(x)$$

懒得抄了，自己看command_block的博客吧

通常来讲，$H(x)$是自己构造的。求复合逆没有比较好的方法，一般要根据题目特殊性质来。一般来讲根据$H(x)$和$F(x)$谁的导函数比较简单来选取公式，并且显然我们也可以看出当$n=0$时只能选后面那一种公式。

比较经典的应用是有标号有根树计数。

Part 2

咕了。自己看大佬写的题解吧。感觉肯定比我写得好。

代码：

//我还真写了，居然能过。