多项式 exp

· · 个人记录

多项式 exp

前言

学了 多项式 ln 就自然去学了 多项式 exp 了
当然，其中出现了一些问题，不然这个文章也不会出现

理论推导

我直接上牛顿迭代了，因为这个比较通用一些，很多类似 (G\circ F)(x) 的情况都可以使用牛顿迭代求解

大部分推导来自 OI-wiki

考虑倍增思想(用这个总有特殊性质可以被发现)

首先，我们更新出 [x^0]Exp(x) 的值

[x^0]Exp(x)=1

因为 [x^0]f(x) 为 0
证明:
假设 [x^0]f(x)=a_0\neq 0

\lim_{x \to \infty}$ 时，因为此时 $[x^2]f(x), [x^3]f(x)...[x^n]f(x)$ 都是比 $[x^1]f(x)$ 更高阶的无穷大，所以我们只讨论 $[x^1]f(x)

那么此时有 f(\infty)=a_0+a_1\cdot \infty 不难看出

牛顿迭代

将 g\left(f\left(x\right)\right) 在 f_{0}\left(x\right) 处进行泰勒展开，有：

\sum_{i=0}^{+\infty}\frac{g^{\left(i\right)}\left(f_{0}\left(x\right)\right)}{i!}\left(f\left(x\right)-f_{0}\left(x\right)\right)^{i}\equiv 0\pmod{x^{n}}

因为 f\left(x\right)-f_{0}\left(x\right) 的最低非零项次数最低为 \left\lceil\frac{n}{2}\right\rceil
故当 i=2 时, (f(x)-f_0(x))^i 的非0项最低次为\lceil\frac{n}{2}\rceil*2=n 又有 (mod\ x^n) 则当 i\geq2 时 最终结果为 (f(x)-f_0(x))^i=0x^0+0x^1+\cdots+0x^n\equiv 0\pmod{x^{n}}
即有 \forall 2\leqslant i:\left(f\left(x\right)-f_{0}\left(x\right)\right)^{i}\equiv 0\pmod{x^{n}}
则有：f\left(x\right)\equiv f_{0}\left(x\right)-\frac{g\left(f_{0}\left(x\right)\right)}{g'\left(f_{0}\left(x\right)\right)}\pmod{x^{n}}

Exp推导

设给定函数为 h\left(x\right)，有方程：

g\left(f\left(x\right)\right)=\ln{f\left(x\right)}-h\left(x\right)\pmod{x^{n}}

应用 Newton's Method 可得：

f\left(x\right)&\equiv f_{0}\left(x\right)-\frac{\ln{f_{0}\left(x\right)}-h\left(x\right)}{\frac{1}{f_{0}\left(x\right)}}&\pmod{x^{n}}\\ &\equiv f_{0}\left(x\right)\left(1-\ln{f_{0}\left(x\right)+h\left(x\right)}\right)&\pmod{x^{n}} \end{aligned}

代码

void exp(ll a[], int len){

    Exp[0]=1;
    for(int h=2;h<=len;h<<=1){
        int H=h<<1;

        copy(Exp, Exp+h, c);
        ln(c, h);
        c[0]=1;
        for(int i=1;i<h;++i) c[i]=(a[i]-c[i]+P)%P;

        ntt<>(c, H), ntt<>(Exp, H);
        for(int i=0;i<H;++i)
            Exp[i]=Exp[i]*c[i];
        ntt<0>(Exp, H);

        fill(Exp+h, Exp+H, 0);
    }

}

由于卷积中有 [x^m]H(x)=\sum_{i=0}^{m}[x^i]F(x)\cdot [x^{m-i}]G(x)
不难得出, 我们把 [x^0]F(x) 赋值为 1 即可贡献后面的所有值，可以实现[x^i]G(x)\cdot [x^i]F(x)+[x^i]G(x)