丧心病狂的多项式

[文章目录]

定义

:表示一个关于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)即可。

多项式开根

已知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)) ,其余的好像得二次剩余。

发表评论

邮箱地址不会被公开。 必填项已用*标注