「学习笔记」多项式的蛇皮操作

目录

> 写的时候注意各种数组的清空

前置知识

趋近

数学公式中,有类似于 \(\leftarrow\) 或者 \(\rightarrow\) 的东西,叫做趋近。

其中, \(x\rightarrow \infty\) 叫做 \(x\) 无限接近于 无限大 。

同理, \(x\rightarrow 0\) 叫做 \(x\) 无限接近于 \(0\) 。

反之亦然。

自然常数

自然常数是一个叫做 \(e\) 的东西,那么他是什么呢?

它的其中一个定义为 \(e=\lim_{x\rightarrow \infty}(x+\frac{1}{x})^x\) 。

这个不用怎么理解,记住就好了...

对数

当满足 \(a^n=x\) 时,我们定义 \(\log_a^x=n\)

> 在数学中,对数是对求幂的逆运算,正如除法是乘法的倒数,反之亦然。 这意味着一个数字的对数是必须产生另一个固定数字(基数)的指数。 在简单的情况下,乘数中的对数计数因子。更一般来说,乘幂允许将任何正实数提高到任何实际功率,总是产生正的结果,因此可以对于 \(b\) 不等于 \(1\) 的任何两个正实数 \(b\) 和 \(x\) 计算对数。
>
> 如果 \(a\) 的 \(x\) 次方等于 \(N\) ( \(a>0\) ,且 \(a\) 不等于 \(1\) ) 即 \(a^x=N\) ,那么数 \(x\) 叫做以 \(a\) 为底 \(N\) 的对数 \((logarithm)\) ,记作 \(x=\log_a^N\)。其中, \(a\) 叫做对数的底数, \(N\) 叫做真数

特别地,以无理数 \(e\) 为底记为 \(\ln\) ,称为自然对数。

逆元

这里指取模意义下的逆元。

被各种数论知识折磨过的大神们应该对这个很熟悉吧,这个就不多说了。

导函数

