这个博客园渲染做了些什么玩意。
$$
f(x)=f(x_0)+f'(x_0)(x-x_0)+\frac{f''(x_0)}{2!}(x-x_0)^2+\dots\\
f'(x)=\sum a_nnx^{n-1}\\
\int f(x)=\sum\frac{a_n}{n+1}x^{n+1}+C
$$$$
\exp'(x)=\exp(x),\exp(0)=1\\
\text{取麦克劳林展开:}\exp(x)=1+x+\frac{x^2}{2!}+\frac{x^3}{3!}+\dots\\
\ln'(x)=\frac1x,\ln(1)=0\\
\text{取麦克劳林展开:}\ln(1+x)=x-\frac{x^2}2+\frac{x^3}3-\frac{x^4}4+\dots
$$对于可导函数 $f(x)$，求零点 $x_0$。任取一点 $x_1$，泰勒展开之：
$$
f(x)=f(x_1)+f'(x_1)(x-x_1)+R\\
0=f(x_1)+f'(x_1)(x_0-x_1)+R\\
x_0=x_1-\frac{f(x_1)}{f'(x_1)}-R
$$
考虑做若干次后，$x_1\equiv x_0\pmod {x^A}$，根据 $R=\frac{f''(\xi)}{2}(x_0-x_1)^2$，易得精度翻倍。求 $f^{-1}$，即要求关于 $G$ 的多项式 $G^{-1}-f$ 的零点，$G$ 为多项式。
$$
G_{new }=G+\frac{G^{-1}-f}{G^{-2}}=2G-G^2f
$$
求 $f^{\frac1a}$，$a$ 为正整数，要求关于 $G$ 的多项式 $G^a-f$ 的零点。
$$
G_{new}=G-\frac{G^a-f}{aG^{a-1}}
$$
注意上面都是关于 $G$ 的多项式，因此求导的时候 $f$ 是常数，即微分的应该是 $dG$。对于 $a=2$，$T(n)=T(\frac n2)+O(n\log n)=O(n\log n)$。所以尽管看上去很荒谬，多项式乘法、需要做 $O(\log n)$ 次多项式乘法的多项式求逆、需要做 $O(\log n)$ 次多项式求逆的多项式开方都是 $O(n\log n)$ 的。初始值需要考虑二次剩余。求 $\ln f$，保证常数项为 $1$，直接用麦克劳林展开计算比较低效，考虑 $\ln f=[\int(\ln f)']+C$，这里微分的是 $dx$，根据 $\frac{d}{dx}f[g(x)]=f'[g(x)]\times g'(x)$，得到 $\ln f=(\int\frac{f'}f)+C$。常数项不一定对，代入 $x=0$ 得到 $C=0$。求 $\exp f$，保证常数项为 $0$，使用牛顿迭代，求 $\ln G-f$ 的零点。
$$
G_{new}=G-\frac{\ln G-f}{\frac1G}=G(1-\ln G+f)
$$
这样看来，若要求一个多项式函数 $h(f)$，如果 $h$ 的复合逆比较容易求且可导，那么就能牛顿迭代。如果 $h'$ 比较好求，可以先求导再积分。还可以构造复合 $z^{-1}[z(h)]$，这里 $z^{-1}$ 指 $z$ 的复合逆，但多项式复合逆比较困难，一般使用的也就是 $\exp$ 和 $\ln$ 这一对。求 $f^a$，$a$ 为正整数，有 $f^a=\exp(a\ln f)$，当常数项不为 $1$ 时比较难办。找到第一个非零项 $f_kx^k$，让 $f$ 除掉 $f_kx^k$ 后即可。时间复杂度 $O(n\log n)$。
诶，其实今天还有一个发现。所有容斥题殊途同归都是 \([n=0]=\sum\limits_{i=0}^n(-1)^i\binom ni\) 这个式子，原因在于这个式子本质上是先枚举所有方案，再枚举该方案下所有不合法的子集；我们把它改成先枚举所有不合法的子集，再在此基础上枚举方案，就是一般的容斥做法。本质上仍然是恰好转钦定，不过之前我只会对着二项式反演的式子硬做，今天终于领悟到了容斥是二项式反演特殊情形的道理，此事在去年五月时被 dcytrl 跟我反复提及，顿感自身之不足，当时不应轻视这句话的分量。不过这个东西好像是 classic，只有我现在才领悟罢了。
这样说来二项式反演也是在交换两个 \(\sum\)。本质上在利用 \([n=x]=\sum\limits_{i=x}^n(-1)^{x-i}\binom ix\)，去年八月份的时候有人问我二项式反演的问题，当时我只会生硬地求出 \(g(x)\) 去推 \(f(x)\)，如今确有一些更好的视角。感觉交换两个 \(\sum\) 这个理解真是太牛了，之前怎么没人跟我说过。
但好像说所有容斥题殊途同归都是这个也不太对，有一些题并不是这样简单地对限制容斥。你说对吧？zr hlt 场 t2。