丧心病狂的多项式

定义

$A(x)$：表示一个关于x的多项式
$A^{-1}(x)$:表示多项式$A(x)$的逆元
$A^{(i)}(x)$:表示$A(x)$的i阶导

多项式乘法

FFT或NTT或任意模FFT 复杂度$O(nlogn)$
扔一个FFT板子：

#include <cmath>
const double pi=acos(-1.0);
struct cp
{
    double x,i;
    cp(double _x=0,double _i=0):x(_x),i(_i){}
    cp operator +(const cp &z)const {return cp(x+z.x,i+z.i);}
    cp operator -(const cp &z)const {return cp(x-z.x,i-z.i);}
    cp operator *(const cp &z)const {return cp(x*z.x-i*z.i,x*z.i+i*z.x);}
};
void FFT(cp a[],int len,int fl)
{
    int i,j,k; cp t,w,wn;
    for(i=k=0;i<len;++i)
    {
        if(i>k) swap(a[i],a[k]);
        for(j=(len>>1);(k^=j)<j;j>>=1);
    }
    for(i=2;i<=len;i<<=1)
    {
        wn=cp(cos(2*pi*fl/i),sin(2*pi*fl/i));
        for(j=0;j<len;j+=i)
        {
            w=cp(1,0);
            for(k=j;k<j+(i>>1);++k,w=w*wn)
                t=w*a[k+(i>>1)],a[k+(i>>1)]=a[k]-t,a[k]=a[k]+t;
        }
    }
    if(fl==-1) for(i=0;i<len;++i) a[i].x/=len;
}

NTT同理，将单位复数根变成 $998244353$ 的原根 $3$ 的 $\frac{phi}{len}*k$ 次幂即可。
任意模FFT：对于每个数$a_i$，拆成两部分$a_i=b_i*32768+c_i$。
那么$a1_i*a2_j$等价于$b1_i*b2_j*32768^2+b1_i*c2_j*32768+c1_i*b2_j*32768+c1_i*c2_j$分成4部分求卷积之后再加到一起，可以缩小FFT后结果大小的范围，进而实现任意模。
如果更大的话可以尝试分3或2*2段

多项式逆元

即$A(x)A^{-1}(x)=1(mod x^n)$则称$A^{-1}(x)$为$A(x)$在$mod x^n$意义下的逆元。

求法：
当n==1时，$A^{-1}(x)$即为$A(x)$常数项的逆元。
倍增，已知$B(x)$使得$A(x)B(x)=1(mod x^\frac{n}{2})$，求$A^{-1}(x)$使得$A(x)A^{-1}(x)=1(mod x^n)$
两式相减得：$A(x)(B(x)-A^{-1}(x))=0(mod x^\frac{n}{2})$
因为A(x)不为0，所以：$B(x)-A^{-1}(x)=0(mod x^\frac{n}{2})$
两边平方得：$B(x)^2+A^{-1}(x)^2-2*B(x)*A^{-1}(x)=0(mod x^n)$，使得模数变成n次。
两边同乘A(x)，移项得：$A^{-1}(x)=2B(x)-B(x)^2A(x) (mod x^n)$就做完了。
每次B(x)的项数是$\frac{n}{2}$的，A是n的，所以开到2n长度就行了。
复杂度：$O(nlogn)$ 注意每次A(x)的长度是当前mod运算的长度

/*
    求多项式逆元 nlogn*6
    传入的AB不能为同一个指针。
    不修改A的值，只修改B的值。
    空间开4倍，B初始为空
*/
void polyinv(ll A[],ll B[],int len)
{
    static ll tmp[N<<2];
    int M=1,i; B[0]=Pow(A[0],mod-2,mod);
    while(M<len)
    {
        M<<=1;
        memset(tmp,0,sizeof(ll)*(M<<1));
        for(i=0;i<M;++i) tmp[i]=A[i];
        NTT(tmp,M<<1,1); NTT(B,M<<1,1);
        for(i=0;i<(M<<1);++i) B[i]=add((2*B[i]-tmp[i]*B[i]%mod*B[i])%mod+mod);
        NTT(B,M<<1,-1);
        for(i=M;i<(M<<1);++i) B[i]=0;
    }
    for(i=len;i<M;++i) B[i]=0;
}

多项式除法/取模

即$A(x)=B(x)C(x)+D(x)$，已知n项A(x)和m项B(x)，求n-m项C(x)和m-1项的D(x)。

