丧心病狂的多项式 – Lijinnn's Blog

[文章目录]

定义
多项式乘法
多项式逆元
多项式除法/取模
泰勒展开
牛顿迭代
多项式牛顿迭代
多项式求导/积分
求ln(A(x))
多项式exp
多项式的幂
多项式开根

定义

：表示一个关于x的多项式
:表示多项式的逆元
:表示的i阶导

多项式乘法

FFT或NTT或任意模FFT 复杂度
扔一个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同理，将单位复数根变成的原根的次幂即可。
任意模FFT：对于每个数，拆成两部分。
那么等价于分成4部分求卷积之后再加到一起，可以缩小FFT后结果大小的范围，进而实现任意模。
~~如果更大的话可以尝试分3或2*2段~~

多项式逆元

即则称为在意义下的逆元。

求法：
当n==1时，即为常数项的逆元。
倍增，已知使得，求使得
两式相减得：
因为A(x)不为0，所以：
两边平方得：，使得模数变成n次。
两边同乘A(x)，移项得：就做完了。
每次B(x)的项数是的，A是n的，所以开到2n长度就行了。
复杂度：注意每次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;
}

多项式除法/取模

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

定义运算，即把A(x)0 ~ n-1项的系数翻转后得到的多项式。
得：
=
=
模得：
移项得：
求出C(x)后回代即可求出D(x)
用求出，翻转即商，回代求模。

泰勒展开

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

首先通过f(0)求出0次项系数a0
将f求导，发现a1变成了常数项，再通过求出1次项系数。
以此推类。
注意每次求导都会使多项式系数前面乘上自己的幂次，之后幂次-1。那么最后的式子就是：

注意每次都是拿0这个横坐标来逼近函数，考虑扩展到任意横坐标
对于定义域[L,R]的函数，在具有n阶导数，则成立下式：

牛顿迭代

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

普通牛顿迭代：求f(x)的零点。
随便弄个，之后将f(x)在处泰勒展开：

只保留线性部分：
化简得：
用x代替代入，迭代多次即可。

多项式牛顿迭代

已知g(x)，，求f(x)。即求一个关于多项式f(x)的方程的解。

和求逆类似，倍增：
n==1时直接用牛顿迭代零点。
考虑已知求
在B(x)处泰勒展开：
发现A(x)-B(x)的前项系数都是0，整个多项式还是的，所以只保留前两项即可:

得：，迭代即可，最后得到的是精确解。

多项式求导/积分

求导，
积分
复杂度O(n)
~~你这求导再积分常数项不就没了么。。。~~

求ln(A(x))

求导+求逆+求积分

多项式exp

已知A(x)，求

取ln得：
代入牛顿迭代：
根据ckh口胡，因为你把f(x)看成变量了，所以A(x)就相当于常数项，求导即为0。
~~真的没问题么。。。~~
化简得：

多项式的幂

求

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

多项式开根