> 如果函数 \(f(x)\) 在 \((a,b)\) 中每一点处都可导,则称 \(f(x)\) 在 \((a,b)\) 上可导,则可建立 \(f(x)\) 的导函数,简称导数,记为 \(f'(x)\) 。

看似高深莫测,实际上就是求一个函数 \(f(x)\) 在 \(x=x_0\) 时的 \(\Delta\) 。

那么,我们有 \(f'(x)=\lim_{\Delta x\rightarrow 0}\frac{f(x+\Delta x)-f(x)}{\Delta x}\) 。

这里有一道函数求导的题,推荐去做一做:OPENJUDGE-NOI-1.5编程基础之循环控制-38

牛顿迭代与泰勒公式

这是什么?怎么全都不知道啊...

首先,牛顿迭代是基于泰勒公式的,那么我们先从泰勒公式说起:

泰勒公式是将一个在 \(x=x_0\) 处具有 \(n\) 阶导数的函数 \(f(x)\) 利用关于 \((x-x_0)\) 的 \(n\) 次多项式来逼近函数的方法。

请注意,这是是逼近,而非等于。

具体的公式呈现:

\[ f(x)=\frac{f(x_0)}{0!}+\frac{f'(x_0)}{1!}(x-x_0)+\frac{f''(x_0)}{2!}(x-x_0)^2+\ldots +\frac{f^{(n)}(x_0)}{n!}(x-x_0)^n+R_n(x) \]
对这个式子进行一些说明:

\(f(x)\) :我们要求的目标函数。

\(f^{(n)}(x_0)\) :函数 \(f(x)\) 的 \(n\) 阶导数。

等号后的多项式称为函数 \(f(x)\) 在 \(x_0\) 处的泰勒展开式,剩余的 \(R_n(x)\) 是泰勒公式的余项,是 \((x-x_0)\) 的 \(n\) 的高阶无穷小。

高阶无穷小:若 \(\lim(β/α)=0\) ,则称“ \(β\) 是比 \(α\) 较高阶的无穷小”。意思是在某一过程 ( \(x→x_0\) 或 \(x→∞\) 这类过程) 中, \(β→0\) 比 \(α→0\) 快一些。

解释完泰勒公式,现在来说牛顿迭代...

多数方程不存在求根公式,因此求精确根非常困难,甚至不可能,从而寻找方程的近似根就显得特别重要。方法使用函数 \(f(x)\) 的泰勒级数的前面几项来寻找方程 \(f(x)=0\) 的根。

用牛顿迭代法解非线性方程,是把非线性方程 \(f(x)=0\) 线性化的一种近似方法。把 \(f(x)\) 在点 \(x_0\) 的某邻域内展开成泰勒级数:
\[ f(x)=\frac{f(x_0)}{0!}+\frac{f'(x_0)}{1!}(x-x_0)+\frac{f''(x_0)}{2!}(x-x_0)^2+\ldots +\frac{f^{(n)}(x_0)}{n!}(x-x_0)^n+R_n(x) \\ =f(x_0)+f'(x_0)(x-x_0)+\frac{f''(x_0)}{2!}(x-x_0)^2+\ldots +\frac{f^{(n)}(x_0)}{n!}(x-x_0)^n+R_n(x) \]

取其线性部分(即泰勒展开的前两项),并令其等于0,即
\[ f(x_0)+f'(x_0)(x-x_0)=0 \]
以此作为非线性方程
\[ f(x)=0 \]
的近似方程,若
\[ f'(x_0)\neq 0 \]
则其解为
\[ x_1=x_0-\frac{f(x_0)}{f'(x_0)} \]
这样,得到牛顿迭代法的一个迭代关系式:
\[ x_{n+1}=x_n-\frac{f(x_n)}{f'(x_n)} \]

不定积分与定积分

积分似乎是一个很高级的东西,但是不幸的是我们现在必须了解(或者说掌握?)其基本定义与基本运算。

不定积分:在微积分中,一个函数 \(f\) 的不定积分,或原函数,或反导数,是一个导数等于 \(f\) 的函数 \(F\) ,即 \(F ′ = f\) 。

什么意思?其实就是我们根据一个导数 \(f'\) 去求一个函数 \(F\) 满足 \(F'=f'\) 。

但为什么是 不定 ?

显然,导数与函数的常数项是没有关系的,也就是说,对于一个导数 \(f'\) ,如果我们要去求其原函数 \(f\) ,是求不出其原函数的 常数项 的,即常数项不定,所以我们只能退而求次,求到 \(F\) (上文有解释),并称 \(F\) 是 \(f'\) 的不定积分。

那么,我们就可以把这个写作
\[ \int f'=F(x)+C \]
或者
\[ \int f'(x)dx=F(x)+C \]

其中, \(C\) 是任意常数。

那么,定积分是什么?

打一个比方,假如说 小明 在 \(2019.1.1\) 有 \(C\) 元钱,在 \(2020.1.1\) 他有了 \(C+\Delta\) 元钱,那么,我们可以根据作差,求到 \(\Delta\) ,但是,如果我们要求到 \(C\) ,似乎是不行的。

这个例子有什么用?

\(C\) 就是我们上文提及的 \(f\) 的常数项,是不可求的,而 \(\Delta\) 是可求得,这就是定积分,是能够确定的。

并且, \(\Delta\) 似乎是一个常数,也就是说:

> 之所以称其为定积分,是因为它积分后得出的值是确定的,是一个常数, 而不是一个函数

定积分定义:设函数f(x) 在区间[a,b]上连续,将区间[a,b]分成n个子区间[x0,x1], (x1,x2], (x2,x3], …, (xn-1,xn],其中x0=a,xn=b。可知各区间的长度依次是:△x1=x1-x0,在每个子区间(xi-1,xi]中任取一点ξi(1,2,...,n),作和式 $\sum_{i=1}^nf(\xi_i)\Delta x_i $ 。该和式叫做积分和,设 \(λ=max\{△x1, △x2, …, △xn\}\) (即λ是最大的区间长度),如果当 \(λ→0\) 时,积分和的极限存在,则这个极限叫做函数 \(f(x)\) 在区间\([a,b]\) 的定积分,记为 \(\int_a^b f(x)dx\) ,并称函数 \(f(x)\) 在区间 \([a,b]\) 上可积。

接下来从几何意义上说明定积分。

![picture]()

终于上图了

设图中的曲线函数为 \(f(x)\) ,现在有一个定积分:
\[ \int_{P_0}^{P_1}f(x)dx \]
其表示的含义就是函数 \(f(x)\) 的图像在 \(P_0< x \leqslant P_1\) 所围出来的图形面积。

怎么求?把他们拆成很多很多个矩形,将这些矩形面积和累加,即可求得面积。

但是这样是会有误差的,但是我们发现,当 \(P_0、P_1\) 越来越大,或者是越来越接近时,我们的计算就越来越精准。


各种基本操作

多项式乘法

这里,我们有十分优秀的 \(FFT\) 以及 \(NTT\) 算法可以解决这样的问题,具体的见下面博客,这里只贴板子了...

\(FFT\) 的详细解释

\(NTT\) 的详细解释

时间复杂度均为 \(\mathcal O(n\log n)\) 。

板子: \(FFT\) 的模板, \(NTT\) 的模板可改


class fft_task{
private:
    struct cplx{
        double vr,vi;//实部和虚部
        cplx(const double R=0,const double I=0):vr(R),vi(I){}//构造函数
        //------------------overload----------------//
        cplx operator + (const cplx a)const{return cplx(vr+a.vr,vi+a.vi);}//重载加法
        cplx operator - (const cplx a)const{return cplx(vr-a.vr,vi-a.vi);}
        cplx operator * (const cplx a)const{return cplx(vr*a.vr-vi*a.vi,vr*a.vi+a.vr*vi);}
        cplx operator / (const double var)const{return cplx(vr/var,vi/var);}
    };

    int n,m;
    cplx a[MAXN+5],b[MAXN+5];

    void fft(cplx* f,const int len,const short opt=1){
        //opt==-1 : FFT 的逆变换
        if(!len)return;
        cplx f0[len+5],f1[len+5];
        for(int i=0;i&lt;len;++i)
            f0[i]=f[i&lt;&lt;1],f1[i]=f[i&lt;&lt;1|1];
        fft(f0,len&gt;&gt;1,opt);
        fft(f1,len&gt;&gt;1,opt);
        cplx w=cplx(cos(Pi/len),opt*sin(Pi/len)),buf=cplx(1,0);
        for(int i=0;i&lt;len;++i,buf=buf*w){
            f[i]=f0[i]+buf*f1[i];
            f[i+len]=f0[i]-buf*f1[i];
        }
    }
public:
    inline void launch(){
        qread(n,m);
        rep(i,0,n)scanf(&quot;%lf&quot;,&amp;a[i].vr);
        rep(i,0,m)scanf(&quot;%lf&quot;,&amp;b[i].vr);
        for(m+=n,n=1;n&lt;=m;n&lt;&lt;=1);
        fft(a,n&gt;&gt;1);
        fft(b,n&gt;&gt;1);
        rep(i,0,n-1)a[i]=a[i]*b[i];
        fft(a,n&gt;&gt;1,-1);
        rep(i,0,m)writc((int)((a[i].vr)/n+0.5),' ');
        Endl;
    }
};

多项式求逆元

给定一个 \(A(x)\) ,求 \(A^{-1}(x)\) 满足
\[ A(x)A^{-1}(x)\equiv 1(\text{mod}\space x^n) \]
其中 \((\text{mod}\space x^N)\) 即为舍去次数 \(\geqslant\space n\) 的项,只保留 \(0\) 到 \(n-1\) 次项。

而 \(A^{-1}(x)\) 就是 \(A(x)\) 在 \(\text{mod}\space x^n\) 下的逆元。

首先,我们设 \(B(x)=A^{-1}(x)\) ,那么就有
\[ A(x)B(x)\equiv 1(\text{mod}\space x^n) \]
假设我们已经知道 \(A(x)\) 在 \(\text{mod}\space x^{\left \lceil \frac{n}{2} \right \rceil}\) 情况下的逆元 \(B_0(x)\) ,那么就有
\[ A(x)B_0(x)\equiv 1 (\text{mod}\space x^{\left \lceil \frac{n}{2} \right \rceil}) \]
而第一个式子我们也可以写为
\[ A(x)B(x)\equiv 1(\text{mod}\space x^{\left \lceil \frac{n}{2} \right \rceil}) \]
将这两个式子相减可得
\[ A(x)(B(x)-B_0(x))\equiv 0(\text{mod}\space x^{\left \lceil \frac{n}{2} \right \rceil}) \]

\[ B(x)-B_0(x)\equiv 0(\text{mod}\space x^{\left \lceil \frac{n}{2} \right \rceil}) \]
平方之后
\[ B^2(x)+B_0^2(x)-2B(x)B_0(x)\equiv 0(\text{mod}\space x^n) \]
由于一个多项式平方之后,次数 \(<n\) 的项至少是由原先一个次数 \(<\lceil \frac{n}{2} \rceil\) 的项乘上其他项得到的,所以这个结果的 \(0\) 到 \(n-1\) 次系数仍然是 \(0\) ,可以变成 \(\pmod{x^n}\)

同乘 \(A(x)\) 得
\[ B(x)-2B_0(x)+A(x)B_0^2(x)\equiv0\pmod{x^n} \]


\[ B(x)\equiv B_0(x)(2-A(x)B_0(x))\pmod{x^n} \]
根据定义,我们可以直接取等,得
\[ B(x)= B_0(x)(2-A(x)B_0(x))\space \text{mod}\space {x^n} \]
时间复杂度为
\[ T(n)=T(\frac{n}{2})+\mathcal O(n\log n)=\mathcal O(n\log n) \]

题目 luoguOJ_P4238

#define rep(i,__l,__r) for(int i=__l,i##_end_=__r;i&lt;=i##_end_;++i)
#define fep(i,__l,__r) for(int i=__l,i##_end_=__r;i&gt;=i##_end_;--i)
int tmp[MAXN+5],p;
void polyinv(int* A,int* B,const int n){
    if(n==1)return (void)(B[0]=qkpow(A[0],MOD-2,MOD));//到了最下面, 直接取其逆元
    polyinv(A,B,(n+1)/2);//n 的上取整
    for(p=1;p&lt;=(n&lt;&lt;1);p&lt;&lt;=1);//NTT 标准步骤
    rep(i,0,n-1)tmp[i]=A[i];//为了避免 A 数组被更改, 
    rep(i,n,p)tmp[i]=0;
    ntt(tmp,p),ntt(B,p);
    rep(i,0,p-1)B[i]=((2-1ll*B[i]*tmp[i]%MOD)%MOD+MOD)*B[i]%MOD;
    ntt(B,p,-1);
    rep(i,n,p)B[i]=0;
}

多项式除法/取模

给定 \(n-1\) 次多项式 \(A(x)\) 与 \(m-1\) 次多项式 \(B(x)\) ,求 \(D(x)、R(x)\) 满足
\[ A(x)=D(x)B(x)+R(x) \]
其中 \(D(x)\) 最高次项最多为 \(n-m\) , \(R(x)\) 的次数 \(<m-1\) 。

或者满足
\[ A(x)\equiv R(x)\pmod {B(x)} \]
其实,从某种角度上来说,这就是多项式除法或者是取模,取决于你想求什么。

因为有 \(R(x)\) ,我们考虑将其去掉,减小问题的复杂度。

定义反转数组
\[ A^R(x)=x^{n-1}A(\frac{1}{x})=\sum_{i=0}^{n-1}a_{n-a-i}x^i \]
将 \(\frac{1}{x}\) 代入第一个式子,并同时乘以 \(x^{n-1}\) ,可得
\[ x^{n-1}A(\frac{1}{x})=x^{n-m}D(\frac{1}{x})x^{m-1}B(\frac{1}{x})+x^{n-m+1}*x^{m-2}R(\frac{1}{x}) \]
根据反转数组的定义,可得
\[ A^R(x)=D^R(x)B^R(x)+x^{n-m+1}R^R(x) \]
由于 \(D^R(x)\) 是 \(n-m\) 次的,所以其在 \(\pmod{x^{n-m+1}}\) 下是没有影响的,那么,我们可以得到
\[ A^R(x)\equiv D^R(x)B^R(x)\pmod{x^{n-m+1}} \]
观察上式,知道 \(A^R(x)、B^R(x)\) ,那么我们可以求得 \(D^R(x)\) ,再通过反转得到 \(D(x)\) ,即
\[ A^R(x){B^R}^{-1}(x)\equiv D^R(x)\pmod {x^{n-m+1}} \]
有一次逆元,两次乘法,时间复杂度是同样的 \(\mathcal O(n\log n)\) 。

而 \(R(x)\) 应该很好求了吧,这里不再赘述。

题目 luoguOJ_P4512

#define rep(i,__l,__r) for(int i=__l,i##_end_=__r;i&lt;=i##_end_;++i)
#define fep(i,__l,__r) for(int i=__l,i##_end_=__r;i&gt;=i##_end_;--i)int Ar[MAXN+5],Br[MAXN+5],Br_[MAXN+5];
inline void polydiv(int* A,int* B,int* D,int* R,int n,int m){
    memset(Ar,0,sizeof Ar);memset(Br,0,sizeof Br);memset(Br_,0,sizeof Br_);
    rep(i,0,n-1)Ar[i]=A[n-i-1];
    rep(i,0,m-1)Br[i]=B[m-i-1];
    polyinv(Br,Br_,n-m+1);
    int p;
    for(p=1;p&lt;=n*2-m+1;p&lt;&lt;=1);
    /*
        因为 Br(x) 的逆元 Br_(x) 是在 mod x^{n-m+1} 的情况下进行的
        因而其长度为 n-m+1
        再加上 A(x) 的长度 n
        总长即为 n+n-m+1=n*2-m+1
    */
    ntt(Ar,p),ntt(Br_,p);
    rep(i,0,p-1)D[i]=1ll*Ar[i]*Br_[i]%MOD;
    ntt(D,p,-1);
    rep(i,n-m+1,p)D[i]=0;//因为 D(x) 的最高次为 n-m , 因而后面的都可以全部清零
    for(int i=0,j=n-m;i&lt;j;++i,--j)swap(D[i],D[j]);//求得 Dr(x) , 还需反转

    for(p=1;p&lt;=n;p&lt;&lt;=1);
    /*
        n+1=n-m+m
        n-m : 多项式 D
        m : 多项式 B
    */
    rep(i,0,m-1)Br[i]=B[i];rep(i,m,p)Br[i]=0;
    rep(i,0,n-m)Br_[i]=D[i];rep(i,n-m+1,p)Br_[i]=0;
    ntt(Br,p),ntt(Br_,p);
    rep(i,0,p-1)R[i]=1ll*Br[i]*Br_[i]%MOD;
    ntt(R,p,-1);
    rep(i,0,n-1)R[i]=(0ll+A[i]-R[i]+MOD)%MOD;
}

多项式牛顿迭代法

这个部分没有代码,只是一种思想。

有一个关于多项式 \(f(x)\) 的方程 \(g(f(x))=0\)

> 对 \(g(f(x))\) 的说明(如果理解其含义可直接跳过):
>
> 这里的 \(f(x)\) 并非是一个值,而是多项式,比如有
> \[ g(x)=4x^2+1 \]
> 并且我们令
> \[ f(x)=x+4 \]
> 那么,就有
> \[ g(f(x))=4(x+4)^2+1 \]

现在开始说明牛顿迭代法。

假设我们已经知道了 \(f(x)\) 的前 \(n\) 项的多项式 \(f_0(x)\) ,即
\[ f(x)\equiv f_0(x)\pmod{x^n} \\ g(f_0(x))\equiv 0\pmod{x^n} \]
然后,我们对 \(g(f(x))\) 在 \(f_0(x)\) 上进行泰勒展开
\[ g(f(x))=g(f_0(x))+\frac{g'(f_0(x))}{1!}(f(x)-f_0(x))^1+\frac{g''f_0(x)}{2!}(f(x)-f_0(x))^2+\ldots \ldots \]
根据定义,有 \(f(x)-f_0(x)\) 的前 \(n\) 项系数为 \(0\) 。

即,从第三项开始, \((f(x)-f_0(x))^k\) 保证 \(2\le k\) 时,后面的东西在 \(\pmod{x^{2n}}\) 意义下同余 \(0\) 。

那么就有
\[ g(f(x))\equiv g(f_0(x))+g'(f_0(x))(f(x)-f_0(x))\equiv 0\pmod{x^{2n}} \]

\[ f(x)\equiv f_0(x)-\frac{g(f_0(x))}{g'(f_0(x))}\pmod{x^{2n}} \]

用这种方法也可以推多项式求逆。

多项式开根(限制常数版)

给定多项式 \(A(x)\) ,求 \(B(x)\) 使得
\[ B^2(x)-A(x)\equiv0\pmod{x^n} \]
设 \(B(x)\equiv B_0(x)\pmod{x^n}\) ,换句话说,设 \(B(x)\) 与 \(B_0(x)\) 的前 \(n\) 项相同。

再令 \(g(x)=B_0^2(x)-A(x)\) ,那么其导函数 \(g'(x)=2B_0(x)\) 。

这与牛顿迭代的定义相似,那么直接带入牛顿迭代,可得
\[ \begin{aligned} B(x)&\equiv B_0(x)-\frac{B_0^2(x)-A(x)}{2B_0(x)} \\ &\equiv\frac{1}{2}\left( B_0(x)+\frac{A(x)}{B_0(x)}\right)\pmod{x^{2n}} \end{aligned} \]
这样,我们也可以考虑用类似于倍增的思想。

时间复杂度 \(\mathcal O(n\log n)\) 。

> 说明:牛顿迭代不是 逼近 吗?怎么可以拿来求根,万一不精准呢?
>
> 我们想一个问题,在我们普通的一些求根之中,不可能也算到精准吧?
>
> 比如 \(\sqrt2=1.414...\) 而我们一般都取 \(1.414\) 等等。
>
> 多项式也是如此

这是最普通版本,即常数项为 \(1\) 时的开根。

拓展版本会在之后补上。

#define rep(i,__l,__r) for(int i=__l,i##_end_=__r;i&lt;=i##_end_;++i)
#define fep(i,__l,__r) for(int i=__l,i##_end_=__r;i&gt;=i##_end_;--i)
const int inv2=qkpow(2,MOD-2,MOD);
void polysqrt(const int* A,int* B,const int n){
    if(n==1)return (void)(B[0]=1);
    polysqrt(A,B,(n+1)&gt;&gt;1);
    static int tmp[MAXN+5],B1[MAXN+5];int p;
    polyinv(B,B1,n);
    for(p=1;p&lt;=n*2;p&lt;&lt;=1);
    rep(i,0,n-1)tmp[i]=A[i];rep(i,n,p)tmp[i]=0;
    ntt(B,p),ntt(B1,p),ntt(tmp,p);
    rep(i,0,p-1)B[i]=((0ll+B[i]+1ll*B1[i]*tmp[i])%MOD)*inv2%MOD;
    ntt(B,p,-1);
    rep(i,n,p)B[i]=0;rep(i,0,p)B1[i]=0;
}

当常数项不为一的时候,会使用到 二次剩余定理 对常数在取模意义下开根。


多项式的自然对数 ln (限制常数版)

对于一个多项式 \(A(x)\) ,求
\[ \ln(A(x))\pmod {x^n} \]

> 这里需要介绍两个自然对数与导数的特性
>
> 1. \(\ln'(x)=\frac{1}{x}\)
> 2. \((f(g(x)))'=f'(g(x))\cdot g'(x)\)
>
> 然后,我们继续推公式...

由微分的定义,可知
\[ \ln(A(x))=\int ((\ln(A(x)))') \]
注意到 \((\ln(A(x)))'\) ,可用我们刚刚补充的第二条展开,得
\[ (\ln(A(x)))'=\ln'(A(x))\cdot A'(x) \]
又注意到 \(\ln'(A(x))\) ,可用公式第一条展开,得
\[ \ln'(A(x))=\frac{1}{A(x)} \]
然后,再代回去,得
\[ \begin{aligned} \ln(A(x)) &=\int ((\ln(A(x)))')\\ &=\int(\ln'(A(x))\cdot A'(x))\\ &=\int(\frac{1}{A(x)}\cdot A'(x))\\ &=\int\frac{A'(x)}{A(x)} \end{aligned} \]
问题来了——导函数怎么求?

之前传过一道题:还不做做?再不做就晚了!

微分怎么求?都说了类似于导数的逆运算,怎么计算导数的,化一下公式就知道微分怎么求了。

其实我也不知道原理是什么,但数论就是靠背了...只是这样理解好记一些...

其中,求导和求微分都可以在 \(\mathcal O(n)\) ,因而时间复杂度基本上是逆元与 \(NTT\) 变换所花费的。

因而时间复杂度 \(\mathcal O(n\log n)\) 。

> 注意:求微分时有一个问题
>
> 还记得前面说的不定微分的问题吗?
>
> 这里我们求的其实就是不定微分。
>
> 所以,此处必须保证常数项为 \(1\) 。

#define rep(i,__l,__r) for(int i=__l,i##_end_=__r;i&lt;=i##_end_;++i)
#define fep(i,__l,__r) for(int i=__l,i##_end_=__r;i&gt;=i##_end_;--i)
void polyln(const int* A,int* B,const int n){
    static int tmp[MAXN+5];int p;
    for(p=1;p&lt;=n*2;p&lt;&lt;=1);
    polyinv(A,B,n);
    rep(i,1,n-1)tmp[i-1]=1ll*A[i]*i%MOD;rep(i,n-1,p)tmp[i]=0;
    ntt(tmp,p),ntt(B,p);
    rep(i,0,p-1)B[i]=1ll*B[i]*tmp[i]%MOD;
    ntt(B,p,-1);
    fep(i,n-1,1)B[i]=1ll*B[i-1]*qkpow(i,MOD-2,MOD)%MOD;
    B[0]=0;rep(i,n,p)B[i]=0;
}

多项式 exp (限制常数版)

\(\exp\) 是什么?可以理解为 \(\ln\) 的逆运算,即

对于一个多项式 \(A(x)\) ,求
\[ e^{A(x)}\pmod{x^n} \]

\[ B(x)=e^{A(x)}\pmod{x^n} \]
两边同时取对数,那么
\[ \begin{aligned} \ln(B(x))&\equiv A(x)&\pmod{x^n}\\ \Longrightarrow\ln(B(x))-A(x)&\equiv0&\pmod{x^n} \end{aligned} \]
考虑使用牛顿迭代,同理于求开根,我们令 \(B(x)\equiv B_0(x)\pmod{x^n}\) ,它的另一重含义应该都明白吧...

为了使过程方便理解,再设 \(g(x)=\ln(B_0(x))-A(x)\) 。

带入牛顿迭代,就有
\[ \begin{aligned} B(x)&\equiv B_0(x)-\frac{g(x)}{g'(x)}&\pmod{x^{2n}}\\ \Longrightarrow B(x)&\equiv B_0(x)-\frac{\ln(B_0(x))-A(x)}{\ln'(B_0(x))}&\pmod{x^{2n}}\\ \Longrightarrow B(x)&\equiv B_0(x)-\frac{\ln(B_0(x))-A(x)}{\frac{1}{B_0(x)}}&\pmod{x^{2n}}\\ \Longrightarrow B(x)&\equiv B_0(x)(1-\ln(B_0(x))+A(x))&\pmod{x^{2n}} \end{aligned} \]
我们已经知道怎么求 \(\ln\) 了,所以可以考虑倍增。

规定: \(A(x)\) 的常数必须为 \(0\) ,\(B(x)\) 的常数项必定为一。

要问为什么?前者不知道 后者是因其使用了 \(\ln\) 函数,而 \(\ln\) 函数的使用是有规定的。

计算复杂度是熟悉的 \(\mathcal O(n\log n)\) 。

#define rep(i,__l,__r) for(int i=__l,i##_end_=__r;i&lt;=i##_end_;++i)
#define fep(i,__l,__r) for(int i=__l,i##_end_=__r;i&gt;=i##_end_;--i)
void polyexp(const int* A,int* B,const int n){
    if(n==1)return (void)(B[0]=1);
    polyexp(A,B,(n+1)&gt;&gt;1);
    static int tmp[MAXN+5];int p;
    polyln(B,tmp,n);
    rep(i,0,n-1)tmp[i]=(0ll+!i-tmp[i]+A[i]+MOD)%MOD;
    //只在常数项 + 1, 其他的地方不用加
    for(p=1;p&lt;=2*n;p&lt;&lt;=1);
    ntt(tmp,p),ntt(B,p);
    rep(i,0,p-1)B[i]=1ll*B[i]*tmp[i]%MOD;
    ntt(B,p,-1);
    rep(i,n,p)B[i]=0;rep(i,0,p)tmp[i]=0;
}

多项式 k 次幂

给定 \(f(x)\) ,求 \(f^k(x)\) 的前 \(n\) 项系数,即求
\[ f^k(x)\pmod{x^n} \]
系数在 \(\pmod{998244353}\) 下进行。

首先思考,直接用 qkpow 计算,时间复杂度?

无疑,时间在 \(\mathcal O(n\log n\log k)\) 左右。

但是,对于这道题:luoguOJ-P5245 ...

其中, \(k\le 10^{10^5}\) ?

> 做个锤子...不做了...

心态要稳...不要慌。

根据 \(\text{OI}\) 多年的经验,这道题的时间复杂度计算不可能跟 \(k\) 有关,或者花式 \(T\) 飞?

因而, 我们又来推公式了...


分两种情况:

> - 情况一:当 \(f(x)\) 的常数项为 \(1\) 时。
>
> 此时可以使用前面的 \(\ln\) 函数,那么就有
> \[ f^k(x)=\exp(k\ln(f(x))) \]
> 时间复杂度为 \(\mathcal O(n\log n)\) 。
>
> - 情况二:当 \(f(x)\) 的常数不为 \(1\) 时。
>
> 此时我们不能使用十分好用的 \(\ln\) 函数了,那么怎么办?
>
> 其实也很简单,我们做这样的处理:
>
> 设 \(f(x)\) 的最低次项为 \(ax^d\) ,那么
> \[ f^k(x)=a^kx^{kd}\left (\frac{f(x)}{ax^d}\right )^k \]
> 这样就可以计算了。

例题:luoguOJ-P5245


结语及完整封装版本

这篇博客写的时间还真够久的。

其实我在写博客的同时,也在一道一道例题地过,虽然说操作较多,但是慢慢来还是会好的。

封装代码之后会出来,应该会发在 挑战多项式 的代码之中。

网址之后发出来。

个人封装版本

声明:该文章系转载,转载该文章的目的在于更广泛的传递信息,并不代表本网站赞同其观点,文章内容仅供参考。

本站是一个个人学习和交流平台,网站上部分文章为网站管理员和网友从相关媒体转载而来,并不用于任何商业目的,内容为作者个人观点, 并不代表本网站赞同其观点和对其真实性负责。

我们已经尽可能的对作者和来源进行了通告,但是可能由于能力有限或疏忽,导致作者和来源有误,亦可能您并不期望您的作品在我们的网站上发布。我们为这些问题向您致歉,如果您在我站上发现此类问题,请及时联系我们,我们将根据您的要求,立即更正或者删除有关内容。本站拥有对此声明的最终解释权。