定义运算$A^R(x)=x^{n-1} A(\frac{1}{x})$，即把A(x)0 ~ n-1项的系数翻转后得到的多项式。
得：$A^R(x)=x^{n-1} A(\frac{1}{x})=x^{n-1}(B(\frac{1}{x})C(\frac{1}{x})+D(\frac{1}{x}))$
=$x^{m-1}B(\frac{1}{x})x^{n-m}C(\frac{1}{x})+x^{n-m+1}x^{m-2}D(\frac{1}{x})$
=$B^R(x)C^R(x)+x^{n-m+1}D^R(x)$
模$x^{n-m+1}$得：$A^R(x)=B^R(x)C^R(x) (mod x^{n-m+1}$
移项得：$C^R(x)=A^R(x)B^R(x)^{-1} (mod x^{n-m+1})$
求出C(x)后回代即可求出D(x)
用$A^R(x)B^R(x)^{-1}$求出$D^R(x)$，翻转即商，回代求模。

泰勒展开

我想用一个多项式来近似表示一个不一定是多项式的函数怎么办？

首先通过f(0)求出0次项系数a0
将f求导，发现a1变成了常数项，再通过$f^{(1)}(0)$求出1次项系数。
以此推类。
注意每次求导都会使多项式系数前面乘上自己的幂次，之后幂次-1。那么最后的式子就是：
$f(x)=\frac{f(0)}{0!}+\frac{f^{(1)}(0)}{1!}x^1+\frac{f^{(2)}(0)}{2!}x^2...+\frac{f^{(n)}(0)}{n!}x^n+...$
注意每次都是拿0这个横坐标来逼近函数，考虑扩展到任意横坐标$x_0$
对于定义域[L,R]的函数$f(x)$，在$L \le x_0 \le R$具有n阶导数，则成立下式：
$f(x)=\sum\limits_0^{\infty} \frac{f^{(i)}(x_0)}{i!} (x-x_0)^i$

牛顿迭代

就是一个用已知的解逼近正确的解的迭代方法。

普通牛顿迭代：求f(x)的零点。
随便弄个$x_0$，之后将f(x)在$x_0$处泰勒展开：
$f(x)=f(x_0)+f^{(1)}(x_0)(x-x_0)+...$
只保留线性部分：$f(x)=f(x_0)+f^{(1)}(x_0)(x-x_0)=0$
化简得：$x=x_0-\frac{f(x_0)}{f^{(1)}(x_0)}$
用x代替$x_0$代入，迭代多次即可。

多项式牛顿迭代

已知g(x)，$g(f(x))=0(mod x^n)$，求f(x)。即求一个关于多项式f(x)的方程的解。

和求逆类似，倍增：
n==1时直接用牛顿迭代零点。
考虑已知$g(B(x))=0(mod x^{\frac{n}{2}})$求$g(A(x))=0(mod x^{n})$
在B(x)处泰勒展开：$g(A(x))=g(B(x))+g^{(1)}(B(x))(A(x)-B(x))+\frac{g^{(2)}(B(x))}{2}(A(x)-B(x))^2+...=0(mod x^n)$
发现A(x)-B(x)的前$\frac{n}{2}$项系数都是0，整个多项式还是$mod x^n$的，所以只保留前两项即可:
$g(B(x))+g^{(1)}(B(x))(A(x)-B(x))=0 (mod x^n)$
得：$A(x)=B(x)-\frac{g(B(x))}{g^{(1)}(B(x))}$，迭代即可，最后得到的是精确解。

多项式求导/积分

求导$b_i=(i+1)a_{i+1}$，
积分$c_i=\frac{a_{i-1}}{i}$
复杂度O(n)
你这求导再积分常数项不就没了么。。。

求ln(A(x))

$ln(A(x))=\int ln^{(1)}(A(x))=\int\frac{A^{(1)}(x)}{A(x)}=\int A^{(1)}(x)A^{-1}(x)$
求导+求逆+求积分

多项式exp

已知A(x)，求$f(x)=e^{A(x)}(mod x^n)$

取ln得：$ln(f(x))-A(x)=0(mod x^n)$
代入牛顿迭代：$f(x)=f_0(x)-\frac{ln(f_0(x))-A(x)}{\frac{1}{f_0(x)}}$
根据ckh口胡，因为你把f(x)看成变量了，所以A(x)就相当于常数项，求导即为0。
真的没问题么。。。
化简得：$f(x)=f_0(x)(A(x)-ln(f_0(x))+1)$

多项式的幂

求$A^k(x)(mod x^n)$

其实要是常数次方的话，可以快速幂，每次乘之后将n次方及以上的部分舍去即可，复杂度$O(nlognlogk)$
以下主要是处理多项式次方：
换底：$A^k(x)=e^{k*ln(A(x))}$
求ln+exp
求多项式次方的话直接把k换成B(x)即可。

多项式开根

已知A(x)，求$f^2(x)=A(x)(mod x^n)$

即：$f^2(x)-A(x)=0$
牛顿迭代:$f(x)=f_0(x)-\frac{f_0(x)^2-A(x)}{2f_0(x)}$
=$\frac{1}{2}(f_0(x)+f_0(x)^{-1}A(x))$

/*
    多项式开根 nlogn*18
    传入的AB不能为同一个指针。
    不修改A的值，只修改B的值。
    空间开4倍，B初始为空
*/
void polysqrt(ll A[],ll B[],int len)
{
    static ll tmp1[N<<2],tmp2[N<<2];
    int M=1,i; B[0]=1; // Sqrt(A[0])=1 mod 998244353 
    while(M<len)
    {
        M<<=1;
        memset(tmp1,0,sizeof(ll)*(M<<1));
        memset(tmp2,0,sizeof(ll)*(M<<1));
        polyinv(B,tmp1,M); // 因为是 mod x^M 所以求逆的长度为M。
        for(i=0;i<M;++i) tmp2[i]=A[i];
        NTT(tmp1,M<<1,1); NTT(tmp2,M<<1,1);
        for(i=0;i<(M<<1);++i) tmp1[i]=tmp1[i]*tmp2[i]%mod;
        NTT(tmp1,M<<1,-1);
        for(i=0;i<M;++i) B[i]=(B[i]+tmp1[i])*inv2%mod;
    }
    for(i=len;i<M;++i) B[i]=0;
}

关于迭代的第一项：
如果为double意义下，可以直接开根获得。
如果为mod意义下，对于特定的常数项直接赋值(eg. sqrt(1)=1(mod x)) ，其余的好像得二次剩余。